用筛法求出100以内的全部素数

例6、用筛法求出100以内的全部素数，并按每行五个数显示。

【问题分析】

⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；

⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；

⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0；

⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N))为止；

⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。

用筛法求素数的过程示意如下（图中用下划线作删去标志）：

①23456789101112131415…9899100｛置数｝

②23456789101112131415…9899100{筛去被2整除的数}

③23456789101112131415…9899100{筛去被3整除的数}

……

23456789101112131415…9899100{筛去被整除的数}

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】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法）

分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。

例如下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如下：

初始数据：829105

第一轮排序：829105

928105

102895

102895

第二轮排序：108295

109285

109285

第三轮排序：109825

109825

第四轮排序：109852

对于十个数，则排序要进行9次。源程序如下：

programex5_2;

var

a:array[1..10]ofinteger;

i,j,t:integer;

begin

writeln('Input10integers:');

fori:=1to10doread(a[i]);｛读入10个初始数据｝

readln;

fori:=1to9do｛进行9次排序｝

begin

forj:=i+1to10do｛将第i个数与其后所有数比较｝

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、编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）

【问题分析】

①用循环把十个数输入到A数组中；

②从A[1]到A[10]，相邻的两个数两两相比较，即：

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

只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形

式A[i]与A[i+1]比较，那么，比较的次数又可用1～(n-i)循环进行控制(即循环次数与两两相比

较时前面那个元素序号有关)；

③在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位

置。

下面例举5个数来说明两两相比较和交换位置的具体情形：

564375和6比较，交换位置，排成下行的顺序；

654375和4比较，不交换，维持同样的顺序；

654374和3比较，不交换，顺序不变

654373和7比较，交换位置，排成下行的顺序；

65473经过（1～（5-1））次比较后，将3调到了末尾。

经过第一轮的1～(N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1～(N-2)次

进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；……；每进行一轮两

两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最

小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。

ProgramExam52;

constN=10;

Vara:array[1..N]ofinteger;｛定义数组｝

i,j:integer;

procedureSwap(Varx,y:integer);｛交换两数位置的过程｝

Vart:integer;

begin

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

end;

Begin

fori:=1toNdo｛输入十个数｝

begin

Readln(a[i])

end;

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

fori:=1toN-jdo{两两相比较}

ifa[i]<a[i+1]thenswap(a[i],a[i+1]);{比较与交换}

fori:=1toNdo｛输出排序后的十个数｝

write(a[i]:6);

Readln

end.例：读入５个学生的学号和成绩，计算他们的平均分，若比平均分高１０分的等第为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．输入一串小写字母（以"."为结束标志），统计出每个字母在该字符串中出现的次数(若某字母不出现，则不要输出)，例：

输入：aaaabbbccc.

输出：a:4

b:3

c:3

4．输入一个不大于32767的正整数N，将它转换成一个二进制数，例如：

输入：100

输出：1100100

＊5．输入一个由10个整数组成的序列，其中序列中任意连续三个整数都互不相同，求该序列中所有递增或递减子序列的个数，例如：

输入：11085932674

输出：6

对应的递增或递减子序列为：

110

1085

59

932

267

74

＊6．输入Ｎ个数，将这Ｎ个数按从小到大的顺序显示出来；

＊＊7．猴子选大王：有N只猴子围成一圈，每只猴子各一个从1到N中的依次编号，打算从中选出一个大王；经过协商，决定出选大王的规则：从第一个开始循环报数，数到M的猴子出圈，最后剩下来的就是大王。要求：从键盘输入N、M，编程计算哪一个编号的猴子成为大王

样例：

输入：７３

输出：４

输入：５２

输出：３

待解：

输入：９９９１５

输出：？

＊＊8．编程求出100！的末尾有多少个连续的0；（100！=1×2×3×4×……×99×100）1、编程将一个十进制数转换成二进制数、八进制数或十六进制数。

例如输入：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、设计一个抽签的程序。

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、设有已按从小到大顺序排列的数组A、B，将他们合并成一个从小到大顺序排列的数组C。

4、给定一串整数数列，求出所有的递增和递减子序列的数目。如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为转折元素。

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报数，报到3的猴子留下，其余退出，留下的猴子再从尾到头1至3报数，再留下报3的猴子，重新从头到尾1至3报数，……，如此进行，直到剩下的一只猴子为王，若剩下二只猴子，以原来站队时排在后面的那只猴子为王。编程，输出最初站在何处的猴子可为王。6、围绕山顶有10个洞，一只兔子和一只狐狸各住在一个洞里。狐狸总想吃掉兔子。一天兔子对狐狸说，你想吃我，有一个条件，你把洞从1到10编号，先到第一个洞找我，第二次隔一个洞找我，第三次隔二个洞找我，以后依次类推，次数不限，若能找到我，可以饱餐一顿。狐狸答应了条件，结果就是没找到。假设狐狸找了1000次，兔子躲在哪个洞里才安全。

vara:array[1..10]ofinteger;

i,j,k,n:integer;

begin

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

i:=10;n:=1;

whilen<=100do

begin?

i:=