1、第第6章章 程序设计的问题求解基础程序设计的问题求解基础哈尔滨工业大学哈尔滨工业大学6.1问题求解策略问题求解策略n算法设计的基本思路就是寻找解决问题的规律。算法设计的基本思路就是寻找解决问题的规律。n指在数学思想支持下的解题思路、方式和方法。指在数学思想支持下的解题思路、方式和方法。n常用的问题求解策略常用的问题求解策略枚举、递推、迭代、分治、递归枚举、递推、迭代、分治、递归6.2枚举枚举从找回你的密码谈起从找回你的密码谈起n穷举法（穷举法（Exhaustion），也称枚举法（），也称枚举法（Enumeration）列举所有可能列举所有可能，逐一试探，逐一试探n基本思想基本思想根据问题的根据
2、问题的部分部分已知已知条件预估解的范围条件预估解的范围在此范围内对所有可能的情况进行逐一验证在此范围内对所有可能的情况进行逐一验证若某个情况符合题目的全部条件，则该情况为本问题的一个解若某个情况符合题目的全部条件，则该情况为本问题的一个解若全部情况的验证结果均不符合题目的全部条件，则说明该题无解若全部情况的验证结果均不符合题目的全部条件，则说明该题无解直到直到找到满足已知条件的解找到满足已知条件的解为止为止6.2枚举枚举从找回你的密码谈起从找回你的密码谈起确定穷举对象确定穷举对象和穷举范围和穷举范围确定确定判定条件判定条件l 符合答案的条件符合答案的条件l 分支结构实现分支结构实现l 影响算法
3、的时间复杂度影响算法的时间复杂度l 循环结构实现循环结构实现for(穷举范围穷举范围)if(符合答案的条件符合答案的条件)枚举法求解问题的两个基本要素枚举法求解问题的两个基本要素【例6.1】百鸡问题是我国古代数学名著张丘建算经中的一个著名数学问题，它给出了由三个未知量的两个方程组成的不定方程组的解。张丘建算经为北魏张丘建所著，所载问题大部分为当时社会生活中的实际问题，如有关测量、纺织、交换、纳税、冶炼、土木工程等，涉及面广泛，其问题和解法均超出九章算术。百鸡问题具体是这样的：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？其意为：公鸡每只5元，母鸡每只3元，小
4、鸡3只1元。请用穷举法编程计算，若用100元买100只鸡，则公鸡、母鸡和小鸡各能买多少只。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include int main(void)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.0=100)printf(x=%d,y=%d,z=%dn,x,y,z);return 0;6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include int main(void)int
5、 x,y,z;for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;if(5*x+3*y+z/3.0=100)printf(x=%d,y=%d,z=%dn,x,y,z);return 0;n【例例6.3】韩信点兵问题。西汉开国功臣、军事家韩信有一队兵，他想知道有韩信点兵问题。西汉开国功臣、军事家韩信有一队兵，他想知道有士兵多少人，便让士兵排队报数。按从士兵多少人，便让士兵排队报数。按从1至至5报数，最末一个士兵报的数为报数，最末一个士兵报的数为1；按从按从1至至6报数，最末一个士兵报的数为报数，最末一个士兵报的数为5；按从；按从1至至7报数，最末一个士兵报报数，最
6、末一个士兵报的数为的数为4；最后再按从；最后再按从1至至11报数，最末一个士兵报的数为报数，最末一个士兵报的数为10。请问韩信至少。请问韩信至少有多少兵。确定问题的输入和输出有多少兵。确定问题的输入和输出输入：无；输出：士兵至少输入：无；输出：士兵至少x人人n确定穷举对象：士兵数确定穷举对象：士兵数xn确定搜索范围：确定搜索范围：x从从1变化变化n确定判定条件：确定判定条件：x被被5、6、7、11整除余数为整除余数为1、5、4、10nx%5=1&x%6=5&x%7=4&x%11=106.2枚举枚举从找回你的密码谈起从找回你的密码谈起6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#inclu
7、de int main(void)int x;for(x=1;x3000;x+)if(x%5=1&x%6=5&x%7=4&x%11=10)printf(x=%dn,x);return 0;#include int main(void)int x;for(x=1;x+)if(x%5=1&x%6=5&x%7=4&x%11=10)printf(x=%dn,x);break;return 0;6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include#include int main(void)int x;for(x=1;x+)if(x%5=1&x%6=5&x%7=4&x%11=10)prin
8、tf(x=%dn,x);exit(0);return 0;#include int main(void)int x;int find=0;/置找到标志变量为假置找到标志变量为假 for(x=1;!find;x+)/find为假时继续循环为假时继续循环 if(x%5=1&x%6=5&x%7=4&x%11=10)printf(x=%dn,x);find=1;/置找到标志变量为真置找到标志变量为真 return 0;6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include int main(void)int x=0;int find=0;do x+;find=(x%5=1&x%6=5&x%
9、7=4&x%11=10);while(!find);printf(x=%dn,x);return 0;#include int main(void)int x=0;/因因do-while循环中先对循环中先对x加加1，故这里，故这里x初始化为初始化为0 do x+;while(!(x%5=1&x%6=5&x%7=4&x%11=10);printf(x=%dn,x);return 0;n【例例6.4】还原算术表达式。请编写一个程序求解以下算式中各还原算术表达式。请编写一个程序求解以下算式中各字母所代表的数字的值，已知不同的字母代表不同的数字。先字母所代表的数字的值，已知不同的字母代表不同的数字。先
10、从键盘输入小于从键盘输入小于1000的的n值，如果值，如果n不小于不小于1000，则重新输入，则重新输入n值，然后输出第一个满足条件的解。值，然后输出第一个满足条件的解。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include int main(void)int x,y,z,n,find=0;do printf(Input n(n=1000);/若输入的若输入的n不在合法范围内，则重新输入不在合法范围内，则重新输入 for(x=1;x=9;+x)for(y=1;y=9;+y)for(z=0;z=9;+z)if(100*x+10*y+z+z+10*z+100*y=n&x!=y&y!=z
11、&x!=z)printf(X=%d,Y=%d,Z=%dn,x,y,z);find=1;if(!find)printf(Not found!);return 0;n【例例6.4】还原算术表达式。请编写一个程序求解以下算式中各还原算术表达式。请编写一个程序求解以下算式中各字母所代表的数字的值，已知不同的字母代表不同的数字。先字母所代表的数字的值，已知不同的字母代表不同的数字。先从键盘输入小于从键盘输入小于1000的的n值，如果值，如果n不小于不小于1000，则重新输入，则重新输入n值，然后输出第一个满足条件的解。值，然后输出第一个满足条件的解。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#i
12、nclude int main(void)for(x=1;x=9&!find;+x)for(y=1;y=9&!find;+y)if(x=y)continue;/若若y与与x相等，就直接换下一个相等，就直接换下一个y再试再试 for(z=0;z=9&!find;+z)if(y=z|x=z)continue;/若若z与与x或或y相等，就换下一个相等，就换下一个z if(100*x+10*y+z+z+10*z+100*y=n)printf(X=%d,Y=%d,Z=%dn,x,y,z);find=1;count+;printf(Not found!);return 0;n【例例6.4】还原算术表达式。
13、请编写一个程序求解以下算式中各还原算术表达式。请编写一个程序求解以下算式中各字母所代表的数字的值，已知不同的字母代表不同的数字。先字母所代表的数字的值，已知不同的字母代表不同的数字。先从键盘输入小于从键盘输入小于1000的的n值，如果值，如果n不小于不小于1000，则重新输入，则重新输入n值，然后输出第一个满足条件的解。值，然后输出第一个满足条件的解。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include int main(void)for(x=1;x=9;+x)for(y=1;y=9;+y)if(x=y)continue;for(z=0;z=9;+z)if(y=z|x=z)con
14、tinue;count+;if(100*x+10*y+z+z+10*z+100*y=n)printf(X=%d,Y=%d,Z=%dn,x,y,z);find=1;goto END;if(!find)printf(Not found!);END:printf(count=%dn,count);return 0;n【例例6.5】请编写一个程序，计算并输出请编写一个程序，计算并输出1n之间的所有素数之和。之间的所有素数之和。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起int IsPrime(int m)int i;int squareRoot=(int)sqrt(m);if(m=1)retur
15、n 0;/负数、负数、0和和1都不是素数都不是素数 for(i=2;i=squareRoot;+i)if(m%i=0)goto END;END:return i=squareRoot?0:1;int IsPrime(int m)int i;int squareRoot=(int)sqrt(m);if(m=1)return 0;/负数、负数、0和和1都不是素数都不是素数 for(i=2;i=squareRoot;+i)if(m%i=0)break;return i=squareRoot?0:1;n【例例6.5】请编写一个程序，计算并输出请编写一个程序，计算并输出1n之间的所有素数之和。之间的所有
16、素数之和。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起int IsPrime(int m)int flag=1;int squareRoot=(int)sqrt(m);if(m=1)flag=0;/负数、负数、0和和1都不是素数都不是素数 for(int i=2;i=squareRoot&flag;+i)if(m%i=0)flag=0;/若能被整除，则不是素数若能被整除，则不是素数 return flag;#include bool IsPrime(int m)bool flag=true;int squareRoot=(int)sqrt(m);if(m=1)flag=false;/负数
17、、负数、0和和1都不是素数都不是素数 for(int i=2;i=squareRoot&flag;+i)if(m%i=0)flag=false;/若能被整除，则不是素数若能被整除，则不是素数 return flag;int main(void)int n;scanf(%d,&n);printf(sum=%dn,SumofPrime(n);return 0;【例例6.66.6】德国人哥德巴赫在德国人哥德巴赫在17421742年提出了自己无法证明的两个猜想：（年提出了自己无法证明的两个猜想：（1 1）每个大于）每个大于2 2的偶数都的偶数都是两个素数之和；（是两个素数之和；（2 2）每个大于）每个
18、大于5 5的奇数都是三个素数之和。的奇数都是三个素数之和。19731973年，我国数学家陈景润攻克了年，我国数学家陈景润攻克了数学界数学界200200多年悬而未决的世界级数学难题即多年悬而未决的世界级数学难题即“哥德巴赫猜想哥德巴赫猜想”中的中的“1 12”2”，成为哥德巴赫猜，成为哥德巴赫猜想研究史上的里程碑。他的论文发表后立即在国际数学界引起了轰动，被公认为是对哥德巴赫猜想研究史上的里程碑。他的论文发表后立即在国际数学界引起了轰动，被公认为是对哥德巴赫猜想研究的重大贡献。他的成果被国际数学界称为想研究的重大贡献。他的成果被国际数学界称为“陈氏定理陈氏定理”，写进美、英、法、苏、日等六国，写
19、进美、英、法、苏、日等六国的许多数论书中。的许多数论书中。20092009年，陈景润被评为年，陈景润被评为100100位新中国成立以来感动中国人物之一。位新中国成立以来感动中国人物之一。现在，请你编写一个程序来验证：任何一个大于或等于现在，请你编写一个程序来验证：任何一个大于或等于6 6但不超过但不超过20000000002000000000的足够大的偶数的足够大的偶数n n总总能表示为两个素数之和。例如，能表示为两个素数之和。例如，8=3+58=3+5，12=5+712=5+7等等。如果等等。如果n n符合符合“哥德巴赫猜想哥德巴赫猜想”，则输出将，则输出将n n分解为两个素数之和的等式，否
20、则输出分解为两个素数之和的等式，否则输出“n n不符合哥德巴赫猜想！不符合哥德巴赫猜想！”的提示信息。的提示信息。他曾经说过：时间是个常数，花掉一天等于浪费24小时；学习要有三心：信心、决心、恒心；攀登科学高峰，就像登山运动员攀登珠穆朗玛峰一样，要克服无数艰难险阻，懦夫和懒汉是不可能享受到胜利的喜悦和幸福的。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起n【例例6.5】请编写一个程序，计算并输出请编写一个程序，计算并输出1n之间的所有素数之和。之间的所有素数之和。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起#include#include#include bool IsPrime(l
21、ong m);bool Goldbach(long n);int main(void)long n;int ret;do printf(Input n:);ret=scanf(%ld,&n);if(ret!=1)while(getchar()!=n);while(ret!=1|n%2!=0|n2000000000);if(!Goldbach(n)printf(%ld不符合哥德巴赫猜想不符合哥德巴赫猜想n,n);return 0;n【例例6.5】请编写一个程序，计算并输出请编写一个程序，计算并输出1n之间的所有素数之和。之间的所有素数之和。6.2枚举枚举从找回你的密码谈起从找回你的密码谈起boo
22、l Goldbach(long n)bool find=false;for(long a=3;a=n/2&!find;a+=2)if(IsPrime(a)&IsPrime(n-a)printf(%ld=%ld+%ld,n,a,n-a);find=true;return find;bool IsPrime(long m)bool flag=true;int squareRoot=(int)sqrt(m);if(m=1)flag=false;/负数、负数、0和和1都不是素数都不是素数 for(int i=2;i=squareRoot&flag;+i)if(m%i=0)flag=false;/若能被
23、整除，则不是素数若能被整除，则不是素数 return flag;6.4 递推递推荷花定律和大自然中的秘密荷花定律和大自然中的秘密n在一个荷花池里，第一天荷花开放的很少，第二天在一个荷花池里，第一天荷花开放的很少，第二天开放的数量是第一天的两倍，之后的每一天，荷花开放的数量是第一天的两倍，之后的每一天，荷花都会以前一天两倍的数量开放。如果到第都会以前一天两倍的数量开放。如果到第30天，荷天，荷花就开满了整个池塘，那么请问荷花是在第几天开花就开满了整个池塘，那么请问荷花是在第几天开了半个池塘呢？了半个池塘呢？n向日葵的花盘中有向日葵的花盘中有2组对数螺线，一组顺时针方向盘组对数螺线，一组顺时针方向
24、盘绕，另一组则逆时针方向盘绕，并且彼此相嵌。虽绕，另一组则逆时针方向盘绕，并且彼此相嵌。虽然不同的向日葵品种中，这些顺逆螺旋的数目并不然不同的向日葵品种中，这些顺逆螺旋的数目并不固定，但往往不会超出固定，但往往不会超出34和和55、55和和89、89和和144这三组数字。除了向日葵，松果也符合这一奇妙的这三组数字。除了向日葵，松果也符合这一奇妙的自然规律自然规律植物的花瓣、萼片、果实的数目以及其他方面的特征，都非常吻合一个奇特的数列，即Fibonacci数列：1，1，2，3，5，8，13，21，34，55，89.。这个数列从第三项开始，每一项都是前两项之和6.4 递推递推荷花定律和大自然中的秘
25、密荷花定律和大自然中的秘密n正向顺推，就是从已知条件出发，向着所求问题前进，最后与所求问题联系起来正向顺推，就是从已知条件出发，向着所求问题前进，最后与所求问题联系起来例如，已知一个汉堡包例如，已知一个汉堡包12元，一个蛋挞比一个汉堡包贵元，一个蛋挞比一个汉堡包贵5元，问买两种各一个需多少元？首先根据元，问买两种各一个需多少元？首先根据已知条件可以推出一个蛋挞的价格是已知条件可以推出一个蛋挞的价格是12+5=17元，然后可以推出买两种各一个需元，然后可以推出买两种各一个需17+12=29。n反向逆推，即从所求问题出发，向着已知条件靠拢，最后与已知条件联系起来。反向逆推，即从所求问题出发，向着已
26、知条件靠拢，最后与已知条件联系起来。例如，小明来到一家早餐店，拿出一半钱吃早餐，又花了例如，小明来到一家早餐店，拿出一半钱吃早餐，又花了3.5元钱买饮料，还剩元钱买饮料，还剩1元钱，问他原来元钱，问他原来带了多少钱？这个问题适合使用反向逆推的方法，即从问题的结果出发，一步一步还原出答案。带了多少钱？这个问题适合使用反向逆推的方法，即从问题的结果出发，一步一步还原出答案。因为我们知道小明现在有因为我们知道小明现在有1元钱，他做的最后一件事是花元钱，他做的最后一件事是花3.5元买饮料，所以我们可以把元买饮料，所以我们可以把3.5元和他元和他的一元加起来，逆推出他买饮料之前有的一元加起来，逆推出他买
27、饮料之前有4.5元，根据已知条件，他花一半钱吃早餐还剩元，根据已知条件，他花一半钱吃早餐还剩4.5元，那元，那么他吃早餐一定花了么他吃早餐一定花了4.5元，那么原来他就应该有元，那么原来他就应该有9元。元。n可递推求解的问题一般具有以下两个特点：可递推求解的问题一般具有以下两个特点：（1）问题可以划分成多个状态；）问题可以划分成多个状态；（2）除初始状态外，其它各个状态都可以用固定的递推关系式来表示。）除初始状态外，其它各个状态都可以用固定的递推关系式来表示。6.4.1正向顺推实例正向顺推实例1 1 2 3 5 8 .f1 f2 f3 f1 f2 f3 f1 f2 f3 f1 f2 f3 f3
28、=f1+f2;f1=f2;f2=f3;1 1 2 3 5 8 .f1 f2 f1 f2 f1 f2 f1 f1=f1+f2;f2=f2+f1;【例例6.7】计算计算Fibonacci数列的前数列的前n项。项。6.4.1正向顺推实例正向顺推实例【例例6.7】计算计算Fibonacci数列的前数列的前n项。项。#include long Fib(int n);int main(void)int i;long n;printf(Input n:);scanf(%ld,&n);for(i=1;i=n;i+)printf(%4ld,Fib(i);return 0;/函数功能：正向顺推法计算并返回函数功能
29、：正向顺推法计算并返回Fibonacci数列的第数列的第n项项long Fib(int n)int i;long f1=1,f2=1,f3=2;if(n=1)return 1;else if(n=2)return 1;else for(i=3;i=n;i+)/每递推一次计算一项每递推一次计算一项 f3=f1+f2;f1=f2;f2=f3;return f3;6.4.1正向顺推实例正向顺推实例【例例6.7】计算计算Fibonacci数列的前数列的前n项。项。#include long Fib(int n);int main(void)int i;long n;printf(Input n:);s
30、canf(%ld,&n);for(i=1;i=n;i+)printf(%4ld,Fib(i);return 0;/函数功能：正向顺推法计算并返回函数功能：正向顺推法计算并返回Fibonacci数列的第数列的第n项项long Fib(int n)int i;long f1=1,f2=1;if(n=1)return 1;else if(n=2)return 1;else for(i=1;i(n+1)/2;i+)f1=f1+f2;f2=f2+f1;return n%2!=0?f1:f2;6.4.2反向逆推实例反向逆推实例n【例【例6.8】猴子吃桃问题猴子吃桃问题猴子第一天摘下若干个桃子，吃了一半，还
31、不过瘾，又多吃了一个。第二天猴子第一天摘下若干个桃子，吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子早上又将剩下的桃子吃掉一半，并且又多吃了一个吃掉一半，并且又多吃了一个。以后每天早上都。以后每天早上都吃掉前吃掉前一天剩下的一半零一个一天剩下的一半零一个。到第。到第10天早上再想吃时，发现只剩下一个桃子。问天早上再想吃时，发现只剩下一个桃子。问第一天共摘了多少桃子。第一天共摘了多少桃子。每天每天剩下的桃子数剩下的桃子数比前一天的一半少一个比前一天的一半少一个每天剩下的桃子数加每天剩下的桃子数加1之之后后，刚好是前一天的一半刚好是前一天的一半天数：10 9 8 7 6 5 4 3 2
32、 1 4 10 22 46 94 190 382 766 1534 101)1(21011nxxnxnnn6.4.2反向逆推实例反向逆推实例#include int MonkeyEatPeach(int dayn);int main(void)int days,total;printf(Input days:);scanf(%d,&days);total=MonkeyEatPeach(days);printf(x=%dn,total);return 0;int MonkeyEatPeach(int day)int x=1;do x=(x+1)*2;day-;while(day 1);retur
33、n x;int MonkeyEatPeach(int day)int x=1;while(day 1)x=(x+1)*2;day-;return x;6.5 递归递归千里之行始于足下的启示千里之行始于足下的启示6.5.1 递归的内涵与数学基础递归的内涵与数学基础n一种问题求解的策略一种问题求解的策略假设你已经走了假设你已经走了999步，那么你再走一步即可迈出第步，那么你再走一步即可迈出第1000步步假设你已经走了假设你已经走了998步，那么你再走一步即可迈出第步，那么你再走一步即可迈出第999步步直到你迈出第直到你迈出第1步，递归结束步，递归结束)1()1(2)1(age10)(agennnn
34、walkwalk1“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”.6.5.1 递归的内涵与数学基础递归的内涵与数学基础n如果一个对象部分地由它自己组成或按它自己定义，如果一个对象部分地由它自己组成或按它自己定义，则称它是则称它是递归的（递归的（Recursive）n递归（递归（Recursion）函数函数/过程过程/子程序在运行过程中直接或间接调用自身而产生子程序在运行过程中直接或间接调用自身而产生的重入现象的重入现象6.5.1 递归的内
35、涵与数学基础递归的内涵与数学基础n递归算法必须包含如下两个部分：递归算法必须包含如下两个部分：由其自身定义的与原始问题类似的更小规模的子问题，它使递归由其自身定义的与原始问题类似的更小规模的子问题，它使递归过程持续进行，称为过程持续进行，称为一般条件（一般条件（General case）所描述问题的最简单的情况，它是一个能控制递归过程结束的条所描述问题的最简单的情况，它是一个能控制递归过程结束的条件，称为件，称为基本条件（基本条件（Base case）计算n!问题的一般条件可以用递归公式表示为：n!=n(n-1)!（当n1时）计算n!问题的基本条件可以表示为：n!=1 （当n=1时）6.4.2
36、递归函数的基本要素递归函数的基本要素if(递归终止条件递归终止条件)/基本条件，也称边界条件，代表递归的出口基本条件，也称边界条件，代表递归的出口 return 递归公式的初值递归公式的初值;else /一般条件，表示递推关系一般条件，表示递推关系 return 递归函数调用返回的结果值递归函数调用返回的结果值;n【例【例6.9】分别用迭代和递归两种方法计算正整数】分别用迭代和递归两种方法计算正整数n的阶乘即的阶乘即n!。326.4.2递归函数的基本要素递归函数的基本要素#includeunsigned int Fact(unsigned int n);int main(void)unsign
37、ed int n;printf(Input n:);scanf(%u,&n);printf(%u!=%un,n,Fact(n);return 0;/函数功能：用迭代法计算函数功能：用迭代法计算n的阶乘并返回的阶乘并返回unsigned int Fact(unsigned int n)unsigned int i,p=1;for(i=2;i=n;i+)p=p*i;return p;#includeunsigned int Fact(unsigned int n);int main(void)unsigned int n;printf(Input n:);scanf(%u,&n);printf(%
38、u!=%un,n,Fact(n);return 0;/函数功能：用递归法计算函数功能：用递归法计算n的阶乘并返回的阶乘并返回unsigned int Fact(unsigned int n)if(n=1|n=0)/基本条件基本条件 return 1;else/一般条件一般条件 return n*Fact(n-1);/递归调用递归调用#include int MonkeyEatPeach(int days);int main()int x,days;printf(Input days:);scanf(%d,&days);x=MonkeyEatPeach(days);printf(x=%dn,x)
39、;return 0;int MonkeyEatPeach(int days)/由第由第days天推出第天推出第days-1天天 if(days=1)/递归结束条件递归结束条件 return 1;/递归初值递归初值 else return 2*(MonkeyEatPeach(days-1)+1);/递推式递推式 6.4.2递归函数的基本要素递归函数的基本要素101)1(21011nxxnxnnnn【例【例6.10】采用递归法编写求解例采用递归法编写求解例6.8的猴子吃桃问题的程序代码的猴子吃桃问题的程序代码6.5.3 递归的执行过程递归的执行过程n递归算法的执行过程一般可分为两个阶段：递归算法的
40、执行过程一般可分为两个阶段：递推阶段（也称递归前进阶段）递推阶段（也称递归前进阶段）把一个较复杂的问题逐步分解为与原始问题类似的更小规模的子问题，逐步简化直至最终转把一个较复杂的问题逐步分解为与原始问题类似的更小规模的子问题，逐步简化直至最终转化为一个最简单的问题，可以直接求解并终止递归化为一个最简单的问题，可以直接求解并终止递归回归阶段（也称递归返回阶段）回归阶段（也称递归返回阶段）当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。6.5.3 递归的执行过程递归的执行过程n栈操作栈操作“后进先出后进先出”的特点使其能够精确地满
41、足函数调用和返回的顺序，因此特的特点使其能够精确地满足函数调用和返回的顺序，因此特别适合于保存与函数调用相关的信息。保存这些信息的栈空间，称为活跃记录或别适合于保存与函数调用相关的信息。保存这些信息的栈空间，称为活跃记录或者栈帧。者栈帧。n栈帧中主要存储输入参数、计算表达式时用到的临时变量的值、函数调用时保存的状态信栈帧中主要存储输入参数、计算表达式时用到的临时变量的值、函数调用时保存的状态信息（如返回地址）等息（如返回地址）等6.5.4 递归与迭代的关系递归与迭代的关系n递归的本质递归的本质不断地把规模较大的问题分解成与原来问题相同但规模较小的同类子问题，不断地把规模较大的问题分解成与原来问
42、题相同但规模较小的同类子问题，直到这个小的问题能够直接使用简单的方法解决为止直到这个小的问题能够直接使用简单的方法解决为止子问题与原问题的区别只是问题的规模不同而已子问题与原问题的区别只是问题的规模不同而已n递归和迭代的关系递归和迭代的关系迭代显式地使用重复结构，而递归使用选择结构，通过重复函数调用实现重迭代显式地使用重复结构，而递归使用选择结构，通过重复函数调用实现重复结构复结构迭代和递归都涉及终止测试，迭代在循环测试条件为假时终止循环，递归则迭代和递归都涉及终止测试，迭代在循环测试条件为假时终止循环，递归则在遇到基本条件时终止递归。在遇到基本条件时终止递归。迭代不断修改循环计数变量，直到它
43、使循环条件为假时为止。递归则不断产迭代不断修改循环计数变量，直到它使循环条件为假时为止。递归则不断产生最初问题的简化版本，直到简化为递归的基本条件。生最初问题的简化版本，直到简化为递归的基本条件。6.5.4 递归与迭代的关系递归与迭代的关系n【例例6.11】最大公约数问题。两个正整数的最大公约数（最大公约数问题。两个正整数的最大公约数（Greatest Common Divisor，GCD）是能够整除这两个整数的最大整数。从键盘任意输入两个正整）是能够整除这两个整数的最大整数。从键盘任意输入两个正整数数a和和b，请分别采用枚举法、欧几里德算法（辗转相除法）以及更相减损术三种，请分别采用枚举法、
44、欧几里德算法（辗转相除法）以及更相减损术三种不同的方法编程计算并输出两个正整数不同的方法编程计算并输出两个正整数a和和b的最大公约数。的最大公约数。（1）穷举法）穷举法 int Gcd(int a,int b)int i,t;if(a=0|b=0)return-1;t=a 0;i-)if(a%i=0&b%i=0)return i;return 1;6.5.4 递归与迭代的关系递归与迭代的关系（2）欧几里德算法（辗转相除法）欧几里德算法（辗转相除法）对正整数对正整数a和和b，连续进行求余运算，连续进行求余运算 r=a%b 直到余数直到余数r r为为0为止为止 此时非此时非0的除数，即为所求的除数
45、，即为所求 若若r0，则，则b作为新的作为新的a，r作为新的作为新的b 即即Gcd(a,b)=Gcd(b,r)重复重复a%b运算，直到运算，直到r=0时为止。时为止。int Gcd(int a,int b)int r;if(a=0|b=0)return-1;dor=a%b;a=b;b=r;while(r!=0);return a;6.5.4 递归与迭代的关系递归与迭代的关系辗转相除法的递归实现辗转相除法的递归实现 int Gcd(int a,int b)if(a=0|b b，则，则Gcd(a,b)=Gcd(a-b,b)性质性质2 如果如果ba，则，则Gcd(a,b)=Gcd(a,b-a)性质性
46、质3 如果如果a=b，则，则Gcd(a,b)=a=b int Gcd(int a,int b)if(a=0|b b)return Gcd(a-b,b);else return Gcd(a,b-a);九章算术九章算术是我国古代的数学专著，值得是我国古代的数学专著，值得我们后人为之骄傲和自豪的是，作为一部世我们后人为之骄傲和自豪的是，作为一部世界数学名著，界数学名著，九章算术九章算术早在隋唐时期即早在隋唐时期即已传入朝鲜、日本。它已被译成日、俄、德已传入朝鲜、日本。它已被译成日、俄、德、法等多种文字版本。、法等多种文字版本。九章算术九章算术是算经是算经十书中最重要的一种，该书系统地总结了战十书中最
47、重要的一种，该书系统地总结了战国、秦、汉时期的数学成就，是当时世界上国、秦、汉时期的数学成就，是当时世界上最简练有效的应用数学，它的出现标志中国最简练有效的应用数学，它的出现标志中国古代数学形成了完整的体系。更相减损术就古代数学形成了完整的体系。更相减损术就是是九章算术九章算术中记载的一种求最大公约数中记载的一种求最大公约数的方法，其主要思想是的方法，其主要思想是6.5.4 递归与迭代的关系递归与迭代的关系更相减损术更相减损术迭代方法迭代方法 int Gcd(int a,int b)if(a=0|b b)a=a-b;else if(b a)b=b-a;return a;6.5.4 递归与迭代的
48、关系递归与迭代的关系n【例例6.12】利用如下递归公式，用递归法编程计算并输出利用如下递归公式，用递归法编程计算并输出Fibonacci数列的前数列的前n项。项。long Fib(int n)if(n=1)/基本条件基本条件 return 1;else if(n=2)/基本条件基本条件 return 1;else /一般情况一般情况 return(Fib(n-1)+Fib(n-2);6.5.4 递归与迭代的关系递归与迭代的关系n【例例6.12】利用如下递归公式，用递归法编程计算并输出利用如下递归公式，用递归法编程计算并输出Fibonacci数列的前数列的前n项。项。int count;/全局变
49、量，自动初始化为全局变量，自动初始化为0long Fib(int n)count+;if(n=1)/基本条件基本条件 return 1;else if(n=2)/基本条件基本条件 return 1;else /一般情况一般情况 return(Fib(n-1)+Fib(n-2);如果我们想知道计算如果我们想知道计算Fibonacci数列的每一数列的每一项所需的递归调用次数项所需的递归调用次数，那么应该如何修改程，那么应该如何修改程序呢？序呢？n计算计算Fibonacci数列数列第第n项项6.5.4 递归与迭代的关系递归与迭代的关系n建议：对时空效率要求高的场合，建议：对时空效率要求高的场合，用迭
50、代递推代替递归实现用迭代递推代替递归实现n优点优点：简洁、直观、精炼简洁、直观、精炼n缺点：缺点：n重复计算多，递归层数过深时函数调用重复计算多，递归层数过深时函数调用开销大，时空效率低，易导致栈溢出开销大，时空效率低，易导致栈溢出int count;/全局变量，自动初始化为全局变量，自动初始化为0long Fib(int n)count+;if(n=1)/基本条件基本条件 return 1;else if(n=2)/基本条件基本条件 return 1;else /一般情况一般情况 return(Fib(n-1)+Fib(n-2);6.5.4 递归与迭代的关系递归与迭代的关系n什么情况下考虑使
