基本程序设计技术.ppt

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

1、1高级语言程序设计高级语言程序设计2第四章第四章基本程序设计技术基本程序设计技术3主要内容：基本程序设计技术主要内容：基本程序设计技术n循环程序设计循环程序设计n循环与递归循环与递归n基本输入输出基本输入输出n控制结构和控制语句控制结构和控制语句n程序设计实例程序设计实例n程序测试和排错程序测试和排错递归与循环递归与循环递归函数的执行过程递归函数的执行过程递归函数效率递归函数效率4n重复性计算可用重复性计算可用循环循环结构完成结构完成;n有些重复性计算，有些重复性计算，C中可用中可用递归递归完成完成;例：定义计算整数阶乘的函数：例：定义计算整数阶乘的函数：12(n-1)n乘的次数依赖于乘的次数

2、依赖于n，定义时不知道，每次用可能不同。，定义时不知道，每次用可能不同。程序的典型情况：计算程序的典型情况：计算“次数次数”依赖某些参数的值。依赖某些参数的值。4.2循环与递归循环与递归5计算整数阶乘的递推函数计算整数阶乘的递推函数long fact(long n) long i, f = 1; for (i = 2; i = n; +i) f *= i; return f;类型特征可定为：类型特征可定为： int fact(int)阶乘值增长极快（数学），更合适的类型特征：阶乘值增长极快（数学），更合适的类型特征： long fact(long)6nnnnn!()!10101.关于递归定义关

3、于递归定义n如果问题本身能用数学递归描述，可用递归定义解决如果问题本身能用数学递归描述，可用递归定义解决;nC允许递归定义：允许递归定义：在函数定义内调用被定义函数本身在函数定义内调用被定义函数本身。求阶乘的数学求阶乘的数学递归定义公式递归定义公式7n嵌套调用嵌套调用C规定：规定：函数定义不可嵌套函数定义不可嵌套，但，但可以嵌套调用可以嵌套调用函数函数main( )调用函数调用函数a结束结束a函数函数b函数函数调用函数调用函数b函数的嵌套与递归调用函数的嵌套与递归调用8定义：函数直接或间接的调用自身叫函数的递归调用定义：函数直接或间接的调用自身叫函数的递归调用f( )调调f调调f2调调f1f1

4、( )f2( )说明说明C编译系统对递归函数的自调用次数没有限制编译系统对递归函数的自调用次数没有限制每调用函数一次，在内存堆栈区分配空间，用于存放函数变量、每调用函数一次，在内存堆栈区分配空间，用于存放函数变量、返回值等信息，所以递归次数过多，可能引起堆栈溢出返回值等信息，所以递归次数过多，可能引起堆栈溢出int f(int x) int y,z; z=f(y); . return(2*z);int f1(int x) int y,z; z=f2(y); . return(2*z);int f2(int t) int a,c; c=f1(a); . return(3+c);递归调用递归调用9

5、构成递归需具备的条件构成递归需具备的条件n子问题须与原始问题为同样的事，且更为简单；子问题须与原始问题为同样的事，且更为简单；n不能无限制地调用本身，必须有个出口，化简不能无限制地调用本身，必须有个出口，化简为非递归状况处理。为非递归状况处理。10long 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：求阶乘的递归函数定义求阶乘的递归

6、函数定义2 :递归如何实现递归如何实现?11fact(3) 3*fact(2)fact(2) 2*fact(1)fact(1) 1*fact(0)fact(0)调用 fact(3)返回值 1返回值 1返回值 2返回值 6图 3.3fact(3)的计算过程计算中计算中fact被递归调用被递归调用的次数由实参确定。的次数由实参确定。考虑负参数值处理。可考虑负参数值处理。可改为：改为：n=1 ? 1 : .long fact(long n) long i, f; if (n = 0) f = 1; else f=n*fact(n-1); return f;12long fact(1)if (1 =

7、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 * f

8、act(n - 1);13例例1 1 阅读源程序阅读源程序, ,写出运行结果。写出运行结果。#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;结果：结果：142.递归与计算过程递归与计算过程n包含递归的程序产生的计算过程和性质复杂，能完成很包含递归的程序产生的计算过程和性质复杂，能完成很复杂的工作。复杂的工作。q递归调用只有一个调用表达式或语句，但

9、是可能要许多步才能完递归调用只有一个调用表达式或语句，但是可能要许多步才能完成。成。q实际参数的不同，会实际产生的递归调用次数（步数）也会有很实际参数的不同，会实际产生的递归调用次数（步数）也会有很大的不同。大的不同。q递归程序的理解比较困难递归程序的理解比较困难n递归的函数定义需要有条件语句去控制递归过程的最终递归的函数定义需要有条件语句去控制递归过程的最终结束结束q直接给出结果的时候，递归结束；直接给出结果的时候，递归结束；q把对较复杂情况的计算归结为对更简单情况的计算，需要进行递把对较复杂情况的计算归结为对更简单情况的计算，需要进行递归处理。归处理。n基本运算、关系判断、条件表达式，加函

10、数定义和递归基本运算、关系判断、条件表达式，加函数定义和递归定义构成了一个（理论上）定义构成了一个（理论上）“足够强的足够强的”的程序语言。的程序语言。15Fibonacci（斐波那契）序列的递归定义：（斐波那契）序列的递归定义：求第求第n项项Fn) 1(, 1, 12110nFFFFFnnn#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); 问题分析

11、问题分析：研究程序的执行过程：研究程序的执行过程例：有一对兔子，从出生后第例：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第个月起每个月都生一对兔子，小兔子长到第3个个月后每月又生一对兔子，假设所有的兔子都不会死，问每个月的兔子总数是多月后每月又生一对兔子，假设所有的兔子都不会死，问每个月的兔子总数是多少？少？ 11235813213416 fib(5) fib(4) fib(3) fib(3) fib(2) fib(2) fib(1) Fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) fib(1) fib(0) 图图 4.1 fib(5)计算

12、中的函数调用情况计算中的函数调用情况 问题问题:存在大量重复计算，参数越大重复计算越多。存在大量重复计算，参数越大重复计算越多。计算计算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); 173.为计算过程计时为计算过程计时统计程序统计程序/程序片段的计算时间有助于理解程序性质。程序片段的计算时间有助于理解程序性质。许多语言或系统都提供了内部计时功能。许多语言或系统都提供了内部计时功能。有关函数在有关函数在time.h，统计程序时

13、间时程序头部应写：，统计程序时间时程序头部应写：#include在程序里计时，通常写表达式：在程序里计时，通常写表达式：clock()/CLOCKS_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() -

14、 x) / CLOCKS_PER_SEC; printf(Timing fib(45): %f.n, x); return 0;/*计算需计算需210s*/确定计算确定计算fib(45)所需要的时间的程序：所需要的时间的程序：19Fibonacci数的递推计算前数的递推计算前n项项,第第01n-1项项1）F0和和F1是是12）知道连续两个）知道连续两个Fibonacci数，就可算出下一个数，就可算出下一个递推计算方式：逐个前推，可用循环实现：递推计算方式：逐个前推，可用循环实现： 1 1235第一次第一次f0 + f1 f2 第二次第二次 f0 + f1 f2第三次第三次 f0 + f1 f2

15、20void 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数的递推计算前数的递推计算前n项项, 一次计算一个数一次计算一个数21#includevoid

16、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%ldt, i, f0); printf(f(%d)=t%ldt, i+1, f1);if(i%2 = 0) printf(n); 22Fibonacci数列的递归及非递归算法数列的递归及非递归算法/求求Fibonacci数列数列非递归算法非递归算法#include void fib1(int n) long f0, f1, f