清华大学程序设计课件-------第4章

1、n算法基本概念算法基本概念n算法特征算法特征n有穷性：有穷性：n确定性：确定性：n输入：输入：n有效性：有效性：n正确性正确性不是算法的特征，算法的正确性需要数学证明！不是算法的特征，算法的正确性需要数学证明！n算法步骤算法步骤执行某任务执行下一任务if( 条件表达式 )switch( 条件变量 ) 处理条件为真的情况case 常量表达式 1: 处理分支 1elsecase 常量表达式 2: 处理分支 2 处理条件为假的情况default: 处理默认分支for( 初始化表达式; 条件表达式; 步进表达式 ) | while( 条件表达式 ) 循环体内部代码逻辑描述n准备准备 终止终止 处理处理

2、 预定义处理预定义处理数据输入输出数据输入输出 条件判断条件判断 连接符连接符 流程线流程线BOOL IsPrime( unsigned int n ) unsigned int i = 2; while( i n ) if( n % i = 0 ) return FALSE; i+; return TRUE;BOOL IsPrime( unsigned int n ) unsigned int i = 2; while( i = (unsigned int)sqrt(n) ) if( n % i = 0 ) return FALSE; i+; return TRUE;BOOL IsPrime

3、( unsigned int n ) unsigned int i; if( n % 2 = 0 ) return FALSE; i = 3; while( i = (unsigned int)sqrt(n) ) if( n % i = 0 ) return FALSE; i += 2; return TRUE;BOOL IsPrime( unsigned int n ) unsigned int i; if( n % 2 = 0 ) return FALSE; i = 3; while( i = (unsigned int)sqrt(n) + 1 ) if( n % i = 0 ) retu

4、rn FALSE; i += 2; return TRUE;BOOL IsPrime( unsigned int n ) unsigned int i, t; if( n % 2 = 0 ) return FALSE; i = 3; t = (unsigned int)sqrt(n) + 1; while( i = t ) if( n % i = 0 ) return FALSE; i += 2; return TRUE;checkprime关关 于于 素素 数数素数是上帝用来描写宇宙的文字（伽利略语）素数是上帝用来描写宇宙的文字（伽利略语）求素数的常用方法：求素数的常用方法： 试商判别法试商

5、判别法 筛法筛法1。区间素数。区间素数 求区间求区间 a, b 上的所有素数上的所有素数2。梅森尼数。梅森尼数 ( Mersenne Prime ) 形如形如 2n-1 的素数的素数 例如：例如：22-1=3, 23-1=7 231 1 = 21474836473。孪生素数。孪生素数 相差为相差为 2 的两个素数的两个素数 例如：例如：3 与与 5 11 与与 13 17 与与 19 4。可逆素数。可逆素数 一个素数的逆序仍是素数一个素数的逆序仍是素数 例如：例如：37 73 可逆素数对可逆素数对 1193 1399 1913 1933 3319 5。金蝉素数。金蝉素数 对于素数对于素数k，从

6、低位去掉，从低位去掉1位位,2位位,或或3位后仍是素数；位后仍是素数；从高位去掉从高位去掉1位位,2位位,或或3位后仍是素数；同时去掉最低位位后仍是素数；同时去掉最低位与最高位后仍是素数，则与最高位后仍是素数，则k为金蝉素数。为金蝉素数。 例如：例如：373 3137 3797关关 于于 合合 数数合数世纪：合数世纪：一个世纪的一个世纪的100个年号全为合数个年号全为合数21, 200000区间中最早出现的合数世纪是区间中最早出现的合数世纪是16719世纪！世纪！最小的连续最小的连续n个合数个合数最小的最小的100个连续合数区间为个连续合数区间为 370262, 370361 unsigned

7、 int gcd(unsigned int x, unsigned int y) unsigned int t; t = x y ? x : y; while( x % t != 0 | y % t != 0 ) t-; return t;输入：正整数 x、y 输出：最大公约数步骤 1：x 整除以 y，记余数为 r步骤 2：若 r 为 0，则最大公约数即为 y，算法结束步骤 3：否则将 y 作为新 x，将 r 作为新 y，重复上述步骤unsigned int gcd(unsigned int x, unsigned int y) unsigned int r; while( TRUE ) r

8、= x % y; if( r = 0 ) return y; x = y; y = r; int mysqrt(int x) int i=1,sum=0,count=0; while (sum=x) sum+=i; count+; i+=2; return count-1;思考：思考：参数的有效性、合法性判断参数的有效性、合法性判断应应 放在函数里放在函数里? ? 放在主程序里放在主程序里? ?int mysqrt(int x) int i=0; while (i*i=x) i+; return i-1;#include int mysqrt(int);int main() int i, nu

9、m; while (1) printf(Please input a number:); scanf(%d,&num); if (num0) break; printf( sqrt(%d)=%dnn, num, mysqrt(num) ); return 0;int mysqrt(int x) 使用循环实现使用循环实现unsigned int GetFactorial(unsigned int n) unsigned int result = 1, i = 0; while( +i = n ) result *= i; return result;使用递归实现使用递归实现unsigned in

10、t GetFactorial(unsigned int n) unsigned int result; if( n = 1 )result = 1; elseresult = n * GetFactorial( n - 1 ) ; return result;Fibonacci)unsigned int GetFibonacci( unsigned int n ) / 使用循环实现使用循环实现 unsigned int result, i, f1, f2; if( n = 2 | n = 1 )return 1; f2 = 1; f1 = 1; for( i = 3; i = n; i+ )

11、result = f1 + f2; f1 = f2; f2 = result; return result;unsigned int GetFibonacci(unsigned int n) /使用递归实现使用递归实现 if ( n = 2 | n = 1 ) return 1; else return GetFibonacci(n-1)+GetFibonacci(n-2);使用递归实现：使用递归实现：unsigned int gcd( unsigned int x, unsigned int y ) if (x%y=0) return y; return gcd(y,x%y) ;unsign

12、ed int gcd( unsigned int x, unsigned int y ) unsigned int r; while( TRUE ) r = x % y; if( r = 0 ) return y; x = y; y = r; n循环使用显式的循环结构重复执行代码段，循环使用显式的循环结构重复执行代码段， 递归使用重复的函数调用执行代码段递归使用重复的函数调用执行代码段n循环在满足其终止条件时终止执行，循环在满足其终止条件时终止执行， 递归在问题简化到最简单情形时终止执行递归在问题简化到最简单情形时终止执行n循环和递归都可能隐藏程序错误，循环的条件测试可能永循环和递归都可能隐藏

13、程序错误，循环的条件测试可能永远为真，递归可能永远退化不到最简单情形远为真，递归可能永远退化不到最简单情形n理论上，任何递归程序都可以使用循环迭代的方法解决理论上，任何递归程序都可以使用循环迭代的方法解决n递归函数的代码更短小精悍递归函数的代码更短小精悍n一旦掌握递归的思考方法，递归程序更易理解一旦掌握递归的思考方法，递归程序更易理解#include #include zylib.hvoid PrintWelcomeInfo();unsigned int GetInteger( STRING prompt );unsigned int GetFactorial( unsigned int n

14、);int main() unsigned int n, result; PrintWelcomeInfo(); n = GetInteger( Input a non-negative number: ); result = GetFactorial( n ) ; printf( %d! = %d.n, n, result ); return 0;void PrintWelcomeInfo() printf( The program gets a number and computes the factorial.n );unsigned int GetInteger( STRING pro

15、mpt ) unsigned int t; printf( prompt ); t = GetIntegerFromKeyboard(); return t;unsigned int GetFactorial( unsigned int n ) unsigned int result; if( n = 1 ) result = 1; else result = n * GetFactorial( n - 1 ) ; return result;求求 3! 的递归调用与返回的递归调用与返回 fact(2)fact(2)=2=2* *fact(1)fact(1)=2=2* *1 1=2=2返回返回

16、 fact(3)fact(3)=3=3* *fact(2)fact(2)=3=3* *2 2=6=6返回返回 fact(1)=1调用调用调用调用unsigned int GetFactorial( unsigned int n ) fact 31 fact(3) 真真 假假 调调用用 fact(2) 计计算算 3*fact(2) fact(2) fact(1) 21 真真 假假 调调用用 fact(1) 计计算算 2*fact(1) 11 真真 假假 fact(1) 1 返返回回 返返回回 fact(3) 真真 假假 3=1 调调用用 fact(2) 真真 假假 假假 真真 2=1 1=1 f

17、act(2)=2*fact(1) 返返回回 fact(3)=3*fact(2) 返返回回 调调用用 fact(1) fact(1) =1 返返回回 3nresultmainmain 函数栈框架函数栈框架mainGetFactorial第一次以第一次以 3 为参数调用为参数调用 GetFactorial，进入函数时，进入函数时3nresultmainGetFactorial第二次以第二次以 2 为参数调用为参数调用 GetFactorial，进入函数时，进入函数时GetFactorial2nresultmainGetFactorial第三次以第三次以 1 为参数调用为参数调用 GetFactor

18、ial，进入函数时，进入函数时GetFactorialGetFactorial1nresultmainGetFactorial第三次以第三次以 1 为参数调用为参数调用 GetFactorial，退出函数前，退出函数前GetFactorialGetFactorial11nresultmainGetFactorial第二次以第二次以 2 为参数调用为参数调用 GetFactorial，退出函数前，退出函数前GetFactorial22nresultmainGetFactorial第一次以第一次以 3 为参数调用为参数调用 GetFactorial，退出函数前，退出函数前36nresult36nr

19、esultmain递归调用结束后的递归调用结束后的 main 函数栈框架函数栈框架n待解决的问题待解决的问题n解答方案解答方案nA1：只有一个圆盘时是最简单情形：只有一个圆盘时是最简单情形nA2：对于：对于 n 1，考虑，考虑 n 1 个圆盘，如果能将个圆盘，如果能将 n - 1 个个圆盘移动到某个塔座上，则可以移动第圆盘移动到某个塔座上，则可以移动第 n 个圆盘个圆盘n策略：策略：首先将首先将 n 1 个圆盘移动到塔座个圆盘移动到塔座 Y 上上，然后将第，然后将第 n 个圆盘移动到个圆盘移动到 Z 上，上，最后再将最后再将 n - 1 个圆盘从个圆盘从 Y 上移上移动到动到 Z 上上递递 归

20、归XYZXYZXYZXYZXYZXYZXYZvoid MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to) if( n = 1 ) 将一个圆盘从将一个圆盘从 from 移动到移动到 to else 将将 n 1 个圆盘从个圆盘从 from 以以 to 为中转移动到为中转移动到 tmp 将圆盘将圆盘 n 从从 from 移动到移动到 to 将将 n - 1个圆盘从个圆盘从 tmp 以以 from 为中转移动到为中转移动到 to fromtmpton-1#include #include “zylib.h”/* 枚举类型枚举类型 HA

21、NOI，其文字分别表示三个圆柱的代号其文字分别表示三个圆柱的代号 */typedef enum X, Y, Z HANOI;void PrintWelcomeInfo();unsigned int GetInteger( STRING prompt );void MoveHanoi( unsigned int n, HANOI from, HANOI tmp, HANOI to );STRING ConvertHanoiToString( HANOI x );void MovePlate( unsigned int n, HANOI from, HANOI to );int main() un

22、signed int n; PrintWelcomeInfo(); n = GetInteger( Input number of plates: ); MoveHanoi( n, X, Y, Z ); return 0;void PrintWelcomeInfo() printf( The program shows the moving process of Hanoi Tower.n );unsigned int GetInteger( STRING prompt ) unsigned int t; printf( prompt ); t = GetIntegerFromKeyboard

23、(); return t;STRING ConvertHanoiToString( HANOI x ) switch( x ) case X: return X; case Y: return Y; case Z: return Z; default: return Error; void MovePlate( unsigned int n, HANOI from, HANOI to ) STRING from_str, to_str; from_str = ConvertHanoiToString( from ); to_str = ConvertHanoiToString( to ); p

24、rintf( %d: %s - %sn, n, from_str, to_str );void MoveHanoi(unsigned int n,HANOI from,HANOI tmp,HANOI to) if( n = 1 ) MovePlate( n, from, to ); else MoveHanoi( n - 1, from, to, tmp ); MovePlate( n, from, to ); MoveHanoi( n - 1, tmp, from, to ); n的含义？的含义？n的含义？的含义？#include int step=0;void move( char, ch

25、ar );void MoveHanoiTower( int, char, char, char );int main() int n; printf(please input n=); scanf(%d, &n); MoveHanoiTower(n,X,Y,Z); return 0;简化版简化版void MoveHanoiTower(int num,char source,char temp,char dest) if( num = 1 ) move( source, dest ); else MoveHanoiTower( num - 1, source, dest, temp ); mov

26、e( source, dest ); MoveHanoiTower( num - 1, temp, source, dest ); void move( char source, char dest ) step+; printf( step %3d: %c-%cn, step, source, dest );num的含义？的含义？假设有假设有64个圆盘个圆盘 n = 64264 - 1 = 18，446，744，073，709，551，615Hanoi问题问题-2 仍然是给定仍然是给定N只盘子，只盘子，3根柱子，但是允许每次最多根柱子，但是允许每次最多移动相邻的移动相邻的M只盘子（当然移动盘

27、子的数目也可以小于只盘子（当然移动盘子的数目也可以小于M）,最少需要多少次？最少需要多少次？ 例如例如N=5，M=2时，时， 可以分别将最小的可以分别将最小的2个盘子、中间的个盘子、中间的2个盘子以及最大的个盘子以及最大的一个盘子分别看作一个整体，这样可以转变为一个盘子分别看作一个整体，这样可以转变为N=3，M=1的情况，共需要移动的情况，共需要移动7次。次。递推：递推：从已知的初始条件出发，逐次去求所需要的阶乘值。从已知的初始条件出发，逐次去求所需要的阶乘值。 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2

28、) = 6 for ( i=1; i=n; i+ ) / 循环结构循环结构 result*= i;递归与递推递归与递推(迭代迭代)的比较（以求的比较（以求 n! 为例）为例）递归：递归：出发点不在初始条件上，而在求解目标上。出发点不在初始条件上，而在求解目标上。 从所求的未知项出发，逐次调用自身，直到从所求的未知项出发，逐次调用自身，直到 递归的边界（初始条件）。递归的边界（初始条件）。 递归算法比较符合人的思维方式，逻辑递归算法比较符合人的思维方式，逻辑 性强，易于理解。性强，易于理解。unsigned long fact(int m)if (m=1) return 1;else retur

29、n m*fact(m-1); / / 递归调用递归调用递归与递推的相似之处：递归与递推的相似之处： 都基于控制结构，均涉及循环 递推：使用显式循环结构 递归：使用选择结构，通过重复性的函数调用实现循环 均涉及终止测试，都有可能发生无限循环 递推：在循环条件不满足时终止 递归：遇到初始条件时终止 能用递归算法解决的问题，也能用递推算法解决。王小二切饼王小二切饼 1 2 4 7 11切0刀 切1刀 切2刀 切3刀 切4刀切切100100刀后最多可得多少块？刀后最多可得多少块？递推问题举例：递推问题举例： A、B、C、D、E 五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自睡去。日上三竿，A第一个醒来，他将

30、鱼平分为5份，把多余的一条扔回湖中，拿着自己的一份回家了；B第二个醒来，他也将鱼分为5份，扔掉多余的一条，只拿走自己的一份；接着C、D、E依次醒来，也都按同样的办法分鱼。 问题：五人至少捕了多少条鱼？每人醒来后看到的鱼是多少条？五人分鱼五人分鱼几个问题的递归思想几个问题的递归思想：求求 a1 a2 a3 an-1 an 的和的和求求 a1 a2 a3 an-1 an 的最大的最大(最小最小)数数给给 a1 a2 a3 an-1 an 排序排序求一个自然数的各位数字之和求一个自然数的各位数字之和下楼问题下楼问题跳马问题跳马问题八皇后问题八皇后问题n递归实现是否检查了最简单情形递归实现是否检查了最

31、简单情形n是否解决了最简单情形是否解决了最简单情形n递归分解是否使问题更简单递归分解是否使问题更简单n问题简化过程是否能够确实回归最简单情形，还问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况是遗漏了某些情况n子问题是否与原始问题完全一致子问题是否与原始问题完全一致n使用递归信任时，子问题的解是否正确组装为原使用递归信任时，子问题的解是否正确组装为原始问题的解始问题的解n数据有效性检查数据有效性检查n程序流程的提前终止程序流程的提前终止n断言与不变量断言与不变量void GetUserInput() 获取用户输入数据获取用户输入数据 while( 用户输入数据无效用户输入数据无效 )

32、 通知用户输入数据有误，提醒用户重新输入数据通知用户输入数据有误，提醒用户重新输入数据 重新获取用户输入数据重新获取用户输入数据 void Input() c = GetFloat( Input a temperature value (C): ); while( c = absolute_zero ) printf( The temperature value is below %.2f.n, absolute_zero ); c = GetFloat( Input a temperature greater than the absolute zero: ); const int fail

33、ed_in_testing_primality = 1;BOOL IsPrime( unsigned int n ) unsigned int i, t; if( n = 1 ) printf( IsPrime: Failed in testing the primality of %d.n, n ); exit( failed_in_testing_primality ); if( n = 2 )return TRUE; if( n % 2 = 0 )return FALSE; i = 3; t = (unsigned int)sqrt(n) + 1; while( i = t ) if( n % i = 0 )return FALSE; i += 2; return TRUE; 头文件：#include 函数: void abort(void);说明：这是一个比较严重的函数，调用它会导致程序异常终止，而不会进行 一些常规的清除工作，如释放内存等。头文件：#include函数：void exit(int status);说明：用来正常终结目前程序的执行。 它不像abort那样不做任何清理工作就退出，而是在完成所有清理工作 （释放内存、关闭文件等）后才退出