1
上次作业中的问题
思路不清,尤其是迭代法
两种理解:
1,计算完这一次,还要为下一次准备数据。
2,每次都要完成的工作,除了按照迭代公式(方法)处理数据以外,还有其它的步骤。
对于多重穷举,要一层一层地来,别忘了在循环体中加上必要的{}
第 5部分多函数程序设计
3
先看一个大型实例
程序的结构:
编译预处理命令
其它必要的定义
其它函数声明
主函数
其它函数定义
结论:
C程序是由很多个函数组成的。
C语言中关于函数有三个主要内容:
函数定义
函数调用
函数声明
4
为什么定义函数?
大型任务总要由多人完成,因此,在编程之前,一定要将任务划分成多个功能独立的 模块,再分别分配给多个程序分别编程实现。
函数可以 复用,以节省开发时间。每个函数,就象一块雕刻好的积木,可以直接用来构建新的程序。
5
模块化的几个原则
模块分解的原则
保证模块的相对独立性
高聚合:一个模块只能完成单一的功能,代码一般几十行。
低耦合:指模块之间参数传递尽量少,尽量不通过全局变量来实现数据传递
信息隐藏
把所有用户不需要关心的细节隐藏至模块内部。
6
我们怎么做?
关键是如何 "分段 "。
比较独立的、完整的功能分为一个函数,
一般函数十几行。
函数定义时注意与被调函数之间的沟通与联系,即参数传递与返回两个方向的数据流动。
在讲例题的时候请注意这两点
7
例 1:定义一个函数,求梯形面积
先完成一个数学函数的定义:
s(a,b,h)=(a+b)*h/2
自变量
函数名
函数公式
编写函数必须考虑的三个内容:
先来考虑这个任务需要什么必要的数据,都是什么类型?( 形式参数 )
有没有结果,结果又是什么类型?( 返回值 )
应该完成什么功能?如何实现?( 函数功能 )
8
分析结果
/*函数 功能,求梯形面积函数 形式参数,
float a表示上底
float b表示下底
float h表示高函数 返回值,梯形面积( float类型)
*/
9
涉及的语法
- 函数定义 格式
/*函数功能:实现 ×××× 功能函数形式参数:参数 1,表示 ×××××
参数 2,表示 ×××××
...
函数返回值,×××××
*/
返回值类型 函数名 (形式参数列表 )
{
函数体
}
养成注释的好习惯:
10
函数定义
/*函数功能:求梯形面积函数参数,float a表示上底,float b表示下底,float h表示高函数返回值:梯形面积 */
float Area(float a,float b,float h)
{
int s = (a+b)*h/2 ;
return s;
}
三个 形式参数返回值 类型函数名称返回语句函数体函数定义相当于建立一个
s(a,b,h)=(a+b)*h/2这样一个函数的形式化表示,此时 没有具体的数值,只有 代入数值才能计算出数值。
11
在 main函数中怎样 调用 呢?
#include<stdio.h>
float s(float,float,float);/*函数声明 */
float s(float a,float b,float h)
{
return (a+b)*h/2;
}
void main()
{ float a,b,h,area;
printf(" please input a,b,h,");
scanf("%f%f%f",&a,&b,&h);/*假设输入的数据是 1,2,3*/
area= s(a,b,h); /*函数调用,相当于数学函数的代入,a,b,h有确切的数值,因此称为 实参,函数的返回值赋值给 area,相当于计算 area=s(1,2,3)*/
printf(" area=%f\n",area);
}
12
运行过程
#include<stdio.h>
float s(float,float,float);/*函数声明 */
float s(float a,float b,float h)
{
return (a+b)*h/2;
}
void main()
{ float a,b,h,area;
printf(" please input a,b,h,");
scanf("%f%f%f",&a,&b,&h);
area= s(a,b,h); /*实参向形参单向传递数值 */
printf(" area=%f\n",area);
}
printf(" area=%f\n",s(a,b,h) );
13
涉及的语法
- 函数调用 ( call)
调用即使用已经定义好的函数。
调用函数时,必须提供所有的参数
printf和 scanf是采用变长变量表定义的函数,
所以变量的个数不固定。
提供的参数 个数、类型、顺序 应与定义时相同
单向 值传递
14
涉及的语法
-函数调用格式
函数调用的一般形式:
函数名(实参列表)
具体调用格式:
有返回值时
放到一个数值表达式中,如 area = s(a,b,h);
作为另一个函数调用的参数,如
printf("area=%f\n",s(a,b,h) );
或者直接参与运算:如:
F= pow(a,b) *c
无返回值时
函数调用表达式,如 printf("hello!");
注意,main()函数可以调用其它函数,但它不可以被其它函数调用。即:它只能作为 主调函数,不能作为 被调函数
15
涉及的语法
- 函数原型 或 函数声明
调用一个函数之前,先要对其返回值类型、
函数名和参数进行声明( declare)
不对函数进行声明是非常危险的
声明时不要省略参数以及返回值的类型
一般都写在编译预处理命令之后。
16
函数的分类
从使用角度:
库函数,直接使用 (调用 )
自定义函数:用户需要自己先定义,然后使用。
根据返回值:
有返回值:需要返回计算结果
无返回值:不需要返回计算 (处理 )结果
根据参数:
无参函数,clrscr()
有参函数,pow(x,y)
17
函数声明
函数声明 也称为 函数原型
在调用之前一定要对函数进行声明,否则在编译时会出现 "function ***
not define!"的提示
如果函数定义在函数调用之前,函数声明可以省略。
18
也可以写成
#include<stdio.h>
/*函数功能:计算梯形面积并输出函数形式参数,float a表示上底,float b表示下底,float h
表示高函数 返回值:无 */
void Area(float a,float b,float h)
{
printf("area=%f",(a+b)*h/2);
}
void main()
{ float a,b,h;
printf(" please input a,b,h,");
scanf("%d%d%d",&a,&b,&h);
Area(a,b,h); /*调用函数计算面积并输出 */
}
19
多函数程序的调试方法
要想检验一个函数是否正确,要在调用函数处设置断点。当调试执行时,在该行停止,此时,点击 build->step into
进入函数内部执行,此时可点击 build-
>step over单步跟踪执行,或在调试前在函数内部重点检查语句行设置断点。
若想结束函数内部的执行,点击 build-
>step out,回到主调函数。
20
练习 1:编写函数,将 小写字母转换成大写字母#include <stdio.h>
char atoA(char);/*函数声明 */
/* 函数功能:将小写字母转换成大写字母函数形式参数:小写字母 char lower
函数返回值:转换成的大写字母,char类型 */
char atoA(char lower)
{
return (lower-32);
}
void main()
{
char lower,upper;
printf(" please input an lowercase,");
scanf("%c",&lower);
upper= atoA(lower);
printf(" lower:%c->upper:%c\n",lower,upper);
}
21
#include <math.h>
#include <stdio.h>
int Prime(int m)/*判断 m是否为素数,是返回 1,否返回 0*/
{ int i,find = 0,k = sqrt(m);
for (i=2; i<=k && !find; i++)
{ if (m % i == 0)
find = 1;
}
return !find;
}
void main()
{ int m;
for (m=2; i<=100; m++)
{ if (Prime(m))
printf("Yes! %d is a prime!\n",m);
else
printf("No!%d is not a prime!\n",m);
}
}
例 2:判断 2-100
之间哪些是素数算法?
22
练习 2:求两个数最大公约数
#include <stdio.h>
int Gcd(int,int); /*函数声明 */
int Gcd(int a,int b)/*函数功能:求两数的最大公约数 */
{ int c;
do{
c=a%b;
a=b;
b=c;
}while(c!=0);
return a;
}
void main()
{ int a,b,c;
printf("please enter two integers:");
scanf("%d%d",&a,&b);
printf("the greatest common divisor is %d\n",Gcd(a,b));
}
23
小结 1
要求
能够编写 多函数 程序,编写函数之前要写清楚注释
(包括函数功能,函数形参,函数返回值)
会调用函数,理解函数的调用过程和整个程序的执行顺序
理解数据在函数调用过程中和返回时的流动。
应掌握的语法内容
函数的定义、调用、声明格式 (重点中的重点)
24
作业 1
定义一个求 n!的函数,并在主函数中调用它,计算 1!+… +m!.
定义两个函数,分别计算圆的周长和面积,并在主函数中调用这两个函数。
25
#include <stdio.h>
double Fac(int n);
void main()
{
int i,n; double sum;
printf("please input n:");
scanf("%d",&n);
for(i=1,sum=0;i<=n;i++)
sum+=Fac(i);
printf("1!+… +%d!=%lf\n",n,sum);
}
double Fac(int n)/*函数功能:求 n!*/
{int i;
double fac;
for(i=1,fac=1;i<=n;i++)
{
fac*=i;
}
return fac;
}
作业答案
26
#include <stdio.h>
#define PI 3.14
float l(float); /*函数声明 */
float s(float); /*函数声明 */
float l(float r) /*函数定义:求周长 */
{return PI*r*2; }
float s(float r) /*函数定义:求面积 */
{ return PI*r*r; }
void main()
{ float r,l,s;
printf("please input r:");
scanf("%f",&r);
l=l(r); /*函数调用 */
s=s(r); /*函数调用 */
printf("circumference=%7.2f\n,area=%7.2f\n",l,s);
}
问题若这样起名会怎样?
会有错误提示,
因为相同的名字造成了冲突。
27
#include <stdio.h>
#define PI 3.14
float l(float); /*函数声明 */
float s(float); /*函数声明 */
float l(float r) /*函数定义:求周长 */
{return PI*r*2; }
float s(float r) /*函数定义:求面积 */
{ return PI*r*r; }
void main()
{ float r,cir,area;
printf("please input r:");
scanf("%f",&r);
cir =l(r); /*函数调用 */
area =s(r); /*函数调用 */
printf("circumference=%7.2f\n,area=%7.2f\n",cir,area);
}
问题若这样起名又会怎样?会冲突吗?
不会,它们虽然是不同的 r,但因为它们的 作用域 不同,所以不会产生冲突。
28
涉及的语法
-作用域
作用域:即作用范围
可分为:
局部变量
全局变量
29
局部变量
局部变量
在语句块内 (即 { }内 )定义的变量
形式参数也是局部变量
特点
定义时不会自动初始化,除非程序员指定初值
进入语句块时获得内存,仅能由语句块内语句访问,退出语句块时释放内存,不再有效
并列语句块各自定义的同名变量互不干扰
30
main()
{ int i=1,j=2;
printf(″i=%d,j=%d\n″,i,j);
{int i=3,a=4; printf(″i=%d,a=%d\n″,i,a);
j++;
}
{int i=5; printf(″i=%d\n″,i);
j++;
}
printf(″i=%d,j=%d\n″,i,j);
}
运行结果为:
i=1,j=2
i=3,a=4
i=5
i=1,j=4
例,运行结果? ++是一个 运算符,j++表示将 j变量的值加 1
31
例 3,运行结果?
#include <stdio.h>
void swap(int x,int y); /* 函数声明 */
void main( )
{ int a=3,b=5;
printf("11>a=%d,b=%d\n",a,b);/* 调用交换函数之前 */
swap(a,b); /* 调用交换函数 swap */
printf("12>a=%d,b=%d\n",a,b);/* 调用交换函数之后 */
}
/* 函数定义:交换两个变量的值的函数 */
void swap(int a,int b)
{ int temp;
printf("21> a=%d,b=%d\n",a,b); /* 交换变量值之前 */
temp=a; a=b; b=temp; /* 交换器:交换变量 x,y的值 */
printf("22> a=%d,b=%d\n",a,b); /* 交换变量值之后 */
}
3 5
a b
3 5
a b
temp 3
5 3
实参 a,b的值 没发生变化 !
单向值传递 !
即由实参向形参的方向传递数值 !而不会朝相反的方向 !
32
全局变量
全局变量
在所有函数之外定义的变量
特点
默认 作用范围:在源程序,c中,从定义它的位置以后都有效
在定义点之前或在其他,c文件中引用,应该进行如下声明:
extern 类型名 变量名 ;
从程序运行起即占据内存,程序运行过程中可随时访问,程序退出时释放内存
使函数之间的数据交换更容易,也更高效
但是尽量少用,因为谁都可以改写全局变量,所以很难确定是谁改写了它
破坏了函数的独立性 (封装性 )
33
#include <stdio.h>
int global; /*定义全局变量 */
void GlobalPlusPlus(void);
main()
{
global = 1;
printf("Before GlobalPlusPlus(),it is %d\n",global);
GlobalPlusPlus();
printf("After GlobalPlusPlus(),it is %d\n",global);
}
/* 函数功能,对 全局变量 global加 1,并打印加 1之前与之后的值函数入口参数,无函数返回值,无
*/
void GlobalPlusPlus(void)
{
printf("Before ++,it is %d\n",global);
global++;
printf("After ++,it is %d\n",global);
}
例 4-1Before GlobalPlusPlus(),it is 1
Before ++,it is 1
After ++,it is 2
After GlobalPlusPlus(),it is 2
注意:全局变量具有 "记忆性
" 。
34
#include <stdio.h>
void GlobalPlusPlus(void);
main()
{
int global = 1;
printf("Before GlobalPlusPlus(),it is %d\n",global);
GlobalPlusPlus();
printf("After GlobalPlusPlus(),it is %d\n",global);
}
/* 函数功能,对 局部变量 global加 1,并打印加 1之前与之后的值函数入口参数,无函数返回值,无
*/
void GlobalPlusPlus(void)
{
int global = 1;
printf("Before ++,it is %d\n",global);
global++;
printf("After ++,it is %d\n",global);
}
例 4-2Before GlobalPlusPlus(),it is 1Before ++,it is 1
After ++,it is 2
After GlobalPlusPlus(),it is 1
35
如何用全局变量解决例 3
#include <stdio.h>
int a=3,b=5;
void swap(void); /* 函数声明 */
void main( )
{ printf("11> a=%d,b=%d\n",a,b);/* 调用交换函数之前 */
swap(); /* 调用交换函数 swap */
printf("12> a=%d,b=%d\n",a,b);/* 调用交换函数之后 */
}
void swap(void ) /* 函数定义,没有参数 */
{ int temp;
printf("21> a=%d,b=%d\n",a,b); /* 交换变量值之前 */
temp=a; a=b; b=temp; /* 交换变量 a,b的值 */
printf("22> a=%d,b=%d\n",a,b); /* 交换变量值之后 */
}
虽然得以解决,但并不是一个好办法 !
为什么?
因为它破坏了函数的封闭性 !
学指针的时候我们会学另外一种方法 !
即便要用全局变量,一般也是在只读不写的时候才用 !
36
例:使用全局变量解决
#include <stdio.h>
#define PI 3.14
float r;
float l( void ); /*函数声明 */
float s(void); /*函数声明 */
float l(void) /*函数定义:求周长 */
{return PI*r*2; }
float s(void) /*函数定义:求面积 */
{ return PI*r*r; }
void main()
{ float cir,area;
printf("please input r:");
scanf("%f",&r);
cir =l( ); /*函数调用 */
area =s( ); /*函数调用 */
printf("circumference=%7.2f\n,area=%7.2f\n",cir,area);
}
r一旦被赋值,其值不再发生变化,只是拿来用。
37
另一个具有 "记忆性 "的变量类型,静态变量( static)
一般的内部变量
在函数退出后失效,再次进入函数,变量值重新初始化
静态变量
在变量类型前面用 static修饰
static int i;
变量存在 静态存储区,当函数结束时,内存空间不被释放,因此,变量的值可以保存到下次进入函数,即变量具有记忆功能
38
涉及的语法
-变量的 存储类型
编译器为变量分配内存的方式
它决定变量的生存期程序存储区静态 存储区动态 存储区 形参、自动变量、函数调用的现场等全局变量、
静态变量
动态存储
根据需要临时分配存储空间,离开即释放
静态存储
在程序运行期间分配固定的存储空间不释放内存分配
39
根据存储类型可分为
自动变量 (auto)
静态变量 (static)
寄存器变量 (register)
40
例 -静态变量
#include <stdio.h>
void Func(void);
void main()
{ int i;
for (i=0; i<10; i++)
{ Func();
}
}
/* 函数功能,打印被调用的次数函数入口参数,无函数返回值,无
*/
void Func(void)
{ static int times = 1; /*静态局部变量 函数结束时 times变量仍然占据静态存储区的存储空间,不释放 */
printf("Func() was called %d time(s).\n",times++);
}
Func() was called 1 time(s).
Func() was called 2 time(s).
Func() was called 3 time(s).
Func() was called 4 time(s).
Func() was called 5 time(s).
Func() was called 6 time(s).
Func() was called 7 time(s).
Func() was called 8 time(s).
Func() was called 9 time(s).
Func() was called 10 time(s).
1times 2310
41
例 -非静态变量
#include <stdio.h>
void Func(void);
void main()
{ int i;
for (i=0; i<10; i++)
{ Func();
}
}
/* 函数功能,打印被调用的次数函数入口参数,无函数返回值,无
*/
void Func(void)
{ int times = 1;
printf("Func() was called %d time(s).\n",times++);
}
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
Func() was called 1 time(s).
1times 2 1times 2
42
自动变量 ( auto )
我们以前定义的那些变量,都默认是这种类型
"自动 "体现在
进入语句块时自动申请内存,退出时自动释放内存
标准定义格式
auto 类型名 变量名 ;
特点:
动态局部变量
缺省的存储类型
不初始化时,值是不确定的
43
寄存器变量( register)
寄存器
CPU的内部容量很有限、但速度极快的存储器
使用频率比较高的变量声明为 register,
可以使程序更小,执行速度更快
register 类型名 变量名 ;
register int i;
现代编译器有能力自动把普通变量优化为寄存器变量,并且可以忽略用户的指定,所以一般无需特别声明变量为 register
44
静态变量和全局变量
相同点:都是静态存储类型
自动初始化为 0
都存储在静态存储区,整个程序运行期间一直占据内存
不同点:作用域不同
全局变量在所有的源程序文件中都可用
静态变量又分为静态局部变量和静态全局变量,作用域分别是所在函数和所在源文件
45
读程序功能
#include <stdio.h>
double Fac(int n);
void main()
{
int i,n; double result;
printf("please input n:");
scanf("%d",&n);
for(i=1,result=1;i<=n;i++)
{ result =Fac(i);
printf("result=%lf\n",result);
}
}
double Fac(int n)
{static double fac=1;
fac*=n;
}
程序功能:
求 1-n的阶乘
分析:
虽然函数中只乘了一个数,但由于是 static变量,所以,记住,
了以前乘的结果
46
#include<stdio.h>
int square(int i);
void main()
{int i=0;
i=square(i);
for(;i<3;i++)
{static int i=1;
i+=square(i);
printf("%d,",i);
}
printf("%d\n",i);
}
int square(int i)
{return i*i;}
读程序结果
0i
1i 2
1
6
2
42
3
输出结果:
2,6,342,
注意:搞清楚三个 I的作用域和存储类型。
47
小结 2
按变量作用域,可分为局部变量和全局变量。
一般情况下用局部变量,局部变量可以重名,
不冲突,但各自为政。
极少情况下,当需要考虑到数据的一致性时可以用全局变量。全局变量具有记忆性,所以,
一般不随意修改它的值。
按存储类型分:可分为 auto,static、
register变量。
static 具有记忆性,一般用做局部变量。
auto,register一般不用 。
48
例 5
例:求 n!= 1 n=1
n*(n-1)! n>1
long fac(int n)
{ if(n==1)
return 1;
else
return n*fac(n-1);
}
写成函数?
49
例 5程序
#include<stdio.h>
long fac(int n)
{ if(n==1)
return 1;
else
return n*fac(n-1);
}
main()
{int n;
Printf("please input a number:\n");
scanf("%d",&n);
printf(″%2d!=%ld″,n,fac(n));
}
f(10)
{…
retrun 10*f(9 );
… }
f(9)
{…
retrun 9*f(8 );
… }
f(1)
{…
return 1;
… }
f(2)
{…
return 2*f(1);
… }

执行过程?
调用函数 递推依次返回 回归
递归:函数嵌套调用自身
50
递归 迭代
long int fac(int n)
{ if(n<=1)
return 1;
else
return n*fac(n-1);
}
long int fac(int n)
{Long fc=1; int i;
for(i=1;i<=n;i++);
fc=fc*i;
return fc;
}n!= 1 n=1
n*(n-1)! n>1 n!=(… ((1*2)*3)… *n)
51
递归与迭代的比较递 归 迭 代控制结构 选择结构 循环结构终止条件 边界条件 循环条件求解方向 n?n-1?…?1 1?2?…?n
优点 解题思路简单缺点 递归调用执行过程复杂,
效率低效率高例,n!= 1 n=1
n*(n-1)! n>1
n!=(… ((1*2)*3)… *n)
52
什么问题可以用递归来解决?
问题具有如下特点:
问题较复杂,不易用迭代法直接求解
该问题可以分解成若干子问题,子问题除了规模较原问题小以外,其它均相同。
最终,总有一个问题不能再分解。
复杂问题 边界问题
n n=1或 2规模减小依次递推求得复杂问题的解
53
例 5-4 求解 Hanoi(汉诺)塔问题
古代有一个梵塔,塔内有三个柱子 A,B、
C,僧侣们想把 A拄子上的一摞盘子移动到 C柱子上。最初 A拄子上有大小不等的
64个盘子,且小的在上,大的在下。在移动过程中,大盘子只能在下,小盘子只能在上,并且每次只能移动一个盘子,
可以借助于 B柱子。
6463
62
1
A B C
54
问题分析
解决 Hanoi(汉诺)塔问题的方法可以表述如下:
⑴老和尚移动 64个盘子的步骤第 1步,请第 2个和尚将前 63个盘子从 A柱子移到 B柱子;
第 2步,自己将最下面的第 64个盘子从 A柱子移到 C柱子;
第 3步,再请第 2个和尚将 63个盘子从 B柱子移到 C柱子。
⑵第 2个和尚移动 63个盘子的步骤第 1步,请第 3个和尚将前 62个盘子从 A柱子移到 C柱子;
第 2步,自己将最下面的第 63个盘子从 A柱子移到 B柱子;
第 3步,再请第 3个和尚将 62个盘子从 C柱子移到 B柱子。
依此类推,直到第 63个和尚完成了 2个盘子的移动,最后由第 64个和尚完成 1个盘子的移动。这个过程称之为 "回推 "过程。
每个人的工作是:移动 n个盘子从 A到 B(借助 C)的步骤
第 1步,请别人将 n-1个盘子从 A柱子移到 C柱子;
第 2步,自己将最下面的第 n个盘子从 A柱子移到 B
柱子;
第 3步,再请别人将 n-1个盘子从 C柱子移到 B柱子。
一个特例:当 n==1的时候
55
move函数
/* 定义函数:显示移动过程
int no:表示第 no个盘子
char from:表示源柱子
char to:表示目的柱子
*/
void move(int no,char from,char to)
{
printf("Move %3dth disk:%c ->%c\n",no,from,to);
}
56
hanoi函数
/* 定义函数:
借助 by柱子将 n个盘子从 from柱子移动到 to柱子
int n:表示 n个盘子 char from:表示源柱子
char to:表示目的柱子,char by:表示要借助的柱子
*/
void hanoi(int n,char from,char by,char to)
{ if (n==1)
move(n,from,to);
else
{ hanoi(n-1,from,to,by);
move(n,from,to);
hanoi(n-1,by,from,to);
}
}
57
#include <stdio.h> /* 包含头文件 */
void move(int,char,char); /* 自定义函数的声明 */
void hanoi(int n,char,char,char); /* 自定义函数的声明 */
void main() /* 主函数,无参数,无返回值 */
{ int n; /* 定义整型变量 n,存放盘子总数 */
printf("Input the number of diskes,"); /* 提示输入 n的值 */
scanf("%d",&n); /* 输入 n的值 */
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C'); /* 借助 B柱子将 n个盘子从 A移到 C */
}
/* 定义函数:显示第 no个盘子的移动过程,从 from到 to */
void move(int no,char from,char to)
{
printf("Move %3d,%c ――> %c\n",no,from,to);
}
/* 定义函数:借助 by柱子将 n个盘子从 from柱子移动到 to柱子 */
void hanoi(int n,char from,char by,char to)
{ if (n==1)
move(n,from,to);
else
{ hanoi(n-1,from,to,by);
move(n,from,to);
hanoi(n-1,by,from,to);
}
}
完整程序
执行过程?
作业:请大家用讲过的单步执行方法观察一下 n为 3的执行过程
58
运行输出:
Input the number of disks:
3
The step to moving 3 disks:
Move 1,A --> B
Move 2,A --> C
Move 3,B --> C
Move 4,A --> B
Move 5,C --> A
Move 6,C --> B
Move 7,A --> B
59
语法:函数的 递归调用
在调用一个函数的过程中又直接或间接地调用函数本身
f( )
{…
f( );
… }
f1( )
{…
f2( );
… }
f2( )
{…
f1( );
… }
特殊形式的函数嵌套重点直 接递归 间 接递归
60
练习 3:写递归函数计算
fabonacci数列的第 n项
fib(n)=
n ( n= 0,1) /* 递归结束条件 */
fib(n-2)+ fib(n-1) ( n>1) /* 递归方式 */
61
练习 3程序
#include<stdio.h>
long fib(int n); /* 自定义函数声明 */
void main()
{ long s; /* 第 i 项斐波那契数列的值 */
int i=0; /* 斐波那契数列某项的序号 */
do
{ s=fib(i); /* 求斐波那契数列第 i 项 */
printf("Fib(%d)=%ld\n",i,s); /* 显示斐波那契数列第 i 项的值 */
printf("Input Fibonacci Number,0 means exiting:");
scanf("%d",&i); /* 输入要求的某一项的序号 */
}while(i>0); /* 循环输入序号,直到 i值小于等于 0 */
}
/* 定义求第 n项斐波那契数列值的函数 */
long fib(int n)
{ if(n==0||n==1) /* 判断是否为结束条件 */
return n;
else
return fib(n-2)+fib(n-1); /* 求斐波那契数列的递归方式 */
}
62
带参数的宏定义
#define SQUARE(n) ((n)*(n))
void main()
{ int i=1;
for( ;i<=10;i++)
printf("%4d",SQUARE(i) );
}
void main()
{ int i=1;
for( ;i<=10;i++)
printf("%4d",((i)*(i)) );
}
编译前替换为:
63
区别使用函数 使用带参数的宏定义
int SQUARE(int n)
{
return(n*n);
}
#define SQUARE(n) ((n)*(n))
void main()
{
int i=1;
for( ;i<=10;i++)
printf("%4d",SQUARE(i));
}
void main()
{
int i=1;
for( ;i<=10;i++)
printf("%4d",SQUARE(i) );
}
((i)*(i))
当函数功能非常简单时,可以用带参数的宏定义来实现。
64
涉及语法
-带参数的宏定义
一般格式:
#define 宏名 (参数表 ) 字符序列
功能,将程序中出现的前者置换为后者。
其中宏名后面的括号里是参数,类似函数中形参表,只是此处的形参无类型说明。字符序列中应包含括号中所指定的参数,否则参数设置无意义。
65
应注意的问题
使用带参数的宏定义可以实现某些简单函数的功能(注意是某些,而不是全部)。
定义时,宏名和参数表之间不能有空格。
对带参数的宏定义,字符序列及其字符序列中各个形参都应该用圆括号括起来。
例,#define SQUARE(n) ((n)*(n))
#define s (a,b,c) a*b*c
main()
{
printf("%d",s( 3+5,5/2,2+3));
}
3+5*5/2*2+3#define f(x,y) (x)+(y)
main()
{int a=4,b=3;
printf("%d",f(a,b)*f(a,b) );
}
)+(b)*(a)+(b)
(a)*(b)*(c)
((a)+(b))
66
函数相关知识小结
多函数程序设计
为什么定义函数?怎样编写多函数的 C程序
函数的定义、调用、声明格式
理解函数的调用过程(程序的执行过程)
什么情况下用递归?递归的解题思路是什么?递归的执行过程是什么?递归与递推有何区别?
变量的作用域和存储类型
如何分类?各具有什么特点?什么情况下用全局变量和 static变量。
带参数的宏定义
用法,以及与函数的区别
67
作业 2:
分别用递归法和迭代法求解 (都要写成函数 ):
S(x,n)=x1+x2+… +xn;
自学例题:求解 Hanoi(汉诺)塔问题。关键是要搞清楚递归函数的写法 (即如何将 n的问题转化为 n-1的问题 ),以及递归调用的过程 (输入 3试跟踪一下调用过程 )
68
作业 2答案
问题的关键是如何 将 n的问题化解为 n-1
的问题 (即 反方向求解问题 )。
根据分析,写出如下的数学函数:

1!),()1,(
1
),(
nnxpo wnxs
nx
nxs
double S(float x,int n)
{if(n==1)
return x;
else
return S(x,n-1)+pow(x,n);
}/*若函数定义为 float,会有类型不一致的警告 */
69
#include<stdio.h>
#include<math.h>
double S(float x,int n);
void main()
{ double x,s; int n;
printf("please input x,n:\n");
scanf("%lf,%d",&x,&n);
s=S(x,n);
printf("\nS(%lf,%d)=%lf\n",x,n,s);
}
double S(double x,int n)
{if(n==1)
return x;
else
return S(x,n-1)+pow(x,n);
/*递归要通过函数的依次调用实现 */
}
习题 5.12程序
#include<stdio.h>
#include<math.h>
double S(float x,int n);
void main()
{ double x,s; int n;
printf("please input x,n:\n");
scanf("%lf,%d",&x,&n);
s=S(x,n);
printf("\nS(%lf,%d)=%lf\n",x,n,s);
}
double S(double x,int n)/*用递推求解 */
{double sum=0;
int i;
for(i=1;i<=n;i++)/*递推要用循环语句实现 */
sum+=pow(x,i);
return sum;
}
切忌,
将递归函数的内容写至主函数中;
将递归中的语句放至循环中;
在递归函数中写 s(x,n)=S(x,n-1)+pow(x,n);
70
Hanoi(3,’A’,’B’,’C’)
{
......
else
{ hanoi(2,’A’,’C’,’B’);
move(n,’A’,’C’);
hanoi(2,’B’,’A’,’C’);
}
}
Hanoi(2,’A’,’C’,’B’)
{
......
else
{ hanoi(1,’A’,’B’,’C’);
move(n,’A’,’B’);
hanoi(1,’C’,’A’,’B’);
}
}
Hanoi(1,’A’,’B’,’C’)
{
......
move(1,’A’,’C’);
}21
3
4
5
6
7
Hanoi(1,’C’,’A’,’B’)
{
......
move(1,’C’,’B’);
}
8 9
1011
Hanoi(2,’B’,’A’,’C’)
{
......
else
{ hanoi(1,’B’,’C’,’A’);
move(n,’B’,’C’);
hanoi(1,’A’,’B’,’C’);
}
}
Hanoi(1,’B’,’C’,’A’)
{
......
move(1,’B’,’A’);
}
14
15
16
17
18
Hanoi(1,’A’,’B’,’C’)
{
......
move(1,’A’,’C’);
}
19
20
21
22
12
13