基本程序设计技术.ppt

《基本程序设计技术.ppt》由会员分享，可在线阅读，更多相关《基本程序设计技术.ppt（44页珍藏版）》请在课桌文档上搜索。

1、1,高级语言程序设计,2,第四章基本程序设计技术,3,主要内容：基本程序设计技术,循环程序设计循环与递归基本输入输出控制结构和控制语句程序设计实例程序测试和排错,递归与循环递归函数的执行过程递归函数效率,4,重复性计算可用循环结构完成;有些重复性计算，C中可用递归完成;,例：定义计算整数阶乘的函数：12(n-1)n乘的次数依赖于n，定义时不知道，每次用可能不同。,程序的典型情况：计算“次数”依赖某些参数的值。,4.2循环与递归,5,计算整数阶乘的递推函数,long fact(long n)long i,f=1;for(i=2;i=n;+i)f*=i;return f;,类型特征可定为：int

2、fact(int)阶乘值增长极快（数学），更合适的类型特征：long fact(long),6,1.关于递归定义如果问题本身能用数学递归描述，可用递归定义解决;C允许递归定义：在函数定义内调用被定义函数本身。,求阶乘的数学递归定义公式,7,嵌套调用C规定：函数定义不可嵌套，但可以嵌套调用函数,函数的嵌套与递归调用,8,定义：函数直接或间接的调用自身叫函数的递归调用,说明C编译系统对递归函数的自调用次数没有限制每调用函数一次，在内存堆栈区分配空间，用于存放函数变量、返回值等信息，所以递归次数过多，可能引起堆栈溢出,int f(int x)int y,z;z=f(y);.return(2*z);,

3、递归调用,9,构成递归需具备的条件,子问题须与原始问题为同样的事，且更为简单；不能无限制地调用本身，必须有个出口，化简为非递归状况处理。,10,long fact(long n)return n=0?1:n*fact(n-1);,long fact(long n)long i,f=1;if(n=0)f=1;else f=n*fact(n 1);return f;,求阶乘的递归函数定义1：,求阶乘的递归函数定义2:,递归如何实现?,11,计算中fact被递归调用的次数由实参确定。,考虑负参数值处理。可改为：n=1?1:.,long fact(long n)long i,f;if(n=0)f=1;

4、else f=n*fact(n-1);return f;,12,long fact(1)if(1=1)return 1;return 1*fact(1-1);,long fact(2)if(2=1)return 1;return 2*fact(2-1);,long fact(3)if(3=1)return 1;return 3*fact(3-1);,main()printf(“%d”,fact(3);,蓝线：函数调用线路绿线：函数内部执行路线红线：函数执行结束返回主调函数的路线,long fact(long n)if(n=1)return 1;return n*fact(n-1);,13,例1

5、 阅读源程序,写出运行结果。,#includelong f(int n)long s;if(n=1)|(n=2)s=2;else s=n+f(n 1);return s;,int main()long x;x=f(4);printf(“%ldn”,x);return 0;,结果：9,14,2.递归与计算过程,包含递归的程序产生的计算过程和性质复杂，能完成很复杂的工作。递归调用只有一个调用表达式或语句，但是可能要许多步才能完成。实际参数的不同，会实际产生的递归调用次数（步数）也会有很大的不同。递归程序的理解比较困难递归的函数定义需要有条件语句去控制递归过程的最终结束直接给出结果的时候，递归结束；

6、把对较复杂情况的计算归结为对更简单情况的计算，需要进行递归处理。基本运算、关系判断、条件表达式，加函数定义和递归定义构成了一个（理论上）“足够强的”的程序语言。,15,Fibonacci（斐波那契）序列的递归定义：求第n项Fn,#includelong fib(int);int main()long f;int n=40;f=fib(n);printf(n=%d,f=%ldn,n,f);return 1;long fib(int n)return n2?1:fib(n-1)+fib(n-2);,问题分析：研究程序的执行过程,例：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第3个

7、月后每月又生一对兔子，假设所有的兔子都不会死，问每个月的兔子总数是多少？112358132134,16,问题:存在大量重复计算，参数越大重复计算越多。,计算fib(10)?fib(3):21次 fib(30)?fib(3):317811次 fib(40)?fib(60)?.,long fib(int n)return n2?1:fib(n-1)+fib(n-2);,17,3.为计算过程计时统计程序/程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部计时功能。,有关函数在time.h，统计程序时间时程序头部应写：#include在程序里计时，通常写表达式：clock()/CLOCK

8、S_PER_SEC得到从程序开始到表达式求值时所经历的秒数。注意：有些老的C系统（如Turbe-C）用 CLK_TCK。,18,#include#includelong fib(int n)return n=1?1:fib(n 1)+fib(n 2);int main()double x;x=clock()fib(45);x=(clock()-x)/CLOCKS_PER_SEC;printf(Timing fib(45):%f.n,x);return 0;/*计算需210s*/,确定计算fib(45)所需要的时间的程序：,19,Fibonacci数的递推计算前n项,第01n-1项1）F0和F1

9、是12）知道连续两个Fibonacci数，就可算出下一个递推计算方式：逐个前推，可用循环实现：,1 1235第一次f0+f1 f2 第二次 f0+f1 f2第三次 f0+f1 f2,20,void fib1(int n)long f0,f1,f2;int i;f0=f1=1;printf(%ld%ld,f0,f1);for(i=2;i n;i+)f2=f0+f1;f0=f1;f1=f2;printf(%ld,f);if(i%5=0)printf(n);,#includevoid fib1(int);int main()int n=45;fib1(n);return 0;,Fibonacci数的

10、递推计算前n项,一次计算一个数,21,#includevoid fib1(int);int main()int n=45;fib1(n);return 0;,Fibonacci数的递推计算前n项,一次计算二个数 f0=1;f1=1;f0=f0+f1;f1=f1+f0;n为偶数算出n个数，n为奇数算出n+1个数;,void fib1(int n)long f0,f1;int i;f0=f1=1;printf(f(%d)=t%ldt,0,f1);printf(f(%d)=t%ldn,1,f2);for(i=2;i n;i=i+2)f0=f0+f1;f1=f1+f0;printf(f(%d)=t%l

11、dt,i,f0);printf(f(%d)=t%ldt,i+1,f1);if(i%2=0)printf(n);,22,Fibonacci数列的递归及非递归算法,/求Fibonacci数列非递归算法#include void fib1(int n)long f0,f1,f2;int i;f0=f1=1;printf(%ld%ld,f0,f1);for(i=2;i n;i+)f2=f0+f1;f0=f1;f1=f2;printf(%ld,f);if(i%5=0)printf(n);int main()int n=45;fib1(n);return 0;,/求Fibonacci数列递归算法#incl

12、ude long fibonacci(int n)if(n=0|n=1)return 1;else return fibonacci(n-1)+fibonacci(n-2);int main()int n;printf(Input a integer number:);scanf(%d,23,Fibonacci数列的递归及非递归算法运行时间对比,24,问题,存在大量重复计算，参数越大重复计算越多。随着参数增大，计算中重复增长迅速，最快的微机上一分钟大约可以算出fib(45)参数加1，fib多用近一倍时间(指数增长)。最快的微机一小时算不出fib(55)，算fib(100)要数万年计算需要时间，

13、复杂计算需要很长时间。这是计算机的本质特征和弱点。说明它不是万能，有些事情“不能”做。,25,思考题1,有一头母牛，在她四岁时生下一头小牛，也是母的，自此以后，她每年都生一头母牛，假设牛不会死亡，小牛生育和老牛一样，问老牛五十岁时，她有多少个后代？试用递归和递推分别解决,26,求最大公约数（greatest common divisor，GCD）写函数 long gcd(long,long),方式1：k取初值1后递增，大于m或n之一时结束。需要记录循环中找到的公约数。,解法1：逐个检查，直到找到能同时整除m和n的最大整数（生成与检查）。需辅助变量k记录检查值。,27,只需记录已找到最大的公约数

14、，用变量d，初值1（是公约数），遇到新公约数（一定更大）时记入d：if(m%k=0/*k为新找到的公约数*/有了d及其初值，k可以从2开始循环。函数定义：,long gcd(long m,long n)long d=1,k=2;for(;k=m,m,n小于零时？m,n等于零时?,28,1）m和n都为0时，令函数返回值0；2）若m和n中一个为0，gcd是另一个数。也可直接判断处理；3）m、n为负时？应在循环前加语句：,if(m=0,29,方式2：令k从某大数开始递减，找到的第一个公约数就是最大公约数。k初值可取m和n中小的一个。结束条件：k值达到1或找到了公约数。1总是公约数。,程序主要部分可写

15、为：for(k=(m n?n:m);m%k!=0|n%k!=0;k-);/*空循环体*/return k;/*循环结束时k是最大公约数*/,两种方法的共同点是重复测试。这类方法的缺点是效率较低，参数大时循环次数很多。,30,解法2：求GCD有著名的欧几里德算法（欧氏算法，辗转相除法）。最大公约数的递归定义：,函数定义（递归）：求最大公约数 假设第二个参数非0，且参数都不小于0。,long gcd1(long m,long n)return m%n=0?n:gcd1(n,m%n);,31,求最大公约数的完整程序：,#includeint main()int m,n,d;m=12;n=8;d=gc

16、d(m,n);return 1;long gcd(long m,long n)if(m 0)m=-m;if(n 0)n=-n;return n=0?m:gcd1(m,n);long gcd1(long m,long n)return m%n=0?n:gcd1(n,m%n);,32,函数定义（循环）：求最大公约数辗转相除就是反复求余数，可用循环结构实现。,循环可写为：for(r=m%n;r!=0;r=m%n)m=n;n=r;,出发点m和n；循环判断m%n是否为0，若是则n为结果；否则更新变量：令m取n的原值，n取m%n的原值。为正确更新需用辅助变量r，正确的更新序列：r=m%n;m=n;n=r;

17、,33,循环语句实现求最大公约数long gcd2(long m,long n)long r;if(m 0)m=-m;if(n 0)n=-n;if(n=0)return m;for(r=m%n;r!=0;r=m%n)m=n;n=r;return n;,请注意，这里的循环不变式！,34,递归与递推,一般情况下,大多数递归问题都可以转化为递推求解,递归调用使用选择结构,而递推求解使用循环结构.递归调用是通过不断简化原始问题,最终达到基本实例时终止。递推调用是通过不断修改循环变量的值,达到循环条件为假时结束循环。使用递归的目的是简化程序,便于阅读,但会占用CPU大量的时间和过多的内存。而非递归具有效

18、率高,但编程难度较大,可读性较差的特点。当递归函数清晰的优点可以补偿它的效率开销时，就可以使用这个工具,35,汉诺塔（hanoi塔，梵塔）问题,问题出自古印度（一说西藏）。某神庙有三根细柱，64个大小不等、中心有孔的金盘套在柱上，构成梵塔。僧侣日夜不息地将圆盘从一柱移到另一柱，规则是每次只移一个盘，大盘不能放到小盘上。开始时圆盘从大到小套在一根柱上，据说所有圆盘都搬到另一根柱时世界就要毁灭。本问题用递归写程序很简单，用循环解决较困难。,要求写程序模拟搬圆盘过程，打印出搬动指令序列。,36,分别将三根圆柱命名为a、b和c，假定开始时所有圆盘都在a上，要求最终搬到b，借助c盘。,初看问题似乎没规律

19、。求解的关键在于看到问题的“递归性质”。搬64个盘的问题可归结为两次搬63个盘。,a-ba-cb-ca-bc-ac-ba-b,37,从柱a借助柱b将3个圆盘搬到柱c,a,b,c,a,b,c,从柱a将最大的圆盘移动b柱,从柱c借助柱a将3个圆盘搬到柱b,38,汉诺塔(Tower of Hanoi)问题的解题思路：,递归算法：如果 n=1，则将这一个盘子直接从 a 柱移到 b柱上。否则，执行以下三步：用 b 柱做过渡，将 a 柱上的(n-1)个盘子移到 c 柱上；将 a 柱上最后一个盘子直接移到 b 柱上；用 a 柱做过渡，将 c 柱上的(n-1)个盘子移到 b 柱上。,一般情况：搬n个圆盘的问题

20、可以归结为搬n-1个圆盘把n个盘从柱a搬到柱b的工作可以如下完成：从柱a借助柱b将n-1个圆盘搬到柱c；将最大圆盘从柱a搬到柱b；从柱c借助柱a将n-1个圆盘搬到柱b；,a,c,b,a,c,b,a,c,b,39,定义函数void henoi(int n,char from,char to,char by)表示从from柱借助by柱移动n个盘子到to柱。,定义函数void moveone(char from,char to)表示从from柱移动1个盘子到to柱.,搬n个圆盘的问题归结为搬n-1个圆盘，把n个盘从柱a搬到柱b的工作henoi(n,a,b,c)，可以如下完成：,从柱c借助柱a将n-1

21、个圆盘搬到柱b；,从柱a借助柱b将n-1个圆盘搬到柱c；,将最大圆盘从柱a搬到柱b；,henoi(n-1,a,c,b),moveone(a,b),henoi(n-1,c,b,a),40,递归函数定义void moveone(char from,char to)printf(%c-%cn,from,to);void henoi(int n,char from,char to,char by)if(n=1)moveone(from,to);else henoi(n-1,from,by,to);moveone(from,to);henoi(n-1,by,to,from);,moveone定义为函数是

22、为了方便。函数调用：henoi(3,a,b,c);,41,hanio(3,a,b,c);hanio(2,a,c,b);moveone(a,b);hanio(2,c,b,a);,hanio(2,a,c,b)hanio(1,a,b,c);moveone(a,c);hanio(1,b,c,a);,hanio(1,a,b,c)moveone(a,b);,hanio(1,b,c,a)moveone(b,c);,hanio(2,c,b,a)hanio(1,c,a,b);moveone(c,b);hanio(1,a,b,c);,hanio(1,c,a,b)moveone(c,a);,hanio(1,a,b,c)moveone(a,b);,42,#includevoid henoi(int n,char from,char to,char by);/*对henoi的函数声明*/void moveone(char from,char to);/*对moveone的函数声明*/int main()int m;printf(input the number of diskes:);scanf(%d,完整的程序函数（定义放在主程序后）,43,思考题3,44,总结,掌握递归的概念递归函数的编写方法理解递归函数的效率,