《程序设计中的基本算法(修改)》由会员分享，可在线阅读，更多相关《程序设计中的基本算法(修改)（135页珍藏版）》请在金锄头文库上搜索。
1、程序设计中的基本算法,什么是算法？ 简单来说算法是解决问题的方法和步骤，它不是问题的答案，但它是经过准确定义的，用来获得答案的过程。 一个好的算法，占用空间小，运行时间短，计算机科学家和程序设计员一直在追求更高效的算法。,模拟法,有些问题的描述和解决方法已经很清楚，只需要按照描述去一步一步的执行即可，这种方法就是计算机解决问题的一种最普遍最直接的方法模拟法。模拟法并不是算法，它只是我们依赖计算机的运算速度解决问题的一种方法或模式，针对具体问题设计具体的程序。 模拟法适用于问题求解清晰，运算规模较小的问题，如果问题求解的时空代价很大就要考虑是否有其它更优的解决方案。,例题1：酗酒的狱警 某监狱里
2、有个很长的走廊,走廊中一个接一个有n个房间。每个房间中锁着一个犯人。一天夜里,狱警决定玩一个无聊游戏。第一轮中,他喝了一口威士忌,然后打开走廊间每个房子。第2轮,他喝了一口威士忌,然后按2的倍数遍历每个房子，第3轮，他又喝了一口威士忌，遍历所有3的倍数的房间，依次类推。在遍历中，如果房间是锁的，则打开否则锁上。他这样重复n轮,最终醉酒。这时有些囚犯人看到自己房间的所以打开，他们立即逃跑。对于有n间房子的走廊，最终会有多少囚犯逃脱。 输入：第一行中输入一个整数表示有多少组测试数据。接下来的若干行，每行包含一个5至100整数,这是房间的数目，输出：对应输入数据输出多行，每行一个整数，表示逃脱的囚犯
3、数量。 样例输入： 2 5 100 样例输出： 2 10,【问题分析】： 由于问题的规模较小，按照题意用一个200个元素的布尔型数组表示房间的状态，“true”表示房间门是关闭的，“false”表示房间门是开的。每次遍历数组，将当前数到数的倍数元素的状态反转，最后遍历数组统计房间开着的个数输出。 【程序实现】： program exp1_1; var num,s,n,m,i,k,j:integer; a:array0200 of boolean; begin readln(num); 读入测试数据的个数 for i:=1 to num do begin readln(n); 读入房间数 fil
4、lchar(a,sizeof(a),true); for j:=1 to n do for k:=1 to n do if k mod j=0 then ak:=not ak; s:=0; for j:=1 to n do 统计个数 if aj=false then inc(s); writeln(s); end; end.,例题2：分发糖果 一些学生围绕老师座着，每人手里都有偶数个糖果，现在老师吹一声哨子，所有学生同时将自己的一半糖果给他右边的同学，如果某个同学手里的糖果个数是奇数则老师给他一个糖果。重复这个过程直到所有同学手中的糖果数一致。 写一个程序判断老师要吹多少下哨子每人手中的糖果数
5、才能一致，结束后每人手里又有多少个糖果。 输入： 包含多组数据，每组数据的第一行是一个数字n，表示学生的个数，下面的n行以顺时针次序，每行一个数字表示每个学生手里的糖果个数，输入以学生个数为0结束。 输出： 对于每组数据输出一行包含两个数据，老师吹哨子的次数和学生最后平均的糖果数，中间以空格相隔。,样例输入： 6 36 2 2 2 2 2 11 22 20 18 16 14 12 10 8 6 4 2 4 2 4 6 8 0,样例输出： 15 14 17 22 4 8,【问题分析】： 首先判断每个人的糖果数是否相等，如果相等则分配结束，否则开始重新分配过程。由于题目中说明是同时将每人手里的糖果
6、数的一半给右边的人，而用程序实现时是逐句执行，因此若用ai表示每人手里的糖果数，q表示第i-1位手中的原糖果数，则有： ai:=ai div 2 + q div 2 接下来判断这时ai是否是奇数，如果是奇数，教师再给他一个糖果并计数，重复上面的过程直到每人手里的糖果数相等。,枚举法,枚举法解决问题的基本思路是依次枚举问题的所以可能解，按照问题的约束条件进行判断，如果满足约束条件则得到一组解，这个过程不断的进行下去最终得到整个问题的解。可以说模拟法主要关心问题“怎么做”，枚举法主要关心当前的可能解“是不是”。 要用枚举法解决问题，首先需要知道解的范围并能以合适的方法列举，其次要对问题的约束条件进
7、行精确的描述，这两个环节有一个疏漏就有可能丢失正确解或多出错误解。枚举法虽然实现起来很容易，但对于大数据量的枚举效率是很低的。,例题3：四人中有一人是小偷，现在警察得到了这样的证词： A说：不是我。 B说：是C。 C说：是D。 D说：他胡说。 已知3个人说的是真话，一个人说的是假话。现在要根据这些信息，确认小偷是谁。 【问题分析】： 假设小偷是“thisman”，由于“thisman”的取值无非是A、B、C、D，如果我们让“thisman”的取值依次是AD，分别对4个关系式求值，如果为“True”的表达式有3个那么这时“thisman”的值就是问题的解。 已知的证词可以表示为： “证词表述”
8、证词 语句表示 A说：不是我 ThismanA; B说：是C Thisman=C; C说：是D Thisman=D; D说：他胡说 ThismanD;,program exp1_3; var n:integer; t:char; begin for t:=A to D do begin n:=ord(tA)+ord(t=C)+ord(t=D)+ord(tD); if n=3 then writeln(thisman is ,t); end; end.,例题4： 数字三角形（NOIP1997普及组第2题） 把1，2， 9共9个数排成下列形状的三角形： a b c d e f g h i 其中：a
9、i分别表示1，2，.9中的一个数字，并要求同时满足下列条件： (1) afi （2）bd, gh， ce； （3）abdf fghi ieca P 程序要求：根据输入的边长之和P，输出所有满足上述条件的三角形的个数及方案。 【问题分析】： 按题意直接直接枚举就行。注意利用每个数之间的大小关系。在检测是用一个数组保存出现的数字，检测数组第19个元素就可以分辨19这9个数字是否不重复的出现。,program exp2_3; var a,b,c,d,e,f,g,h,i,k,p,sum:integer; bb:array-100100 of byte; begin readln(p); sum:=0;
10、 for a:=1 to 7 do for b:=1 to 8 do for c:=1 to 8 do for g:=1 to 8 do for f:=a+1 to 8 do for i:=f+1 to 9 do begin d:=p-a-b-f; if d=b then break; h:=p-f-g-i; if h=g then break; e:=p-a-c-i; if e=c then break; fillchar(bb,sizeof(bb),0); bba:=1;bbb:=1;bbc:=1;bbd:=1;bbe:=1;bbf:=1;bbg:=1;bbh:=1;bbi:=1; for
11、 k:=1 to 9 do if bbk=0 then break; if bbk=1 then begin inc(sum); writeln(a:3,b:3,c:3,d:3,e:3,f:3,g:3,h:3,i:3); end; end; writeln(sum); end.,例题5：一根29cm长的尺子，只允许在上面刻7个刻度，要能用它量出129cm的各种长度。试问这根尺子的刻度该怎么选择？ 问题分析： 从129cm中选择7个刻度的所有可能情况是C729 =1560780 对于每一组刻度的选择都需要判断是否能将129cm的各种刻度量出来。例如选择的刻度为：a1,a2,a3,a4,a5,a6
12、,a7那么能量出的刻度为： a1, 29a1 2 a2, a2a1, 29a2 3 a3, a3a1, a3a2, 29a3 4 a4, a4a1, a4a2, a4a3, 29a4 5 a5, a5a1, a5a2, a5a3, a5a4, 29a5 6 a6, a6a1, a6a2, a6a3, a6a4, a6a5, 29a6 7 a7, a7a1, a7a2, a7a3, a7a4, a7a5, a7a6, 29a7 8 可量出2+3+4+5+6+7+8种刻度，即35种刻度。事实上期中有许多刻度是重复的，不可能覆盖129。例如：a1,a2,a3,a4,a5,a6,a7为1，3，6，10
13、，15，21，28时，能量出的可度为： 1，28 3，2，26 6，5，3，23 10，9，7，4，19 15，14，12，9，5，14 21，20，18，15，11，6，8 28，27，25，22，18，13，7，1 缺16，17，24（29即尺子长度）,如果找出了刻度a1,a2,a3,a4,a5,a6,a7那么我们就可以利用对称性29-an 来求另一组解，所以求解过程中可仅考虑a1a2a3a4a5a6a7的情况。 很显然要使1，28两种刻度能量出来，则在7个刻度中就必须有1或28；这样就可以设a1=1（或a1=28）。题解就变成了在227中选取6个刻度的问题了。其刻度数目为C626=230
14、230。 这样解的范围就从百万数量级变成了十万的数量级，大大减少了运行次数。因此，我们在用穷举法求问题解时，应注意程序的优化，尽可能减少搜索时间。 为了判定7个刻度是否能够度量129的所有长度，可以用集合的方法，也可以用数组的0，1数据判断。,program ex5_kedu; const n=29; m=1; var a:array17 of integer; b:array1n of 01; 记录能量的刻度 f:boolean; i,j:integer; begin a1:=m; for a2:=2 to n-7 do for a3:=a2+1 to n-6 do for a4:=a3+1
15、 to n-5 do for a5:=a4+1 to n-4 do for a6:=a5+1 to n-3 do for a7:=a6+1 to n-2 do begin for i:=1 to 29 do bi:=0; for i:=1 to 7 do begin bai:=1;bn-ai:=1;bn:=1; 初始化 for j:=i+1 to 7 do babs(aj-ai):=1 end; j:=0; for i:=1 to n do j:=j+bi; if j=n then begin for i:=1 to 7 do write(ai:4); writeln end; end; end.,例题6：邮局发行一套四种面值的邮票，如果每封信所贴邮票张数不超过3张，存在整数r，使得用不超过三枚的邮票，可以贴出连续的整数1、2、3、
