C语言第五章.ppt

算法举例 基本思想是，根据提出的问题，列举所有可能的情况，并 用问题中给定的条件检验哪些是需要的，哪些是不需要的。 教学进程 列举与试探 列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。 ● 列举算法 【例】 某参观团按以下限制条件从A，B，C，D，E五个地方 中选定若干参观点： 1）如果去A地，则必须去B地； 2）D和E两地中只能去一地； 3）B和C两地中只能去一地； 4）C和D两地要么都去，要么都不去； 5）如果去E地，则必须去A和D地。问该参观团能去哪几个地方？ 用a、b、c、d、e五个整型变量， 分别表示A、B、C、D、E是否去的 状态。若变量值为1，则表示该地去； 若变量值为0，则表示该地不去。 教学进程 #include stdio.h main() { int a，b，c，d，e； for (a=0； a＜=1； a++) for (b=0； b＜=1； b++) for (c=0； c＜=1； c++) for (d=0； d＜=1； d++) for (e=0； e＜=1； e++) if ((a b || !a) d+e==1 b+c==1 (c+d==2 || c+d==0) (e a+d==2 || !e)) { printf(A will ％s be go.\n，a?: not)； printf(B will ％s be go.\n，b?: not)； printf(C will ％s be go.\n，c?: not)； printf(D will ％s be go.\n，d?: not)； printf(E will ％s be go.\n，e?: not)； } } 运行结果如下： A will not be go. （不去） B will not be go. （不去） C will be go. （去） D will be go. （去） E will not be go. （不去） 列举与试探 教学进程 在前面所讨论的列举算法中，一般总是知道列举量，其列 举的情况总是有限的。而在另外一些问题中，可能其列举量事 先并不知道，只能从初始情况开始，往后逐步进行试探，直到 满足给定的条件为止。这就是逐步试探的方法。 ● 试探算法 【例】 某幼儿园按如下方法依次给A、B、C、D、E五个小孩 发苹果。将全部苹果的一半再加二分之一个苹果发给第一个小孩； 将剩下苹果的三分之一再加三分之一个苹果发给第二个小孩；将剩 下苹果的四分之一再加四分之一个苹果发给第三个小孩；将剩下苹 果的五分之一再加五分之一个苹果发给第四个小孩；将最后剩下的 11个苹果发给第五个小孩。每个小孩得到的苹果数均为整数。 编制一个C程序，确定原来共有多少个苹果？每个小孩各得到 多少个苹果？P146 试探算法 教学进程 #include stdio.h main() { int n，flag，k，x，a，b，c，d，e； n=11； /*试探初值*/ flag=1； while(flag) /*进行试探*/ { x=n； /*保存当前试探值*/ flag=0；/*清标志值*/ for (k=1； k＜=4 flag==0； k++) /*模拟四次发放过程*/ if ((n+1)％(k+1)==0) /*该小孩得到的是整数个苹果*/ n=n-(n+1)/(k+1)； /*计算余下的苹果数*/ else flag=1； /*该小孩得到的不是整数个苹果，置标志值*/ if (flag==0 n!=11) flag=1；/*每次分配都得到整数个苹果，且最后剩下11个苹果*/ n=x+1； /*下一次的试探值*/ } 试探算法 教学进程 printf(Total number of apple=％d\n，x)；/*输出总的苹果数*/ a=(x+1)/2； /*第一个小孩分到的苹果数*/ b=(x-a+1)/3； /*第二个小孩分到的苹果数*/ c=(x-a-b+1)/4； /*第三个小孩分到的苹果数*/ d=(x-a-b-c+1)/5；/*第四个小孩分到的苹果数*/