程序设计实习讲义

《程序设计实习讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计实习第五讲枚举内容提要枚举的基本思想程序设计练习作业枚举一种解决问题的方法。例如：求小于N的最大素数找不到一个数学公式，使得我们根据N就可以计算出这个素数N-1是素数吗？N-2是素数吗？……N-K是素数的充分必要条件是：N-K不能被任何一个大于1、小于N-K的素数整除。判断N-K是否是素数的问题又成了求小于N-K的全部素数解决方法：2是素数，记为PRIM0根据PRIM0、PRIM1、…、PRIMk，寻找比PRIMk大的最小素数PRIMk+1。如果PRIMk+1大于N，则PRIMk是我们需要找的素数，否则继续寻找枚举的思想：列出所有可能的情况，逐一检查是否是问题的解关键：

2、可能的情况是什么有序地枚举，不漏掉情况尽早发现不是解的情况例1：完美立方(POJ1543)问题描述：a3=b3+c3+d3为完美立方等式。例如123=63+83+103。编写一个程序，对任给的正整数N(N≤100)，寻找所有的四元组(a,b,c,d)，使得a3=b3+c3+d3，其中1

3、5)Cube=12,Triple=(6,8,10)Cube=18,Triple=(2,12,16)Cube=18,Triple=(9,12,15)Cube=19,Triple=(3,10,18)Cube=20,Triple=(7,14,17)Cube=24,Triple=(12,16,20)逐一枚举a,b,c,d,#includevoidmain(){intn;scanf("%d",&n);intI,cube[101];for(i=0;i<=100;i++)cube[i]=i*i*i;inta,b,c,d;for(a=2;a<=n;a++)for(b=2;b

4、;b++)for(c=b;c

5、5盏灯的状态在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。各个按钮被按下的顺序对最终的结果没有影响对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重

6、复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。输入：第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。输出：对每个案例，首先输出一行，输出字符串“PUZZLE#m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。样例输入20110101001110010011001010111000010101010110

7、01011101100010100样例输出PUZZLE#1101001110101001011100100010000PUZZLE#2100111110000000100110101101101解题思路既然按钮按下的顺序不影响最后的结果，不妨假设从第一行往下一行一行按按钮按第二行按钮时必须把第一行灯全部熄灭，否则第三行以后的按钮再也不能改变第一行的灯这样只要枚举第一行的按钮组合情况，就可以判断所有灯的熄灭情况。第一行共有2的6次方种情况。源程序1222.cpp例3：poj1054