用篩法求出100以內(nèi)的全部素數(shù)

例6、用篩法求出100以內(nèi)的全部素數(shù)，并按每行五個數(shù)顯示。

【問題分析】

⑴把2到100的自然數(shù)放入a[2]到a[100]中（所放入的數(shù)與下標(biāo)號相同）；

⑵在數(shù)組元素中，以下標(biāo)為序，按順序找到未曾找過的最小素數(shù)minp,和它的位置p（即下標(biāo)號）；

⑶從p+1開始，把凡是能被minp整除的各元素值從a數(shù)組中劃去（篩掉），也就是給該元素值置0；

⑷讓p=p+1，重復(fù)執(zhí)行第②、③步驟，直到minp>Trunc(sqrt(N))為止；

⑸打印輸出a數(shù)組中留下來、未被篩掉的各元素值，并按每行五個數(shù)顯示。

用篩法求素數(shù)的過程示意如下（圖中用下劃線作刪去標(biāo)志）：

①23456789101112131415…9899100｛置數(shù)｝

②23456789101112131415…9899100{篩去被2整除的數(shù)}

③23456789101112131415…9899100{篩去被3整除的數(shù)}

……

23456789101112131415…9899100{篩去被整除的數(shù)}

ProgramExam53;

constN=100;

typexx=1..N;{自定義子界類型xx（類型名）}

Vara:array[xx]ofboolean;i,j:integer;

Begin

Fillchar(a,sizeof(a),true);

a[1]:=False;

fori:=2toTrunc(sqrt(N))do

ifa[I]then

forj:=2toNdivIdo

a[I*j]:=False;

t:=0;

fori:=2toNdo

ifa[i]then

Begin

write(a[i]:5);inc(t);

iftmod5=0thenwriteln

end;

End.

【例3】輸入十個正整數(shù)，把這十個數(shù)按由大到小的順序排列（將數(shù)據(jù)按一定順序排列稱為排序，排序的算法有很多，其中選擇排序中的“簡單選擇排序”是一種較簡單的方法）

分析：要把十個數(shù)按從大到小順序排列，則排完后，第一個數(shù)最大，第二個數(shù)次大，……；因此，我們第一步可將第一個數(shù)與其后的各個數(shù)依次比較，若發(fā)現(xiàn)，比它大的，則與之交換，比較結(jié)束后，則第一個數(shù)已是最大的數(shù)。同理，第二步，將第二個數(shù)與其后各個數(shù)再依次比較，又可得出次大的數(shù)。如此方法進(jìn)行比較，最后一次，將第九個數(shù)與第十個數(shù)比較，以決定次小的數(shù)。于是十個數(shù)的順序排列結(jié)束。

例如下面對5個進(jìn)行排序，這個五個數(shù)分別為829105。按選擇排序方法，過程如下：

初始數(shù)據(jù)：829105

第一輪排序：829105

928105

102895

102895

第二輪排序：108295

109285

109285

第三輪排序：109825

109825

第四輪排序：109852

對于十個數(shù)，則排序要進(jìn)行9次。源程序如下：

programex5_2;

var

a:array[1..10]ofinteger;

i,j,t:integer;

begin

writeln('Input10integers:');

fori:=1to10doread(a[i]);｛讀入10個初始數(shù)據(jù)｝

readln;

fori:=1to9do｛進(jìn)行9次排序｝

begin

forj:=i+1to10do｛將第i個數(shù)與其后所有數(shù)比較｝

ifa[i]<a[j]then｛若有比a[i]大,則與之交換｝

begin

t:=a[i];a[i]:=a[j];a[j]:=t;

end;

write(a[i]:5);

end;

end.

例5、編程輸入十個正整數(shù)，然后自動按從大到小的順序輸出。（冒泡排序）

【問題分析】

①用循環(huán)把十個數(shù)輸入到A數(shù)組中；

②從A[1]到A[10]，相鄰的兩個數(shù)兩兩相比較，即：

A[1]與A[2]比，A[2]與A[3]比，……A[9]與A[10]比。

只需知道兩個數(shù)中的前面那元素的標(biāo)號，就能進(jìn)行與后一個序號元素（相鄰數(shù)）比較，可寫成通用形

式A[i]與A[i+1]比較，那么，比較的次數(shù)又可用1～(n-i)循環(huán)進(jìn)行控制(即循環(huán)次數(shù)與兩兩相比

較時前面那個元素序號有關(guān))；

③在每次的比較中，若較大的數(shù)在后面，就把前后兩個對換，把較大的數(shù)調(diào)到前面，否則不需調(diào)換位

置。

下面例舉5個數(shù)來說明兩兩相比較和交換位置的具體情形：

564375和6比較，交換位置，排成下行的順序；

654375和4比較，不交換，維持同樣的順序；

654374和3比較，不交換，順序不變

654373和7比較，交換位置，排成下行的順序；

65473經(jīng)過（1～（5-1））次比較后，將3調(diào)到了末尾。

經(jīng)過第一輪的1～(N-1)次比較，就能把十個數(shù)中的最小數(shù)調(diào)到最末尾位置，第二輪比較1～(N-2)次

進(jìn)行同樣處理，又把這一輪所比較的“最小數(shù)”調(diào)到所比較范圍的“最末尾”位置；……；每進(jìn)行一輪兩

兩比較后，其下一輪的比較范圍就減少一個。最后一輪僅有一次比較。在比較過程中，每次都有一個“最

小數(shù)”往下“掉”，用這種方法排列順序，常被稱之為“冒泡法”排序。

ProgramExam52;

constN=10;

Vara:array[1..N]ofinteger;｛定義數(shù)組｝

i,j:integer;

procedureSwap(Varx,y:integer);｛交換兩數(shù)位置的過程｝

Vart:integer;

begin

t:=x;x:=y;y:=t

end;

Begin

fori:=1toNdo｛輸入十個數(shù)｝

begin

Readln(a[i])

end;

forj:=1toN-1do｛冒泡法排序｝

fori:=1toN-jdo{兩兩相比較}

ifa[i]<a[i+1]thenswap(a[i],a[i+1]);{比較與交換}

fori:=1toNdo｛輸出排序后的十個數(shù)｝

write(a[i]:6);

Readln

end.例：讀入５個學(xué)生的學(xué)號和成績，計算他們的平均分，若比平均分高１０分的等第為A，若比平均分高小于１０分的等地為B，若低于平均分，則等第為C，輸出他們的成績和等第。

programsample7d1(input,output);

constn=5;

type

no=array[1..n]ofinteger;

s=array[1..n]ofreal;

var

i:integer;

k:real;

num:no;

score:s;

begin

k:=0;

fori:=1tondo

begin

readln(num[i],score[i]);

k:=k+score[i];

end;

k:=k/n;

fori:=1tondo

begin

write(num[i],score[i]);

if(score[i]-k)>=10thenwriteln('A')

elseif((score[i]-k)<10)and((score[i]-k)>0)thenwriteln('B')

elsewriteln('C');

end;

end.3．輸入一串小寫字母（以"."為結(jié)束標(biāo)志），統(tǒng)計出每個字母在該字符串中出現(xiàn)的次數(shù)(若某字母不出現(xiàn)，則不要輸出)，例：

輸入：aaaabbbccc.

輸出：a:4

b:3

c:3

4．輸入一個不大于32767的正整數(shù)N，將它轉(zhuǎn)換成一個二進(jìn)制數(shù)，例如：

輸入：100

輸出：1100100

＊5．輸入一個由10個整數(shù)組成的序列，其中序列中任意連續(xù)三個整數(shù)都互不相同，求該序列中所有遞增或遞減子序列的個數(shù)，例如：

輸入：11085932674

輸出：6

對應(yīng)的遞增或遞減子序列為：

110

1085

59

932

267

74

＊6．輸入Ｎ個數(shù)，將這Ｎ個數(shù)按從小到大的順序顯示出來；

＊＊7．猴子選大王：有N只猴子圍成一圈，每只猴子各一個從1到N中的依次編號，打算從中選出一個大王；經(jīng)過協(xié)商，決定出選大王的規(guī)則：從第一個開始循環(huán)報數(shù)，數(shù)到M的猴子出圈，最后剩下來的就是大王。要求：從鍵盤輸入N、M，編程計算哪一個編號的猴子成為大王

樣例：

輸入：７３

輸出：４

輸入：５２

輸出：３

待解：

輸入：９９９１５

輸出：？

＊＊8．編程求出100！的末尾有多少個連續(xù)的0；（100！=1×2×3×4×……×99×100）1、編程將一個十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)、八進(jìn)制數(shù)或十六進(jìn)制數(shù)。

例如輸入：73102

輸出：(73)10=(1001001)2

vari,j,n,m:longint;

b:array[1..30]ofinteger;

begin

write('Inputn,m:');readln(n,m);

write(n,'=(');i:=0;

whilen<>0do

begin?

i:=i+1;

b[i]:=nmodm;n:=ndivm

end;

forj:=idownto1do

caseb[j]of

10:write('A');

11:write('B');

12:write('C');

13:write('D');

14:write('E');

15:write('F');

??elsewrite(b[j]);

end;

write(')',m);

end.2、設(shè)計一個抽簽的程序。

vara:array[1..20]ofinteger;

r,i,t:integer;

begin

randomize;

fori:=1to20doa[i]:=i;

fori:=20downto1do

begin

r:=random(20)+1;

t:=a[i];a[i]:=a[r];a[r]:=t

end;

fori:=1to20dowrite(a[i]:5);

writeln

end.3、設(shè)有已按從小到大順序排列的數(shù)組A、B，將他們合并成一個從小到大順序排列的數(shù)組C。

4、給定一串整數(shù)數(shù)列，求出所有的遞增和遞減子序列的數(shù)目。如7,2,6,9,8,3,5,2可分為（7,2）、（2,6,9）、（9,8,3）、（3,5）、（5,2,1）5個子序列。答案是5。我們稱2,9,3,5為轉(zhuǎn)折元素。

vara:array[1..20]ofinteger;

i,c:integer;

begin

read(n);

fori:=1tondoread(a[i]);

i:=1;c:=1;

repeat

ifa[i]>a[i+1]

thenbegin

repeat

i:=i+1

until(i>=n-1)or(a[i]<=a[i+1]);

ifa[i]<a[i+1]thenc:=c+1;

end;

ifa[i]<a[i+1]

?thenbegin

repeat

i:=i+1

until(i>=n-1)or(a[i]>=a[i+1]);

ifa[i]>a[i+1]thenc:=c+1;

end;

?untili>=n-1;

?writeln('count:',c);

end.5、有一群猴子共N只，要選大王。它們約定排成一排，從頭到尾1至3報數(shù)，報到3的猴子留下，其余退出，留下的猴子再從尾到頭1至3報數(shù)，再留下報3的猴子，重新從頭到尾1至3報數(shù)，……，如此進(jìn)行，直到剩下的一只猴子為王，若剩下二只猴子，以原來站隊時排在后面的那只猴子為王。編程，輸出最初站在何處的猴子可為王。6、圍繞山頂有10個洞，一只兔子和一只狐貍各住在一個洞里。狐貍總想吃掉兔子。一天兔子對狐貍說，你想吃我，有一個條件，你把洞從1到10編號，先到第一個洞找我，第二次隔一個洞找我，第三次隔二個洞找我，以后依次類推，次數(shù)不限，若能找到我，可以飽餐一頓。狐貍答應(yīng)了條件，結(jié)果就是沒找到。假設(shè)狐貍找了1000次，兔子躲在哪個洞里才安全。

vara:array[1..10]ofinteger;

i,j,k,n:integer;

begin

fori:=1to10doa[i]:=0;

i:=10;n:=1;

whilen<=100do

begin?

i:=