程序设计中的基本算法修改

《程序设计中的基本算法修改》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计中的基本算法什么是算法？简单来说算法是解决问题的方法和步骤，它不是问题的答案，但它是经过准确定义的，用来获得答案的过程。一个好的算法，占用空间小，运行时间短，计算机科学家和程序设计员一直在追求更高效的算法。模拟法有些问题的描述和解决方法已经很清楚，只需要按照描述去一步一步的执行即可，这种方法就是计算机解决问题的一种最普遍最直接的方法—模拟法。模拟法并不是算法，它只是我们依赖计算机的运算速度解决问题的一种方法或模式，针对具体问题设计具体的程序。模拟法适用于问题求解清晰，运算规模较小的问题，如果问题求解的时空代价很大就要考虑是否有其它更优

2、的解决方案。例题1：酗酒的狱警某监狱里有个很长的走廊,走廊中一个接一个有n个房间。每个房间中锁着一个犯人。一天夜里,狱警决定玩一个无聊游戏。第一轮中,他喝了一口威士忌,然后打开走廊间每个房子。第2轮,他喝了一口威士忌,然后按2的倍数遍历每个房子，第3轮，他又喝了一口威士忌，遍历所有3的倍数的房间，依次类推。在遍历中，如果房间是锁的，则打开否则锁上。他这样重复n轮,最终醉酒。这时有些囚犯人看到自己房间的所以打开，他们立即逃跑。对于有n间房子的走廊，最终会有多少囚犯逃脱。输入：第一行中输入一个整数表示有多少组测试数据。接下来的若干行，每行包含一个

3、5至100整数,这是房间的数目，输出：对应输入数据输出多行，每行一个整数，表示逃脱的囚犯数量。样例输入：25100样例输出：210【问题分析】：由于问题的规模较小，按照题意用一个200个元素的布尔型数组表示房间的状态，“true”表示房间门是关闭的，“false”表示房间门是开的。每次遍历数组，将当前数到数的倍数元素的状态反转，最后遍历数组统计房间开着的个数输出。【程序实现】：programexp1_1;varnum,s,n,m,i,k,j:integer;a:array[0..200]ofboolean;beginreadln(num);{

4、读入测试数据的个数}fori:=1tonumdobeginreadln(n);{读入房间数}fillchar(a,sizeof(a),true);forj:=1tondofork:=1tondoifkmodj=0thena[k]:=nota[k];s:=0;forj:=1tondo{统计个数}ifa[j]=falsetheninc(s);writeln(s);end;end.例题2：分发糖果一些学生围绕老师座着，每人手里都有偶数个糖果，现在老师吹一声哨子，所有学生同时将自己的一半糖果给他右边的同学，如果某个同学手里的糖果个数是奇数则老师给他一

5、个糖果。重复这个过程直到所有同学手中的糖果数一致。写一个程序判断老师要吹多少下哨子每人手中的糖果数才能一致，结束后每人手里又有多少个糖果。输入：包含多组数据，每组数据的第一行是一个数字n，表示学生的个数，下面的n行以顺时针次序，每行一个数字表示每个学生手里的糖果个数，输入以学生个数为0结束。输出：对于每组数据输出一行包含两个数据，老师吹哨子的次数和学生最后平均的糖果数，中间以空格相隔。样例输入：6362222211222018161412108642424680样例输出：1514172248【问题分析】：首先判断每个人的糖果数是否相等，如果相

6、等则分配结束，否则开始重新分配过程。由于题目中说明是同时将每人手里的糖果数的一半给右边的人，而用程序实现时是逐句执行，因此若用a[i]表示每人手里的糖果数，q表示第i-1位手中的原糖果数，则有：a[i]:=a[i]div2+qdiv2接下来判断这时a[i]是否是奇数，如果是奇数，教师再给他一个糖果并计数，重复上面的过程直到每人手里的糖果数相等。枚举法枚举法解决问题的基本思路是依次枚举问题的所以可能解，按照问题的约束条件进行判断，如果满足约束条件则得到一组解，这个过程不断的进行下去最终得到整个问题的解。可以说模拟法主要关心问题“怎么做”，枚举法

7、主要关心当前的可能解“是不是”。要用枚举法解决问题，首先需要知道解的范围并能以合适的方法列举，其次要对问题的约束条件进行精确的描述，这两个环节有一个疏漏就有可能丢失正确解或多出错误解。枚举法虽然实现起来很容易，但对于大数据量的枚举效率是很低的。例题3：四人中有一人是小偷，现在警察得到了这样的证词：A说：不是我。B说：是C。C说：是D。D说：他胡说。已知3个人说的是真话，一个人说的是假话。现在要根据这些信息，确认小偷是谁。【问题分析】：假设小偷是“thisman”，由于“thisman”的取值无非是‘A’、‘B’、‘C’、‘D’，如果我们让“t

8、hisman”的取值依次是‘A’～‘D’，分别对4个关系式求值，如果为“True”的表达式有3个那么这时“thisman”的值就是问题的解。已知的证词可以表示为：“