[布尔数组的应用.doc
文本预览下载声明
布尔数组的应用
布尔数组中存放的是布尔值，只有True和False两种结果，所以在有些程序中进行使用可以起到优化程序，甚至是事半功倍的效果。比如在搜索中就经常用到，可以使用布尔数组区分那些经过处理的和没有经过处理的数据，避免了一些不必要的重复。
例题1：使用筛选法求一个给定区域之间的所有素数。
筛选法求素数原理：在某个区间内，如果将所有素数的倍数删除，那么剩下的肯定是素数。
基本做法：建立一个布尔型的数组a[2..n]，开始时数组a的每一个元素均赋值为True，然后从2开始找最小的一个数，找到的第一个数2为素数，将2之后的所有2的倍数为下标的数组元素a[2*m](m=2,3,4,……)均赋值为False，然后找到下一个最小的数3，3也是素数，将3之后的所有3的倍数为下标的数组元素a[3*m](m=2,3,4,……)均赋值为False，接下来找到下一个最小的数5，5也是素数，将5之后的所有5的倍数为下标的数组元素a[5*m](m=2,3,4,……)均赋值为False，依次操作，每次找到的第一个数就是素数（为什么？），然后将这个数的所有倍数去掉，直到最后一个数。最后剩下的所有结果为True的数组元素的下标即为所有的素数。
素数a[x] 数据集合a 2 { 2， 3， 4， 5， 6， 7， 8， 9，10，11，12，13，14，15……} 3 { 3， 5， 7， 9， 11， 13， 15……} 5 { 5， 7， 11， 13， ……} …… ………
参考程序如下：
program example1(input,output);
var
i,j,n,k:integer;
flag:boolean;
a:array[1..1000000000] of longint;
f:array[1..1000000000] of boolean;
begin
read(n);
k:=0;
f[1]:=false;
for i:=2 to n do f[i]:=ture;
for i:=2 to n do
if f[i]
then begin
inc(k);
p[k]:=i;
j:=2*i;
while j=n do
begin
f[j]:=0;
inc(j,i)
end;
end
for i:=2 to k do write(i, );
End.
例题2：明明的随机数（全国信息学奥林匹克联赛 (NOIP2006) 复赛普及组第一题）
描述 Description
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式 Input Format
输入有2行，第1行为1个正整数，表示所生成的随机数的个数：
N
第2行有N个用空格隔开的正整数，为所产生的随机数。
输出格式 Output Format
输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入样例Sample Input
10
20 40 32 67 40 20 89 300 400 15
输出样例Sample Output
8
15 20 32 40 67 89 300 400
第一题明明的随机数参考程序1（先“去重”后“排序”）：
program random(input,output);
var
i,j,m,n,k:integer;
a:array[1..100] of integer;
begin
assign(input,random.in);
assign(output,random.out);
reset(input);
rewrite(output);
readln(n);
m:=0;
for i:=1 to n do {读入过程中直接“去重”}
begin
m:=m+
显示全部