C语言程序设计课件：第2章-基本程序设计-1.ppt

1、第三章第三章选择三种循环的一般原则选择三种循环的一般原则如果循环次数已知，用如果循环次数已知，用for如果循环次数未知，用如果循环次数未知，用while如果循环体至少要执行一次，用如果循环体至少要执行一次，用do-while这只是这只是“一般一般”原则，不是原则，不是“原则原则”注意注意在在for和和while语句之后一般没有分号语句之后一般没有分号有分号表示循环体就是分号之前的内容（空循环体）有分号表示循环体就是分号之前的内容（空循环体） while (i 100); i+; for (i = 0; i 100; i+); printf(%d, i);for通常有一个循环变量控制循环的次数，

2、不要在循通常有一个循环变量控制循环的次数，不要在循环体内改变这个变量环体内改变这个变量分析方法分析方法: :p逐步求精法。对于复杂问题，不可能直接逐步求精法。对于复杂问题，不可能直接得到程序，可以先将简单的部分明确出来，得到程序，可以先将简单的部分明确出来，再逐步对复杂部分进行细化，一步一步推再逐步对复杂部分进行细化，一步一步推出程序出程序以下图为例（共N 行，N 由键盘输入）。 * * * * * * * * * * * * * * * * 此类题目分析的要点是：通过分析，找出每行空格、* 与行号i及总行数N的关系。分析：（设N=4）第1行 3个空格=4-1 1个“*”=2*行号-1第2行

3、2个空格=4-2 3个“*”=2*行号-1第3行 1个空格=4-3 5个“*”=2*行号-1第4行 0个空格=4-4 7个“*”=2*行号-1由此归纳出：第i行的空格数N-i个； 第i行的“*”数是2i-1个。 试下写代码循环嵌套循环嵌套在循环体中，又包在循环体中，又包含有循环结构即构含有循环结构即构成循环嵌套成循环嵌套1 2 3 4 5 6 7 8 9-12 43 6 94 8 12 165 10 15 20 256 12 18 24 30 367 14 21 28 35 42 498 16 24 32 40 48 56 649 18 27 36 45 54 63 72 81行循环行循环中包

4、含中包含列循环列循环5.2.1 5.2.1 switchswitch语句格式语句格式输出下三角形乘法九九表输出下三角形乘法九九表1 2 3 4 5 6 7 8 9-12 43 6 94 8 12 165 10 15 20 256 12 18 24 30 367 14 21 28 35 42 498 16 24 32 40 48 56 649 18 27 36 45 54 63 72 81思路：行号为思路：行号为i，列号为，列号为j(1=i=9)(1=j=i) 则：第则：第 i 行中一共要行中一共要输出输出 i 个乘积个乘积i=7j=5i*j#include main ( ) int i=1,

5、j; /* i:行计数器行计数器 j:列计数器列计数器 */ while (i = 9 ) /* 控制打印表头控制打印表头 */ printf (%4d,i+); printf (n-n); for (i=1;i=9;i+) /* 行循环入口行循环入口 */ j=1; /* 列计数器置列计数器置1 */ while (j=i ) /*嵌套的内循环。输出第嵌套的内循环。输出第i行行 */ printf (“%4d”, i*j); /*输出乘积输出乘积 */ j +; /* 列计数器列计数器+1 */ printf (n); /* 一行输出结束后，输出一行输出结束后，输出n */ 打印九九乘法表打

6、印九九乘法表( (三角形三角形) )内循环终内循环终值与外循值与外循环变量有环变量有关关若要打印完整的九九乘法表，若要打印完整的九九乘法表，则哪里需要修改？则哪里需要修改？枚举法（穷举法）枚举法（穷举法） “笨人之法笨人之法”： 把所有可能的情况一一测试，筛选出符把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。合条件的各种结果进行输出。穷举法程序设计穷举法程序设计从搜索技术角度讲，穷举法可视为最简单的搜索：从搜索技术角度讲，穷举法可视为最简单的搜索：即是在一个可行状态集合中即是在一个可行状态集合中依次遍历所有的元素依次遍历所有的元素，并判断该元素是否为所需要的状态。并判断该元素是否

7、为所需要的状态。使用穷举法时，要恰当地设计变量，并且使用穷举法时，要恰当地设计变量，并且决定用哪决定用哪些变量作为搜索的主线些变量作为搜索的主线，以便穷举出所有可能情，以便穷举出所有可能情况。况。一般使用一般使用循环结构循环结构，要注意循环的起点和终点，对，要注意循环的起点和终点，对可能的情况不能遗漏，一般也不应重复。可能的情况不能遗漏，一般也不应重复。穷举算法基本思想穷举算法基本思想（1） 明确问题要求，确定枚举对象，用合适类型的明确问题要求，确定枚举对象，用合适类型的变量变量表示枚举对象表示枚举对象。（2） 明确枚举明确枚举对象的取值范围对象的取值范围。（3） 根据题目要求，写出根据题目要

8、求，写出有关的条件表达式有关的条件表达式。这里。这里条件表达式可以是数学表达式、关系表达式或逻辑条件表达式可以是数学表达式、关系表达式或逻辑表达式；表达式；（4） 使用使用循环语句枚举循环语句枚举出可能的解，在循环体内验出可能的解，在循环体内验证各种条表达式是否满足；证各种条表达式是否满足；（5） 根据问题背景，根据问题背景，优化程序优化程序，以便缩小搜索范围，以便缩小搜索范围，减少程序运行时间。减少程序运行时间。 枚举法（穷举法）枚举法（穷举法） “笨人之法笨人之法”： 把所有可能的情况一一测试，筛选出符把所有可能的情况一一测试，筛选出符合条件的各种结果进行输出。合条件的各种结果进行输出。分

9、析：分析： 这是个不定方程这是个不定方程三元一次方程组问题三元一次方程组问题 （三个变量，两个方程）（三个变量，两个方程） xyz=100 5x3yz/3=100 设公鸡为设公鸡为x只，母鸡为只，母鸡为y只，小鸡为只，小鸡为z只。只。 百元买百鸡问题分析百元买百鸡问题分析xyz=1005x3yz/3=100三重循环void main() int x,y,z; for (x=0;x=100;x+) for (y=0;y=100;y+) for (z=0;z=100;z+) if (x+y+z=100 & 5*x+3*y+z/3=100 ) printf(x=%d,y=%d,z=%dn,x,y,z

10、); 结果：x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84【讨论讨论】为什么多了几组解为什么多了几组解? ?百元买百鸡问题分析百元买百鸡问题分析void main() int x,y,z; for (x=0;x=100;x+) for (y=0;y=100;y+) for (z=0;z=100;z+) if (z%3=0 &x+y+z=100 & 5*x+3*y+z/3=100 ) printf(x=%d,y=%d,z=%dn,x,y,z); 结果：x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81

11、 x=12,y=4,z=84【讨论讨论】 此为此为“最笨最笨”之法之法要进行要进行101101101= 1030301次次（100多万次）运算。多万次）运算。优化优化void main() int x,y,z; for (x=0;x=100;x+) for (y=0;y=100;y+) z=100-x-y; if (z%3=0 & 5*x+3*y+z/3=100 ) printf(cocks=%d,hens=%d,chickens=%dn,x,y,z); 【讨论讨论】 令令z=100-x-y 只进行只进行101101= 10201 次运算（前者的次运算（前者的1%） 取取x=20,y=33 只

12、进行只进行2134= 714 次运算（第次运算（第1种运算的种运算的6.9e-4） 继续优化继续优化void main() int x,y,z; for (x=0;x=14;x+) for (y=0;y=25;y+) if (7*x+4*y=100 ) z=100-x-y; printf(cocks=%d,hens=%d,chickens=%dn,x,y,z); 取取x=14,y=25 只进行只进行1526= 390 次运算次运算方程组消去变量方程组消去变量z，可以得到满足方程可以得到满足方程 7*x+4*y=100 利用穷举法求解趣味智力题利用穷举法求解趣味智力题(韩信点兵韩信点兵)韩信有一

13、队兵，他想知道有多少人，便让士兵韩信有一队兵，他想知道有多少人，便让士兵排队报数。按从排队报数。按从1至至5报数，最末一个士兵报报数，最末一个士兵报的数为的数为1；按从；按从1至至6报数，最末一个士兵报的报数，最末一个士兵报的数为数为5；按从；按从1至至7报数，最末一个士兵报的数报数，最末一个士兵报的数为为4；最后再按从；最后再按从1至至11报数，最末一个士兵报数，最末一个士兵报的数为报的数为10。你知道韩信至少有多少兵吗？。你知道韩信至少有多少兵吗？设兵数为设兵数为x，则，则x应满足：应满足：x%5 = 1 & x%6 = 5 & x%7 = 4 & x%11 = 10穷举法对穷举法对x从从

14、1开始试验开始试验#include void main()int x;for (x=1; x 5000 ;x+)if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); /*属于属于“瞎猫碰死耗子瞎猫碰死耗子”的做法的做法*/穷举法求解韩信点兵穷举法求解韩信点兵#include void main()int x;for (x=1; ;x+)if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); /*死循环死循环永远不会退出的循环永远不会退出的循环*/穷举法求解韩信点兵穷举法求解韩信

15、点兵穷举法求解韩信点兵：方案穷举法求解韩信点兵：方案1-break1-break#include void main()int x;for (x=1; ;x+) if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); break; 穷举法求解韩信点兵穷举法求解韩信点兵: :方案方案2- 2-标志变量标志变量#include void main()int x; int find = 0; /*设置找到标志为假设置找到标志为假*/for (x=1; !find ;x+) if (x%5=1 & x%6=5 & x%7=4 & x%11=10

16、)printf( x = %dn, x); find = 1; 课堂讨论：谁做的好事？课堂讨论：谁做的好事？ 例例4-7 4-7 有四位同学中的一位做了好事，不留名，表扬信有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。来了之后，校长问这四位是谁做的好事。 A A说：不是我。说：不是我。 B B说：是说：是C C。 C C说：是说：是D D。 D D说：说：C C胡说。胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。这些信息，找出做了好事的人。显然，不是显然，不是AA做的好事（

17、做的好事（四个关系表达式值的和为四个关系表达式值的和为1 1）显然，不是显然，不是BB所为（所为（四个关系表达式值的和为四个关系表达式值的和为2 2）显然，就是显然，就是CC做了好事（做了好事（四个关系表达式值之和为四个关系表达式值之和为3 3）这时，我们可以理出头绪，要用枚举法，一个人一个人地去这时，我们可以理出头绪，要用枚举法，一个人一个人地去试，四句话中有三句为真，该人即所求。试，四句话中有三句为真，该人即所求。#includevoid main( ) char thisman;int sa,sb,sc,sd,cond;for (thisman=A; thisman=D; thisman+)sa=(thisman != A);sb=(thisman = C);sc=(thisman = D);sd=(thisman != D);cond=sa+sb+sc+sd;if (cond=3) printf(做好事的人是：做好事的人是：%cn, thisman);2022-1-2030