c语言程序设计现代方法课件.ppt

1、第9章：函数c语言程序设计现代方法Copyright 2008 W.W.Norton&Company.All rights reserved.1第9章：函数本章要点第9章：函数概述 函数简单来说就是一连串组合在一起并且命名的语句。每个函数本质上是一个自带声明和语句的小程序。函数的优点：可以利用函数把程序划分成小块，这样便于人们理解和修改程序。可以避免重复编写可多次使用的代码。一个函数最初可能是某个程序的一部分，但可以将其用于其他程序中。3第9章：函数函数的定义和调用 在介绍定义函数的规则之前，先来看3个简单的定义函数的程序。4第9章：函数程序：计算平均值 一个叫做average的函数用来计算两

2、个double类型数值的平均值：double average(double a,double b)return(a+b)/2;在函数开始处放置的单词double表示了average函数的返回类型(return type)。标识符a和标识符b(即函数的形式参数(parameter)表示在调用average函数时提供的求平均值的两个数。5第9章：函数程序：计算平均值 每个函数都有一个用大括号括起来的执行部分，称为函数体(body)。average函数的函数体由一条return语句构成。执行这条语句将会使函数“返回”到调用它的地方，表达式(a+b)/2的值将作为函数的返回值。6第9章：函数程序：计算

3、平均值 一个函数调用包括函数名和其后的实际参数(arguments)列表。average(x,y)即为对average函数的调用。实际参数用来给函数提供信息。调用average(x,y)的效果就是把变量x和y的值复制给形式参数a和b。实际参数不一定要是变量；任何正确类型的表达式都可以。average(5.1,8.9)和 average(x/2,y/3)都是合法的。7第9章：函数程序：计算平均值 我们把average函数的调用放在需要使用其返回值的地方。打印x和y平均值的语句为：printf(Average:%gn,average(x,y);average的返回值没有保存；程序显示出这个值后就把

4、它丢弃了。如果需要在稍后的程序中用到返回值，可以把这个返回值赋值给变量：avg=average(x,y);8第9章：函数程序：计算平均值 程序average.c读取了3个数并且计算它们的平均值，其中，一次计算一对数的平均值：Enter three numbers:3.5 9.6 10.2Average of 3.5 and 9.6:6.55Average of 9.6 and 10.2:9.9Average of 3.5 and 10.2:6.859第9章：函数average.c/*Computes pairwise averages of three numbers*/#include do

5、uble average(double a,double b)return(a+b)/2;int main(void)double x,y,z;printf(Enter three numbers:);scanf(%lf%lf%lf,&x,&y,&z);printf(Average of%g and%g:%gn,x,y,average(x,y);printf(Average of%g and%g:%gn,y,z,average(y,z);printf(Average of%g and%g:%gn,x,z,average(x,z);return 0;10第9章：函数程序：显示倒数计数 为了指示出

6、不带返回值的函数，需要指明这类函数的返回类型为void：void print_count(int n)printf(T minus%d and countingn,n);void是一种没有值的类型。print_count函数的调用必须自成一个语句：print_count(i);程序countdown.c在循环内调用了print_count 函数10次。11第9章：函数countdown.c/*Prints a countdown*/#include void print_count(int n)printf(T minus%d and countingn,n);int main(void)in

7、t i;for(i=10;i 0;-i)print_count(i);return 0;12第9章：函数程序：显示双关语(改进版)当函数没有形式参数时，则在函数名后面的圆括号中填入 void：void print_pun(void)printf(To C,or not to C:that is the question.n);为了调用不带实际参数的函数，需要写出函数名并且后面跟上一对圆括号：print_pun();即使没有实际参数也必须显示圆括号。程序pun2.c测试了print_pun函数。13第9章：函数pun2.c/*Prints a bad pun*/#include void pri

8、nt_pun(void)printf(To C,or not to C:that is the question.n);int main(void)print_pun();return 0;14第9章：函数函数定义 函数定义函数定义的一般格式：返回类型 函数名(形式参数)声明 语句15第9章：函数函数定义 函数的“返回类型”是函数返回值的类型。下列规则用来管理返回类型：函数无法返回数组。指定返回类型是void型说明函数没有返回值。在C89中，如果忽略返回类型，那么会假定函数返回值的类型是int型。在C99中，忽略返回类型是非法的。16第9章：函数函数定义 一些程序员习惯把返回类型放在函数名的上

9、边：doubleaverage(double a,double b)return(a+b)/2;如果返回类型很冗长，比如unsigned long int类型，那么把返回类型单独放在一行是非常有用的。17第9章：函数函数定义 函数名后边有一串形式参数列表。每个形式参数需要说明其类型；形式参数间用逗号进行分隔。如果函数没有形式参数，那么在圆括号内应该出现void。18第9章：函数函数定义 函数体可以包含声明和语句。average函数的变体：double average(double a,double b)double sum;/*declaration*/sum=a+b;/*statement*

10、/return sum/2;/*statement*/19第9章：函数函数定义 函数体内声明的变量专属于此函数，其他函数不能对这些变量进行检查或修改。在C89中，变量声明必须出现在语句之前。在C99中，变量声明和语句可以混在一起，只要变量在第一次使用前进行声明即可。20第9章：函数函数定义 返回类型为void的函数(“void 函数”)的函数体可以为空：void print_pun(void)在程序开发过程中，作为一种临时措施，留下空函数体是有意义的。21第9章：函数函数调用 函数调用由函数名和跟随其后的实际参数列表组成，其中实际参数列表用圆括号括起来：average(x,y)print_co

11、unt(i)print_pun()如果丢失圆括号，那么将无法进行函数调用：print_pun;/*WRONG*/这条语句是合法的，但是不起作用。22第9章：函数函数调用 void型的函数调用是语句，所以调用后边始终跟着分号：print_count(i);print_pun();非void型的函数调用产生的值可存储在变量中，还可以进行测试、显示或者其他用途：avg=average(x,y);if(average(x,y)0)printf(Average is positiven);printf(The average is%gn,average(x,y);23第9章：函数函数调用 如果不需要，非

12、void型函数的返回值总是可以丢弃：average(x,y);/*discards return value*/这个调用是一个表达式语句的示例：一个计算出了表达式值但是将其丢弃的语句。24第9章：函数函数调用 丢弃average的返回值是一件很奇怪的事，但在某些情况下是有意义的：例如：printf返回显示的字符的个数。在下面的调用后，num_chars的值为9：num_chars=printf(Hi,Mom!n);通常会丢掉printfs的返回值：printf(Hi,Mom!n);/*discards return value*/25第9章：函数函数调用 为了清楚地表示故意丢掉函数返回值，C语

13、言允许在函数调用前加上(void)：(void)printf(Hi,Mom!n);使用(void)可以使别人清楚编写者是故意扔掉返回值的，而不是忘记了。26第9章：函数程序：判定素数 程序prime.c检查一个数是否是素数：Enter a number:34Not prime 程序使用名为is_prime的函数来进行检查。该函数返回值为true就表示它的形式参数是素数，返回false就表示它的形式参数不是素数。给定数n后，is_prime函数把n除以从2到n的平方根之间的每一个数：如果余数永远为0，就知道n不是素数。27第9章：函数prime.c/*Tests whether a number

14、 is prime*/#include /*C99 only*/#include bool is_prime(int n)int divisor;if(n=1)return false;for(divisor=2;divisor*divisor=n;divisor+)if(n%divisor=0)return false;return true;28第9章：函数int main(void)int n;printf(Enter a number:);scanf(%d,&n);if(is_prime(n)printf(Primen);else printf(Not primen);return 0

15、;29第9章：函数函数声明 C语言没有要求函数的定义必须放置在调用它之前。假设重新编排程序average.c，使average函数的定义放置在main函数的定义之后：30第9章：函数函数声明#include int main(void)double x,y,z;printf(Enter three numbers:);scanf(%lf%lf%lf,&x,&y,&z);printf(Average of%g and%g:%gn,x,y,average(x,y);printf(Average of%g and%g:%gn,y,z,average(y,z);printf(Average of%g

16、and%g:%gn,x,z,average(x,z);return 0;double average(double a,double b)return(a+b)/2;31第9章：函数函数声明 当遇到main函数中第一个average函数调用时，编译器没有任何关于average函数的信息。但是，编译器没有产生错误信息，而是假设average函数返回int型的值。我们将其称为编译器为该函数创建了一个隐式声明(implicit declaration)。32第9章：函数函数声明 编译器无法检查传递给average的实参个数和实参类型是否正确。它只能进行默认的实际参数提升并期待最好情况的发生。当编译器

17、在后面遇到了average的定义时，它发现该函数返回值实际是double而非int，结果我们将得到一条错误消息的提示。33第9章：函数函数声明 为了避免定义前调用这类问题的发生，一种方法是安排程序，使每个函数的定义都在此函数调用之前进行。可惜的是，这类安排不总是存在的。而且即使真的做了这类安排，也会因为按照不自然的顺序放置函数定义，使程序难以阅读。34第9章：函数函数声明 幸运的是，C语言提供了一种更好的解决办法：在调用前声明(declare)每个函数。函数声明(function declaration)使得编译器对函数进行概要浏览，而函数的完整定义稍后再出现。函数声明的一般形式：返回类型 函

18、数名(形式参数);函数的声明必须与函数的定义一致。下面是为average函数添加了声明后程序的样子：35第9章：函数函数声明#include double average(double a,double b);/*DECLARATION*/int main(void)double x,y,z;printf(Enter three numbers:);scanf(%lf%lf%lf,&x,&y,&z);printf(Average of%g and%g:%gn,x,y,average(x,y);printf(Average of%g and%g:%gn,y,z,average(y,z);prin

19、tf(Average of%g and%g:%gn,x,z,average(x,z);return 0;double average(double a,double b)/*DEFINITION*/return(a+b)/2;36第9章：函数函数声明 我们把正在讨论的这类函数声明称为函数原型(function prototype)。C语言还有一种老式的函数声明风格，即圆括号内可以留空。函数原型不需要说明函数形式参数的名字，只要显示它们的类型就可以了：double average(double,double);通常最好是不要忽略形式参数的名字。37第9章：函数函数声明 C99遵循这样的规则：在调

20、用一个函数之前，必须先对其进行声明或定义。调用函数时，如果此前编译器未见到该函数的声明或定义，会导致出错。38第9章：函数实际参数 在C语言中，实际参数是通过值传递的：调用函数时，计算出每个实际参数的值并且把它赋值给相应的形式参数。在函数执行过程中，对形式参数的改变不会影响实际参数的值，这是因为形式参数中包含的是实际参数值的副本。39第9章：函数实际参数 实际参数按值传递既有利也有弊。既然形式参数的修改不会影响到相应的实际参数，那么可以把形式参数作为函数内的变量来使用，因此可以减少真正需要的变量的数量。40第9章：函数实际参数 思考下面这个函数，此函数用来计算数x的n次幂：int power(

21、int x,int n)int i,result=1;for(i=1;i 0)result=result*x;return result;42第9章：函数实际参数 C语言关于实际参数按值传递的要求使它很难编写某些类型的函数。假设我们需要一个函数，它将把double型的值分解成整数部分和小数部分。因为函数无法返回两个数，所以可以尝试把两个变量传递给函数并且修改它们：void decompose(double x,long int_part,double frac_part)int_part=(long)x;frac_part=x-int_part;43第9章：函数实际参数 假设采用下面的方法调用

22、这个函数：decompose(3.14159,i,d);可惜的是，变量i和d不会因为赋值给int_part和frac_part而受到影响。第11章中将阐述如何使decompose函数正确地工作。44第9章：函数实际参数的转换 C语言允许在实际参数的类型与形式参数的类型不匹配的情况下进行函数调用。管理如何转换实际参数的规则与编译器是否在调用前遇到函数(或者函数的完整定义)的原型有关：45第9章：函数实际参数的转换 编译器在调用前遇到原型。编译器在调用前遇到原型。就像使用赋值一样，每个实际参数的值被隐式地转换成相应形式参数的类型。例如：如果把int类型的实际参数传递给期望得到double型数据的函

23、数，那么会自动把实际参数转换成double类型。46第9章：函数实际参数的转换 编译器在调用前没有遇到原型。编译器在调用前没有遇到原型。编译器执行默认的实际参数提升默认的实际参数提升：把float型的实际参数转换成double类型。执行整数的提升，即把char型和short型的实际参数转换成int型(在C99中实现了整数提升)。47第9章：函数实际参数的转换依赖默认的实际参数提升是危险的。例如：#include int main(void)double x=3.0;printf(Square:%dn,square(x);return 0;int square(int n)return n*n;

24、在调用square函数时，编译器没有遇到原型，所以不知道该函数期望有int类型的实际参数。48第9章：函数实际参数的转换 取而代之的，编译器在变量x上执行了没有效果的默认的实际参数提升。因为square函数期望有int类型的实际参数，但是却获得了double类型值，所以square函数将产生无效的结果。把squares的实际参数强制转换为正确的类型可解决这个问题：printf(Square:%dn,square(int)x);当然更好的解决方案是在调用square函数前提供其原型。在C99中，调用square之前不提供声明或者定义是错误的。49第9章：函数数组型实际参数 当形式参数是一维数组时

25、，可以不说明数组的长度：int f(int a)/*no length specified*/C语言没有为函数提供任何简便的方法来确定传递给它的数组的长度。但是，如果函数需要，必须把长度作为额外的实际参数提供出来。50第9章：函数数组型实际参数 例子：int sum_array(int a,int n)int i,sum=0;for(i=0;i n;i+)sum+=ai;return sum;因为sum_array需要知道a的长度，所以我们需要将其作为第二个参数提供出来。51第9章：函数数组型实际参数 sum_array函数的原型形式如下：int sum_array(int a,int n);

26、通常情况下，如果愿意可以忽略形式参数的名字：int sum_array(int,int);52第9章：函数数组型实际参数 在调用sum_array函数时，第一个参数是数组的名字，而第二个参数是这个数组的长度。#define LEN 100 int main(void)int bLEN,total;total=sum_array(b,LEN);注意，在把数组名传递给函数时，不要在数组名的后边放置方括号：total=sum_array(b,LEN);/*WRONG*/53第9章：函数数组型实际参数 函数无法检测通过传递是否获得了正确的数组长度。人们可以利用这个事实，方法是告诉函数数组比实际小得多。

27、假设虽然数组b可以拥有100个元素，但是实际仅存储了50个元素。通过书写下列语句可以对数组的前50个元素进行求和：total=sum_array(b,50);54第9章：函数数组型实际参数 注意不要告诉函数，数组型实际参数要比实际的大大：total=sum_array(b,150);/*WRONG*/sum_array函数将超出数组的末尾，导致不可知的行为。55第9章：函数数组型实际参数 函数可以改变数组型形式参数的元素，且改变会在相应的实际参数中体现出来。下面的函数通过在每个数组元素中存储0来修改数组：void store_zeros(int a,int n)int i;for(i=0;i

28、n;i+)ai=0;56第9章：函数数组型实际参数 调用store_zeros:store_zeros(b,100);数组型实际参数的元素可以修改似乎与C语言中实际参数的值传递相矛盾。第12章中将解释这其实不矛盾。57第9章：函数数组型实际参数 如果形式参数是多维数组，则只有第一维的长度可以省略。如果我们修改sum_array函数，使得a是个二维数组，则必须指定a中列的数量：#define LEN 10 int sum_two_dimensional_array(int aLEN,int n)int i,j,sum=0;for(i=0;i n;i+)for(j=0;j LEN;j+)sum+=

29、aij;return sum;58第9章：函数数组型实际参数 不能传递具有任意列数的多维数组是很讨厌的。但我们经常可以通过使用指针数组来解决这个问题。C99中的变长数组形式参数为上述问题提供了一个更好的解决方案。59第9章：函数变长型数组形式参数(C99)C99允许使用变长型数组作为形式参数。考虑sum_array函数：int sum_array(int a,int n)这样的定义使得n和数组a的长度之间没有直接的联系。尽管函数体会将n看作数组a的长度，但是数组的实际长度有可能比n大或者小。60第9章：函数变长型数组形式参数(C99)如果使用变长数组形式参数，我们可以明确说明数组a的长度就是n

30、：int sum_array(int n,int an)第一个参数(n)的值确定了第二个参数(a)的长度。注意这里交换了形式参数的顺序，使用变长数组形式参数时，参数的顺序很重要。61第9章：函数变长型数组形式参数(C99)对于新版本的sum_array函数，其函数原型有好几种写法：一种写法是使其看起来跟函数定义一样：int sum_array(int n,int an);/*Version 1*/另一种写法是用*(星号)取代数组长度：int sum_array(int n,int a*);/*Version 2a*/62第9章：函数变长型数组形式参数(C99)使用*的理由是：函数声明时，形式参

31、数的名字是可选的。如果第一个参数定义被省略了,那么就没有办法说明数组的长度是n，而*的使用则为我们提供了一个线索数组的长度与形式参数列表中前面的参数相关：int sum_array(int,int*);/*Version 2b*/63第9章：函数变长型数组形式参数(C99)另外，方括号中为空也是合法的。在声明数组参数中我们经常这么做：int sum_array(int n,int a);/*Version 3a*/int sum_array(int,int);/*Version 3b*/让括号为空不是一个好的选择，因为这样并没有说明n和a的关系。64第9章：函数变长型数组形式参数(C99)一般

32、来说，变长数组形式参数的长度可以是任意表达式。假设要编写一个函数来连接数组a和b，结果存到第三个数组c中：int concatenate(int m,int n,int am,int bn,int cm+n)这里用于指定数组C长度的表达式只用到了另外两个参数；但一般来说，该表达式可以使用函数外部的变量，甚至可以调用其他函数。65第9章：函数变长型数组形式参数(C99)一维变长数组做形式参数的用途往往是有限的。一维变长数组形式参数通过指定数组参数的长度使得函数的声明和定义更具描述性。但是，由于没有进行额外的错误检测，数组参数仍然有可能太长或太短。66第9章：函数变长型数组形式参数(C99)如果变

33、长数组参数是多维的则更加实用。如果使用变长数组形式参数，则可以把sum_two_dimensional_array函数推广到任意列数的情况：int sum_two_dimensional_array(int n,int m,int anm)int i,j,sum=0;for(i=0;i n;i+)for(j=0;j=0?n:0;75第9章：函数return语句 如果return语句中表达式的类型和函数的返回类型不匹配，那么系统将会把表达式的类型隐式转换成返回类型。例如，如果声明函数返回int型值，但是return语句包含double型表达式，那么系统将会把表达式的值转换成int型。76第9章：

34、函数return语句 如果没有给出表达式，return语句可以出现在返回类型为void的函数中：return;/*return in a void function*/例子：void print_int(int i)if(i 0)return;printf(%d,i);77第9章：函数return语句 Return语句可以出现在void函数的末尾：void print_pun(void)printf(To C,or not to C:that is the question.n);return;/*OK,but not needed*/这里return语句不是必需的。如果非void函数到达了函

35、数体的末尾(也就是说没有执行return语句)，那么如果程序试图使用函数的返回值，其行为将是未定义的。78第9章：函数程序终止 正常情况下，main的返回类型是int：int main(void)以往的C程序常常省略main的返回类型，这其实是利用了返回类型默认为int类型的传统：main()79第9章：函数程序终止 省略函数的返回类型在C99中是非法的，所以应避免这么做。省略main函数参数列表中的void是合法的，但是最好显式地表明main函数没有参数。80第9章：函数程序终止 main数返回的值是状态码，在程序终止时可以检测到状态码。如果程序正常终止，main函数应该返回0。为了说明异常

36、终止，main函数应该返回非0的值。确信每个C程序都返回状态码是一个很好的实践。81第9章：函数exit函数 在main函数中执行return语句是终止程序的一种方法。另一种方法是调用exit函数，此函数属于。传递给exit函数的实际参数和main函数的返回值具有相同的含义：两者都说明程序终止时的状态。为了说明正常终止，传递0：exit(0);/*normal termination*/82第9章：函数exit函数 因为0有些模糊，所以C语言允许用传递EXIT_SUCCESS来代替(效果是相同的)：exit(EXIT_SUCCESS);传递EXIT_FAILURE表示异常终止：exit(EXI

37、T_FAILURE);EXIT_SUCCESS和EXIT_FAILURE是定义在 中的宏。EXIT_SUCCESS和EXIT_FAILURE的值都是事先定义的，通常分别为0和1。83第9章：函数exit函数 Main函数中的语句return 表达式;等价于exit(表达式);return语句和exit函数之间的差异是：不管哪个函数调用exit函数都会导致程序终止。Return语句仅当由main函数调用时才会导致程序终止。84第9章：函数递归 如果函数调用它本身，那么此函数就是递归的(recursive)。例如，利用公式n!=n (n 1)!，下面的函数可以递归地计算出n!的结果：int fac

38、t(int n)if(n=1)return 1;else return n*fact(n-1);85第9章：函数 为了了解递归的工作原理，一起来跟踪下面这个语句的执行：i=fact(3);fact(3)发现 3 不是小于或等于 1,所以它调用 fact(2),此函数发现 2不是小于或等于 1,所以它调用 fact(1),此函数发现 1是小于或等于 1的,所以它返回1，从而导致 fact(2)返回 2 1=2，从而导致fact(3)返回 3 2=6。递归86第9章：函数递归 下面的递归函数利用公式xn=x xn1计算出xn的值：int power(int x,int n)if(n=0)retur

39、n 1;else return x*power(x,n-1);87第9章：函数递归 通过把条件表达式放入return语句中，可以精简power函数：int power(int x,int n)return n=0?1:x*power(x,n-1);一旦被调用，fact函数和power函数都会仔细地测试“终止条件”。所有递归函数都需要某些类型的终止条件。88第9章：函数快速排序算法 递归对要求函数调用自身两次或多次的复杂算法非常有帮助。实际上，递归经常作为分治法(divide-and-conquer)技术的结果自然地出现。这种称为分治法的算法设计方法把一个大问题划分成多个较小的问题，然后采用相同

40、的算法分别解决这些小问题。89第9章：函数 分治法的经典示例就是流行的排序算法快速排序(quicksort)。假设要排序的数组的下标从1到n。快速排序算法快速排序算法(1)选择数组元素e(作为“分割元素”)，然后重新排列数组使得元素从1一直到i-1都是小于或等于元素e的，元素i包含e，而元素从i+1一直到n都是大于或等于e的。(2)通过递归地采用快速排序方法，对从1到i-1的元素进行排序。(3)通过递归地采用快速排序方法，对从i+1到n的元素进行排序。快速排序算法90第9章：函数快速排序算法 显然快速排序中的第1步是很关键的。有许多种方法可以用来分割数组。我们采用的方法是很容易理解的，但是它不

41、是特别有效。该算法依赖于两个名为low和high的标记，这两个标记用来跟踪数组内的位置。91第9章：函数快速排序算法开始，low指向数组中的第一个元素，而high指向末尾元素。首先把第一个元素(分割元素)复制给其他地方的一个临时存储单元，从而在数组中留出一个“空位”。接下来，从右向左移动high，直到high指向小于分割元素的数时停止。然后把这个数复制给low指向的空位，这将产生一个新的空位(high指向的)。现在从左向右移动low，寻找大于分割元素的数。在找到时，把这个找到的数复制给high指向的空位。重复执行此过程，交替操作low和high直到两者在数组中间的某处相遇时停止。此时，两个标记

42、都将指向空位：只要把分割元素复制给空位就够了。92第9章：函数快速排序算法 分割数组的示例：93第9章：函数快速排序算法 从最后一个图可以看出，分割元素左侧的所有元素都小于或等于12，而其右侧的所有元素都大于或等于12。既然己经分割了数组，那么就可以使用快速排序法对数组的前4个元素(10,3,6,和7)和后2个元素(15和18)进行递归快速排序了。94第9章：函数程序：快速排序 让我们先来开发一个名为quicksort的递归函数，此函数采用快速排序算法对整型数组进行排序。程序qsort.c 将10个数读入一个数组，调用quicksort函数来对数组进行排序，然后打印数组中的元素：Enter 1

43、0 numbers to be sorted:9 16 47 82 4 66 12 3 25 51In sorted order:3 4 9 12 16 25 47 51 66 82 分割数组的代码放置在名为split的独立的函数中。95第9章：函数qsort.c/*Sorts an array of integers using Quicksort algorithm*/#include#define N 10 void quicksort(int a,int low,int high);int split(int a,int low,int high);int main(void)int

44、aN,i;printf(Enter%d numbers to be sorted:,N);for(i=0;i N;i+)scanf(%d,&ai);quicksort(a,0,N-1);printf(In sorted order:);for(i=0;i=high)return;middle=split(a,low,high);quicksort(a,low,middle-1);quicksort(a,middle+1,high);97第9章：函数int split(int a,int low,int high)int part_element=alow;for(;)while(low hig

45、h&part_element=high)break;alow+=ahigh;while(low high&alow=high)break;ahigh-=alow;ahigh=part_element;return high;98第9章：函数程序：快速排序 改进此程序性能的方法：改进分割算法。采用不同的方法进行小数组排序。使得快速排序非递归。99第9章：函数汉诺塔问题一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，

46、总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。如何移动金片？此即汉诺塔（hanoi）问题。类似的有中国的九连环玩具。100第9章：函数汉诺塔问题问题的算法分析：如图，设A上有n个盘子。如果n=1，则将圆盘从A直接移动到C。如果n=2，则：1.将A上的n-1(等于1)个圆盘移到B上；2.再将A上的一个圆盘移到C上；3.最后将B上的n-1(等于1)个圆盘移到C上。如果n=3，则：A.将A上的n-1(等于2，令其为n)个圆盘移到

47、B(借助于C)，步骤如下：(1)将A上的n-1(等于1)个圆盘移到C上。(2)将A上的一个圆盘移到B。(3)将C上的n-1(等于1)个圆盘移到B。B.将A上的一个圆盘移到C。C.将B上的n-1(等于2，令其为n)个圆盘移到C(借助A)，步骤如下：(1)将B上的n-1(等于1)个圆盘移到A。(2)将B上的一个盘子移到C。(3)将A上的n-1(等于1)个圆盘移到C。到此，完成了三个圆盘的移动过程。101ABC第9章：函数汉诺塔问题 从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移

48、到C上；其中第一步和第三步是类同的。当n=3时，第一步和第三步又分解为类同的三步，即把n-1个圆盘从一个针移到另一个针上，这里的n=n-1。显然这是一个递归过程。由此可以得程序如下：102第9章：函数汉诺塔问题void move(char getone,char putone)/*打印移动信息*/printf(%c-%cn,getone,putone);void hanoi(int n,char one,char two,char three)/*递归函数递归函数*/if(n=1)move(one,three);else hanoi(n-1,one,three,two);move(one,th

49、ree);hanoi(n-1,two,one,three);main()int m;printf(Input the number of disks:);scanf(%d,&m);printf(The steps to moving%3d disks:n,m);hanoi(m,A,B,C);103第9章：函数世界何时毁灭？不管汉诺塔传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?利用递归的方法，假设有n片，移动次数是f(n)。显然f=1,f=3,f=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2n-1。n=64时：f(64)=264-1=18446744073709551615假如每秒钟一次，共需多长时间呢？一年365天有 31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615/31556952=584554049253.855年这表明移完这些金片需要5845亿年亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是100多亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。104