算法与程序设计：第2章 穷举法与迭代法

1、第2章 穷举法与迭代法2.1 穷举法概念与举例穷举法概念与举例2.2 迭代法概念与举例迭代法概念与举例学习要点学习要点: 理解穷举法的概念。 掌握简单实例的编程。 理解迭代法的概念。 掌握简单实例的编程。第2章 穷举法与迭代法第2章 穷举法与迭代法2.1 穷举法概念与举例穷举法概念与举例2.2 迭代法概念与举例迭代法概念与举例2.1.1 穷举法（Enumerate）概念 穷举法穷举法：又叫枚举法，指按一定顺序对问：又叫枚举法，指按一定顺序对问题所有可能的候选区间进行校验，从中找出符题所有可能的候选区间进行校验，从中找出符合要求的解集。合要求的解集。通常用来求不定解。通常用来求不定解。 穷举法特

2、点穷举法特点穷举是最简单，最基础，也是最没效率的算法。穷举是最简单，最基础，也是最没效率的算法。穷举拥有很多优点，以致于它能够存活到现在而不被淘穷举拥有很多优点，以致于它能够存活到现在而不被淘汰。汰。 1）穷举具有超级无敌准确性，只要时间足够，正确）穷举具有超级无敌准确性，只要时间足够，正确的穷举得出的结论是绝对正确的。的穷举得出的结论是绝对正确的。 2）穷举拥有天下第一全面性，因为它是对所有方案）穷举拥有天下第一全面性，因为它是对所有方案的全面搜索，所以，它能够得出所有的解。的全面搜索，所以，它能够得出所有的解。2.1.1 穷举法（Enumerate）概念穷举法在使用时，主要考虑以下两个方面

3、穷举法在使用时，主要考虑以下两个方面：（1）找出穷举范围：分析问题所涉及的各种情况；（2）找出约束条件：分析问题的解需要满足的条件并用逻辑表达式表示。 程序实现时，通常需要用程序实现时，通常需要用多重循环多重循环（循环次（循环次数取决于变量的个数）来实现。数取决于变量的个数）来实现。2.1.1 穷举法（Enumerate）概念2.1.2 穷举法举例【例1】 把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？【例2】水仙花数-是指一个n(=3)位数字的数,它等于每个数字的n次幂之和。求1000以内的水仙花数。【例3 3】百鸡问题公元前五世纪，我国古代公元前五世纪，我国古代数学家张

4、丘建在数学家张丘建在算经算经一书中提出了一书中提出了“百鸡问百鸡问题题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？Flower( ) for(n=100;n10000;n+) i=n/100 j=n/10%10 k=n/100%10 if(n=i*i*i+j*j*j+k*k*k) 输出n求解水仙花数问题的伪代码算法1求解水仙花数问题的伪代码Flower() 1 for i1 to 9 2 do for j0 to 9 3 do for k0 to 9 4 do if i*i

5、*i+j*j*j+k*k*k=100*i+10*j+k 5 then 输出i j k算法2求解水仙花数穷举算法的C+代码#include flower( ) int a,b,c; for(a=1;a=9;a+) for(b=0;b=9;b+) for(c=0;c=9;c+) if(100*a+10*b+c=a*a*a+b*b*b+c*c*c) coutabc; coutendl; return 0;【例4】数独游戏：数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出

6、现一次。每一个粗线宫内的数字均含1-9，不重复。2.1.2 穷举法举例2.1.2 穷举法举例2.1.2 穷举法举例8594587969245879684141662843757196243884732528579【注意注意】每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。何无解或多解的题目都是不合格的。2.1.2 穷举法举例837659124245187963196234587759326841413578692628491375571962438984713256362845719

7、【注意注意】每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。何无解或多解的题目都是不合格的。2.2.1 迭代法（Iteration）概念迭代法迭代法是一种不断用变量的旧值递推出新值是一种不断用变量的旧值递推出新值的解决问题的方法。一般用于数值计算。的解决问题的方法。一般用于数值计算。迭代法两要素：迭代法两要素：（1）确定迭代模型：建立前一个（）确定迭代模型：建立前一个（n个）值与其下一个）值与其下一个值的迭代关系数学模型。个值的迭代关系数学模型。这是算法的关键步骤。这是算法的关键步骤

8、。（2）对迭代过程进行控制：即确定何时结束迭代过程。）对迭代过程进行控制：即确定何时结束迭代过程。难点：迭代法关键是找迭代关系，并确定初值。难点：迭代法关键是找迭代关系，并确定初值。2.2.2 迭代法分类迭代法有以下三种：迭代法有以下三种： 递推法递推法（Recursion）是迭代法最基本表现形式。是利用问题本身所具有的一种递推（迭代）关系求问题解的一种方法。 设要求解问题规模为N的解，当N1时，解或已知或能方便求得。 倒推法倒推法（Inverted Recursion）是从后向前推解问题的方法。 近似迭代法近似迭代法用于求解方程。2.2.3 递推法举例 如何建立递推关系？目前尚未总结出一个如

9、何建立递推关系？目前尚未总结出一个一般的方法，一般的方法，只能具体问题，具体分析只能具体问题，具体分析。 一般，先从最简单的情况分析人手，看一般，先从最简单的情况分析人手，看n1，n2，时的情况如何，这就是时的情况如何，这就是先建立先建立初始条件初始条件。 2.2.3 递推法举例【例例5】 要爬到一个小山的顶点，需要上要爬到一个小山的顶点，需要上10个台阶个台阶. 可以一步可以一步上一个台阶，也可以一步上两个台阶，有多少种不同的上山上一个台阶，也可以一步上两个台阶，有多少种不同的上山方式呢？方式呢？ 解：设爬山的台阶数为解：设爬山的台阶数为n，上到第，上到第n个台阶的方式数为个台阶的方式数为a

10、n。 若只有一个台阶若只有一个台阶n=1，上山方式只有一种，即，上山方式只有一种，即a11。 若有两个台阶若有两个台阶n=2，可以两小步，可以两小步(每步一个台阶每步一个台阶)上去，也可上去，也可以一大步以一大步(上两个台阶上两个台阶)上去，即上去，即a22。 若有三个台阶若有三个台阶n=3，可以全用小步上去，也可一大一小，或，可以全用小步上去，也可一大一小，或一小一大，因此，一小一大，因此，a33。2.2.3 递推法举例 若有若有n个台阶，上到第个台阶，上到第n个台阶的方式数为个台阶的方式数为an, 可可分成两类，第一类是从第分成两类，第一类是从第n一一1个台阶迈一小步上个台阶迈一小步上去的

11、，共有去的，共有an-1种；第二类是从第种；第二类是从第n-2个台阶迈一个台阶迈一大步上去的，共有大步上去的，共有an-2种。由于最后一步的上法种。由于最后一步的上法不同，所以这两类上法是不同的。所以这样求得不同，所以这两类上法是不同的。所以这样求得的上山方式数为的上山方式数为 an an-1 + an-2 一直算下去，当然可以得到一直算下去，当然可以得到a10a10的值，这就是问题的值，这就是问题的解。的解。 a10=89【例6】阶乘问题 11011nnnaaaa2.2.3 递推法举例【例7】Fibonacci（兔子）序列211011nnnaaaaaFbnc1(n)1 fnf1 f2 12

12、i 22 while(i=n)3 do fn f1+f24 f1 f25 f2 fn 6 return fn【例7】伪代码2.2.4 倒推法举例【例8】猴子吃桃：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第7天时就只有一个桃子了，问原来有多少个桃？1, 4 , 5 , 6 2)1 ( 2)1 (, 2)1 (, 1165767iaaaaaaaii3820a猴子吃桃问题的伪代码Monkey(n)1 an12 for in-1 downto 03 do a(1+an)*24 ana5 return an学习要点学习要点: 理解穷举法的概念。 掌握简单实例的编程。 理解迭代法的概念。 掌握简单实例的编程。第2章 穷举法与迭代法穷举法练习【题目1】将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别取1，6上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。ABCDEF递推法练