C语言程序设计基础（通识版 慕课版） 课件 第5章 常用的问题求解策略

第5章常用的问题求解策略哈尔滨工业大学5.1计算机的问题求解与问题求解策略算法设计的基本思路就是寻找解决问题的规律。指在数学思想支持下的解题思路、方式和方法。常用的问题求解策略枚举、递推、迭代、分治、递归5.2枚举穷举法（Exhaustion），也称枚举法（Enumeration）列举所有可能，逐一试探基本思想根据问题的部分已知条件预估解的范围在此范围内对所有可能的情况进行逐一验证若某个情况符合题目的全部条件，则该情况为本问题的一个解若全部情况的验证结果均不符合题目的全部条件，则说明该题无解直到找到满足已知条件的解为止5.2枚举确定穷举对象和穷举范围确定判定条件

符合答案的条件分支结构实现

影响算法的时间复杂度循环结构实现for(穷举范围){……

if(符合答案的条件)……}枚举法求解问题的两个基本要素【例5.1】百鸡问题是我国古代数学名著《张丘建算经》中的一个著名数学问题，它给出了由三个未知量的两个方程组成的不定方程组的解。《张丘建算经》为北魏张丘建所著，所载问题大部分为当时社会生活中的实际问题，如有关测量、纺织、交换、纳税、冶炼、土木工程等，涉及面广泛，其问题和解法均超出《九章算术》。百鸡问题具体是这样的：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？其意为：公鸡每只5元，母鸡每只3元，小鸡3只1元。请用穷举法编程计算，若用100元买100只鸡，则公鸡、母鸡和小鸡各能买多少只。5.2枚举5.2枚举#include<stdio.h>intmain(void){intx,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=%d\n",x,y,z);}}}return0;}5.2枚举#include<stdio.h>intmain(void){intx,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=%d\n",x,y,z);}}return0;}【例5.2】素数判定。所谓素数（PrimeNumber），也称质数，它是不能被1和它本身以外的其他整数整除的正整数。按照这个定义，负数、0和1都不是素数，而7之所以是素数，是因为除了1和7以外，它不能被2～6之间的任何整数整除。请编写一个程序，根据素数的定义，采用枚举法判定用户从键盘任意输入的一个整数是否是素数。若为素数，则输出“Yes”，否则输出“No”。求解算法——试商法用2~x-1之间的整数去试商用2~x/2之间的整数去试商用2~sqrt(x)之间的整数试商负数、0和1都不是素数5.2枚举6.2枚举#include<stdio.h>#include<math.h>#include<stdbool.h>boolIsPrime(intm);intmain(void){intm;scanf("%d",&m);if(IsPrime(m)){printf("Yes\n");}else{printf("No\n");}return0;}//函数功能：判断m是否是素数，若是素数，则返回false，若不是素数，则返回trueboolIsPrime(intm){intsquareRoot=(int)sqrt(m);if(m<=1)returnfalse;//负数、0和1都不是素数

for(inti=2;i<=squareRoot;i++){if(m%i==0)returnfalse;//若能被整除，则不是素数

}

returntrue;}【例5.3】最大公约数。两个正整数的最大公约数（GreatestCommonDivisor，GCD）是能够整除这两个整数的最大整数。从键盘任意输入两个正整数a和b，采用枚举法编程计算并输出这两个正整数的最大公约数。5.2枚举intmain(void){ inta,b; scanf("%d,%d",&a,&b); intc=Gcd(a,b); if(c!=-1) { printf("GreatestCommonDivisorof%dand%dis%d\n",a,b,c); } else { printf("Inputnumbershouldbepositive!\n"); } return0;}intGcd(inta,intb){ if(a<=0||b<=0) { return-1; } intt=a<b?a:b; for(inti=t;i>0;i--) { if(a%i==0&&b%i==0){returni;} } return1;}5.3递推正向顺推，就是从已知条件出发，向着所求问题前进，最后与所求问题联系起来例如，已知一个汉堡包12元，一个蛋挞比一个汉堡包贵5元，问买两种各一个需多少元？首先根据已知条件可以推出一个蛋挞的价格是12+5=17元，然后可以推出买两种各一个需17+12=29。反向逆推，即从所求问题出发，向着已知条件靠拢，最后与已知条件联系起来。例如，小明来到一家早餐店，拿出一半钱吃早餐，又花了3.5元钱买饮料，还剩1元钱，问他原来带了多少钱？这个问题适合使用反向逆推的方法，即从问题的结果出发，一步一步还原出答案。因为我们知道小明现在有1元钱，他做的最后一件事是花3.5元买饮料，所以我们可以把3.5元和他的一元加起来，逆推出他买饮料之前有4.5元，根据已知条件，他花一半钱吃早餐还剩4.5元，那么他吃早餐一定花了4.5元，那么原来他就应该有9元。可递推求解的问题一般具有以下两个特点：（1）问题可以划分成多个状态；（2）除初始状态外，其它各个状态都可以用固定的递推关系式来表示。5.3.1正向顺推实例11

2

3

5

8

......f1

f2f3

f1

f2f3

f1

f2f3

f1

f2f3

f3=f1+f2;f1=f2;f2=f3;11

2

3

5

8

......f1

f2

f1

f2

f1

f2

f1

f1=f1+f2;f2=f2+f1;【例5.4】计算Fibonacci数列的前n项。5.3.1正向顺推实例【例5.4】计算Fibonacci数列的前n项。#include<stdio.h>longFib(intn);intmain(void){inti;longn;printf("Inputn:");scanf("%ld",&n);for(i=1;i<=n;i++){printf("%4ld",Fib(i));}return0;}//函数功能：正向顺推法计算并返回Fibonacci数列的第n项longFib(intn){inti;longf1=1,f2=1,f3=2;if(n==1){return1;}elseif(n==2){return1;}else{for(i=3;i<=n;i++)//每递推一次计算一项

{

f3=f1+f2;f1=f2;f2=f3;}returnf3;}}#include<stdio.h>longFib(intn);intmain(void){inti;longn;printf("Inputn:");scanf("%ld",&n);for(i=1;i<=n;i++){printf("%4ld",Fib(i));}return0;}//函数功能：正向顺推法计算并返回Fibonacci数列的第n项longFib(intn){inti;longf1=1,f2=1;if(n==1){return1;}elseif(n==2){return1;}else{for(i=1;i<(n+1)/2;i++)

{

f1=f1+f2;f2=f2+f1;}returnn%2!=0?f1:f2;}}5.3.1正向顺推实例【例5.4】计算Fibonacci数列的前n项。5.3.2反向逆推实例【例5.5】猴子吃桃问题猴子第一天摘下若干个桃子，吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，并且又多吃了一个。以后每天早上都吃掉前一天剩下的一半零一个。到第10天早上再想吃时，发现只剩下一个桃子。问第一天共摘了多少桃子。每天剩下的桃子数比前一天的一半少一个每天剩下的桃子数加1之后，刚好是前一天的一半天数：

10

9

8

7

6

5

4

3

2

1

4

10

22

46

94

190

382

766

1534

5.3.2反向逆推实例#include<stdio.h>intMonkeyEatPeach(intdayn);intmain(void){intdays,total;printf("Inputdays:");scanf("%d",&days);total=MonkeyEatPeach(days);printf("x=%d\n",total);return0;}intMonkeyEatPeach(intday){intx=1;do{x=(x+1)*2;day--;}while(day>1);returnx;}intMonkeyEatPeach(intday){intx=1;while(day>1){x=(x+1)*2;day--;}returnx;}5.4递归5.4.1递归的内涵与数学基础5.4.2递归函数及其基本要素5.4.3递归的执行过程5.4.4递归与迭代的关系5.4.1递归的内涵与数学基础一种问题求解的策略假设你已经走了999步，那么你再走一步即可迈出第1000步假设你已经走了998步，那么你再走一步即可迈出第999步……直到你迈出第1步，递归结束walkwalk1“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”………….5.4.1递归的内涵与数学基础如果一个对象部分地由它自己组成或按它自己定义，则称它是递归的（Recursive）递归（Recursion）函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象5.4.1递归的内涵与数学基础递归算法必须包含如下两个部分：由其自身定义的与原始问题类似的更小规模的子问题，它使递归过程持续进行，称为一般条件（Generalcase）所描述问题的最简单的情况，它是一个能控制递归过程结束的条件，称为基本条件（Basecase）计算n!问题的一般条件可以用递归公式表示为：n!=n×(n-1)!（当n>1时）计算n!问题的基本条件可以表示为：n!=1（当n=1时）5.4.2递归函数及其基本要素if(递归终止条件)//基本条件，也称边界条件，代表递归的出口return递归公式的初值;else//一般条件，表示递推关系return递归函数调用返回的结果值;

【例5.6】分别用迭代和递归两种方法计算正整数n的阶乘即n!。225.4.2递归函数及其基本要素#include<stdio.h>unsignedintFact(unsignedintn);intmain(void){unsignedintn;printf("Inputn:");scanf("%u",&n);printf("%u!=%u\n",n,Fact(n));return0;}//函数功能：用迭代法计算n的阶乘并返回unsignedintFact(unsignedintn){unsignedinti,p=1; for(i=2;i<=n;i++) { p=p*i; }returnp;}#include<stdio.h>unsignedintFact(unsignedintn);intmain(void){unsignedintn;printf("Inputn:");scanf("%u",&n);printf("%u!=%u\n",n,Fact(n));return0;}//函数功能：用递归法计算n的阶乘并返回unsignedintFact(unsignedintn){if(n==1||n==0)//基本条件

{

return1;}else//一般条件

{

returnn*Fact(n-1);//递归调用

}}#include<stdio.h>intMonkeyEatPeach(intdays);intmain(){ intx,days;printf("Inputdays:"); scanf("%d",&days); x=MonkeyEatPeach(days); printf("x=%d\n",x); return0;}intMonkeyEatPeach(intdays)//由第days天推出第days-1天{if(days==1)//递归结束条件

return1;//递归初值else return2*(MonkeyEatPeach(days-1)+1);//递推式}6.4.2递归函数及其基本要素【例5.7】采用递归法编写求解例6.8的猴子吃桃问题的程序代码5.4.3递归的执行过程递归算法的执行过程一般可分为两个阶段：递推阶段（也称递归前进阶段）把一个较复杂的问题逐步分解为与原始问题类似的更小规模的子问题，逐步简化直至最终转化为一个最简单的问题，可以直接求解并终止递归回归阶段（也称递归返回阶段）当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。5.4.3递归的执行过程栈操作“后进先出”的特点使其能够精确地满足函数调用和返回的顺序，因此特别适合于保存与函数调用相关的信息。保存这些信息的栈空间，称为活跃记录或者栈帧。栈帧中主要存储输入参数、计算表达式时用到的临时变量的值、函数调用时保存的状态信息（如返回地址）等5.4.4递归与迭代的关系递归的本质不断地把规模较大的问题分解成与原来问题相同但规模较小的同类子问题，直到这个小的问题能够直接使用简单的方法解决为止子问题与原问题的区别只是问题的规模不同而已递归和迭代的关系迭代显式地使用重复结构，而递归使用选择结构，通过重复函数调用实现重复结构迭代和递归都涉及终止测试，迭代在循环测试条件为假时终止循环，递归则在遇到基本条件时终止递归。迭代不断修改循环计数变量，直到它使循环条件为假时为止。递归则不断产生最初问题的简化版本，直到简化为递归的基本条件。5.4.4递归与迭代的关系【例5.8】最大公约数。从键盘输入两个正整数a和b，采用欧几里德算法（辗转相除法）编程计算并输出两个正整数a和b的最大公约数。欧几里德算法（辗转相除法）

对正整数a和b，连续进行求余运算

r=a%b直到余数r为0为止

此时非0的除数，即为所求

若r≠0，则b作为新的a，r作为新的b即Gcd(a,b)=Gcd(b,r)重复a%b运算，直到r=0时为止。

//迭代实现intGcd(inta,intb){ intr; if(a<=0||b<=0) { return-1; }

do{ r=a%b; a=b; b=r; }while(r!=0);

returna;}5.4.4递归与迭代的关系【例5.8】最大公约数。从键盘输入两个正整数a和b，采用欧几里德算法（辗转相除法）编程计算并输出两个正整数a和b的最大公约数。欧几里德算法（辗转相除法）

对正整数a和b，连续进行求余运算

r=a%b直到余数r为0为止

此时非0的除数，即为所求

若r≠0，则b作为新的a，r作为新的b即Gcd(a,b)=Gcd(b,r)重复a%b运算，直到r=0时为止。

//递归实现intGcd(inta,intb){ if(a<=0||b<=0) { return-1; }intr=a%b;

if(r==0)returnb;elsereturnGcd(b,r);}5.4.4递归与迭代的关系【例5.9】利用如下递归公式，用递归法编程计算并输出Fibonacci数列的前n项。//函数功能：用递归法计算Fibonacci数列中的第n项的值longFib(intn){if(n==1||n==2)//基本条件

{return1;}else//一般情况

{return(Fib(n-1)+Fib(n-2));//递归调用

}}5.4.4递归与迭代的关系【例5.9】利用如下递归公式，用递归法编程计算并输出Fibonacci数列的前n项。intcount;//全局变量，自动初始化为0longFib(intn){

count++;if(n==1)//基本条件

{return1;}elseif(n==2)//基本条件

{return1;}else//一般情况

{return(Fib(n-1)+Fib(n-2));}}如果我们想知道计算Fibonacci数列的每一项所需的递归调用次数，那么应该如何修改程序呢？计算Fibonacci数列第n项5.4.4递归与迭代的关系建议：对时空效率要求高的场合，用迭代递推代替递归实现优点：简洁、直观、精炼缺点：重复计算多，递归层数过深时函数调用开销大，时空效率低，易导致栈溢出intcount;//全局变量，自动初始化为0longFib(intn){

count++;if(n==1)//基本条件

{return1;}elseif(n==2)//基本条件

{return1;}else//一般情况

{return(Fib(n-1)+Fib(n-2));}}5.4.4递归与迭代的关系什么情况下考虑使用递归？数学定义是递归的数据结构是递归的如队列、链表、树和图问题的解法是递归的如Hanoi塔，骑士游历、八皇后问题（回溯法）汉诺塔（Hanoi）问题假设有三根柱子，第一根上从下往上按大小顺序摞着64片黄金圆盘，要求把圆盘从下开始按大小顺序重新摆放到第二根上，规定每次只能移动一个圆盘，在小圆盘上不能放大圆盘。请编写一个程序，求解n（n>1）个圆盘的汉诺塔问题5.4.4递归与迭代的关系将“上面n-1个圆盘”从A移到C将第n号圆盘从A移到B将“上面n-1个圆盘”从C移到B数学归纳法假设n-1个圆盘的汉诺塔问题已解决将“上面n-1个圆盘”看成一个整体移动n个圆盘移动n