程序设计中的基本算法(修改).ppt
《程序设计中的基本算法(修改).ppt》由会员分享,可在线阅读,更多相关《程序设计中的基本算法(修改).ppt(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; en
16、d.,例题6:邮局发行一套四种面值的邮票,如果每封信所贴邮票张数不超过3张,存在整数r,使得用不超过三枚的邮票,可以贴出连续的整数1、2、3、r来,找出这四种面值邮票,使得r值最大。 问题分析: 本题与上题有相似之处,上题知道总长,搜索7个刻度,而本题则是知道每封信邮票数的范围(=3),邮票有四种面值,编程找出能使连续面值最大的邮票。 算法如下: 面值不同的四种邮票,每封信所贴邮票数不超过3张; 用这四种邮票贴出连续的整数,并且使得 r 值最大; 用穷举法,找出所有符合条件的解; 利用集合的方法统计邮票的面值,提高判重的速度。程序优化 设四种邮票的面值分别为 a,b,c,d,根据题意设 abc
17、d,因此a=1,用循环语句完成搜索。,program ex6_youpiao; var a,b,c,d:integer; x,x0,x1,x2,x3,x4:integer; st1:set of 1100; function number(a,b,c,d:integer):integer; var n1,n2,n3,n4,sum:integer; begin st1:=; for n1:=0 to 3 do for n2:=0 to 3-n1 do for n3:=0 to 3-n1-n2 do for n4:=0 to 3-n1-n2-n3 do if n1+n2+n3+n4x0 then
18、begin x0:=x; x1:=a; x2:=b; x3:=c; x4:=d; write(x1:5,x2:5,x3:5,x4:5); writeln(:10,x0=,x0); end; end; end.,贪心法,问题的可行解 问题的最优解 每个最优化问题都包含一组限制条件和一个优化函数,符合限制条件的问题求解方案称为可行解,使优化函数取得最佳值的可行解称为最优解。 贪心法从问题的某一个初始解出发,采用逐步构造最优解的方法向给定目标推进。在每个局部阶段,都做出一个看上去最优的决策(即某种意义下的、或某个标准下的局部最优解),并期望通过每次所做的局部最优选择产生出一个全局最优解。 做出贪心决
19、策的依据称为贪心准则(策略),决策一旦做出,就不可更改。,最优化问题,例题7:删数问题 键盘输入一个高精度的正整数n(240位),去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻求一方案,使得剩下的数字组成的新数最小。 输入: n s 输出:最后剩下的最小数 样例输入:178543 4 样例输出:13 问题分析: 正整数的位数为240位 如何决定哪s位被删除?是否是最大的连续s位的数字? 贪心策略:每一步总是选择一个使得剩下的数最小的数字删去 实现方法:按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符。这样便形成
20、一个新的字符串,然后回到串首,按上述的规则再删除下一个数字。重复以上过程s次,剩下的数字串便是问题的解。,n =178543 删掉8 17543 删掉7 1543 删掉5 143 删掉4 13,字符串类型存贮n,program ex6_shanshu; var i,j,k,s:integer; n:string; begin readln(n); readln(s); while s0 do begin i:=1; while (i1)and(n1=0) do delete(n,1,1); writeln(n); end.,删数问题与如何寻找递减区间首字符的问题对应起来。 注意:字符串串首有若
21、干个0的情况,甚至字符串都是0的情况。,例题8:最大数问题 设有n个正整数(n20),将它们连成一排,组成一个最大的多位整数。例如:n=3时,3个整数13、312、343连成的最大整数为34331213。 输入:包括两行,第一行是一个整数n,第二行有n个整数,它们之间以空格隔开。 输出:连成的多位数。 样例输入:3 13 312 343 样例输出:34331213 问题分析: 利用贪心法则,在待选数中由高位向低位选择较大的数。对待选的数按字典顺序排序,以排序结果依次取数。 若待选数为24、241,则连成的最大数为24241。 改变原先比大小的方法,用A和B表示两个待选数,如果AB比BA大则说A
22、比B“大”,不断地在待选数中贪“大”,就可得到最大数。,program ex8_zuidashu; var n,x,i,j:integer; s:array040 of string; begin readln(n); for i:=1 to n do begin read(x); str(x,si); end; for i:=1 to n-1 do for j:=1 to n-1 do if sj+sj+1sj+1+sj then begin s0:=sj; sj:=sj+1; sj+1:=s0; end; for i:=1 to n do write(si); writeln; end.,
23、例题9:比赛预言 假设有M个人,包括你在内玩一种纸牌游戏。开始时,每一个游戏者接到N张牌,牌的分值是一个正整数,最大是MN,并且牌的分值各不相同。在一轮中,每个游戏者选一张牌和其他人比较。如果你的牌最大则你就赢了这轮,接着开始下一轮。N轮后,所有的牌都比较完毕,赢的轮次最多的人赢得比赛。 游戏开始时给你发牌,写一个程序判断你至少可以赢多少轮。 输入:由多组测试数据构成。每组测试数据的第一行包含两个整数m(2m20)和n(1n50),表示游戏参与者和每个人接到的牌的数量。下面的一行是你接到的牌的分值,每组数据后有一个空行隔开不同的测试数据。输入数据以一行中的两个0表示输入结束。 输出:对应每组测
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 中的 基本 算法 修改
链接地址:https://www.31doc.com/p-2250246.html