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