1
实际问题
1,用弦截法求方程的根
2,Hanoi(汉诺 )塔问题
2
用弦截法求方程的根设方程为：
f(x) = x3 - 5x2 + 16x - 80 = 0
用弦截法求方程的根图示
4
用弦截法求方程根的算法
1,选取两个不同点 x1,x2,使得
f(x1)*f(x2)<0;
2,计算弦与 x轴的交点 x；
3,若 f(x)与 f(x1)同符号，将 x作为新的 x1。
若 f(x)与 f(x2)同符号，则将 x作为新的 x2。
4,重复步骤 2和 3,直到｜ f(x)｜＜ ξ为止,
ξ为一个很小的正数,例如 10-6。此时认为
f(x)≈0。
5
问题分解和模块化
寻找根的区间：
f(x1)*f(x2)<0
计算函数值：
f(x) = x3 - 5x2 + 16x - 80
计算弦与 x轴的交点 x：
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
用弦截法逼近方程根：
｜ f(x)｜＜ ξ
6
模块化程序设计的优点
分而治之
代码可重用
抽象技术
便于实现
易于维护
7
模块化程序设计 图示主模块模块 1 模块 2 模块 3
模块 4
模块 6 模块 7
模块 5
模块化程序设计第 4章 函数
9
本章学习目标
通过本章学习，你能够
了解模块化程序设计
能够分解复杂问题
能够创建模块 (函数 )
能够使用模块 (函数 )
10
本章主要内容
函数定义和调用
函数间参数传递
递归函数
C++标准库函数
本章作业
内联函数
函数重载
函数模板
默认参数 (略 )
11
实例 1模块化
寻找根的区间：
f(x1)*f(x2)<0
计算函数值：
f(x) = x3 - 5x2 + 16x - 80
计算弦与 x轴的交点 x：
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
用弦截法逼近方程根：
｜ f(x)｜＜ ξ
定义函数（创建模块）
模块,f(x) = x3 - 5x2 + 16x - 80
double f(double x)
{
return x*(x*(x-5)+16)-80;
}
调用函数（使用模块）
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
int main()
{
...
y1=f(x1); y2=f(x2);
x=(x1*y2-x2*y1)/(y2-y1);
...
}
14
函数定义的格式返回值类型 函数名 (形式参数表 )
{
函数体
}
模块接口实现模块功能数据传递
15
关于函数定义的说明
函数名：
标识函数，表明函数功能，与变量名命名规则相同
函数形参：
传递数据，必须是变量，不能是表达式
返回值类型 (函数类型 )：
返回给上一层模块的数据的类型
通过 return实现
如果无返回值，则函数类型为 void
函数体：实现函数的功能
16
函数设计要求
执行单一的、明确的任务
函数名表达其任务内聚性强、耦合性弱
17
函数调用
double f(double x); // 函数原型
main()
{
...
y1=f(x1); y2=f(x2); //调用函数
x=(x1*y2-x2*y1)/(y2-y1);
...
}
18
关于函数调用的说明
1,调用前要给出函数原型：
类型 函数名 (形参表 );
例,double f(double x);
2,函数调用的形式：
函数名 (实参 表 );
例,f(10),f(a),f(10+a)
实参：可以是常量、变量或表达式
19
函数调用中的类型问题
按函数原型的参数类型强制转换例：
double maximum( int,int,int );
double x;
x = maximum(1.1,2.1,3.1);
x?
20
函数原型的作用
编译程序用以 检验函数的调用,以避免因错误调用而导致运行时错误：
返回值的类型
参数的个数
参数的类型
参数的顺序
21
函数调用的执行过程
main()
调用 f(x)
结束
f(x)
返回
① ②
④
⑥
⑦
保存：
返回地址当前现场
③
恢复：
主调程序现场返回地址
⑤
22
函数调用中的程序控制
主调函数 (caller)，通过函数名进入被调函数
被调函数 (callee)通过以下途径返回主调函数：
return
函数结束部分的右大括号
Demo
23
函数的参数传递
两种途径：
1,按值传递
被调函数生成 形参
实参值被复制到 形参
形参 的改变不会改变 实参
2,按引用传递
形参使用实参的存储空间
形参的改变会改变实参
两种途径均有各自的优缺点
24
函数参数的 按值 传递
在函数被调用时形参被分配存储单元。
实参可以是常量、变量或表达式。
数据只能从实参传递给形参，即 单向传递 。
当实参类型与形参不同时，按形参类型转换。
虚实结合：一一对应 (类型、个数、顺序 )
25
例：输入两整数交换后输出
void swap(int a,int b);
int main()
{
int x(5),y(10);
cout<<"x="<<x<<"y="<<y<<endl;
swap(x,y);
cout<<"x="<<x<<"y="<<y<<endl;
return 0;
}
void swap(int a,int b)
{
int t;
t=a; a=b; b=t;
cout<<"a="<<a<<"b="<<b<<endl;
}
运行结果,
x=5 y=10
a=10 b=5
x=5 y=10 原因何在？
27
按值传递
void swap( int,int );
void main(void)
{ int x(5),y(10);
…
swap(x,y);
…
}
void swap( int a,int b)
{
…
}
5x
a
x,y
为实参
a,b
为形参
10y
b
28
函数参数的 按引用 传递
在函数被调用时不为形参分配存储单元，
形参使用实参空间。
实参不能是常量或表达式，只能是变量，
而且类型必需与形参类型一致。
实参和形参共享数据，即 双向传递 。
29
何谓引用？
引用是标识符的 别名例如,
int i=10;
int &ri=i; //引用 ri是变量 i的一个别名
ri=100; // i?
声明一个引用时，必须同时对它进行初始化。
一个引用一旦被初始化后，就 不能改为其它对象的引用 。
30
例：输入两整数交换后输出
void swap(int &a,int &b);
int main()
{
int x(5),y(10);
cout<<"x="<<x<<"y="<<y<<endl;
swap(x,y);
cout<<"x="<<x<<"y="<<y<<endl;
return 0;
}
void swap(int &a,int &b)//函数定义
{
int t;
t=a; a=b; b=t;
cout<<"a="<<a<<"b="<<b<<endl;
}
运行结果,
x=5 y=10
a=10 b=5
x=10 y=5 原因何在？
32
函数参数按引用传递
void swap( int &,int &);
void main(void)
{ int x(5),y(10);
…
swap(x,y);
…
}
void swap( int &a,int &b)
{
…
}
5x
a
x,y
为实参
a,b
为形参
10y
b
33
模块化程序设计
设计
自上而下
编码
自下而上定义函数：计算弦与 x轴的交点 x
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
int main()
{
...
y1=f(x1); y2=f(x2);
x=(x1*y2-x2*y1)/(y2-y1);
...
}
定义函数：计算弦与 x轴的交点 x
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
...
double xpoint(double x1,double x2)
{
double y1,y2;
y1=f(x1); y2=f(x2);
return (x1*y2-x2*y1)/(y2-y1);
}
定义函数：用弦截法求方程的根
int main()
{
...//假设已测试得到根存在的区间,x1,x2
y1=f(x1);
do
{ x=xpoint(x1,x2);
y=f(x);
if (y*y1>0)
{ x1=x; y1=y;}
else
x2=x;
}while(fabs(y)>=1e-6);
cout<<"方程的根是,"<<x;
}
定义函数：用弦截法求方程的根
double root(double x1,double x2)
{
double x,y,y1;
y1=f(x1);
do
{ x=xpoint(x1,x2);
y=f(x);
if (y*y1>0)
{ x1=x; y1=y;}
else
x2=x;
}while(fabs(y)>=1e-6);
return x;
}
用弦截法求方程的根
int main( )
{
double x1,x2,f1,f2,x;
do
{ cout<<"input x1,x2,";
cin>>x1>>x2;
f1 = f(x1); f2 = f(x2);
} while(f1*f2>=0);
x = root(x1,x2);
cout<<″A root of equation is ″<<x<<endl;
return 0;
}
39
函数的嵌套调用 (demo)
40
实例
1,用弦截法求方程的根 (已解决 )
2,Hanoi(汉诺 )塔问题
41
汉诺塔问题有三根针 A,B,C。 A针上有 N个盘子，大的在下，小的在上，要求把这 N个盘子从 A针移到 C针，在移动过程中可以借助 B针，每次只允许移动一个盘，且在移动过程中在三根针上都保持大盘在下，小盘在上。
A B C
42
递归算法计算 n!的递归算法如下：
注：其迭代算法为：
n!=1*2*3*..*(n-1)*n
)0()!1(
)0(1
!
nnn
n
n
43
递归算法
由两部分组成：
1,已知部分
解基本情形,n!=1（ n=0）
2,未知部分
与原始问题类似，但更简单或更小：
n!=n*(n-1)!,n>0
44
递归算法
递归算法的两个过程：
1,递推：
4!=4× 3! → 3!=3× 2! → 2!=2× 1! → 1!=1
未知 已知
2,回归：
4!=4× 3!=24← 3!=3× 2!=6← 2!=2× 1!=2← 1!=1
未知 已知
45
用 递归函数 实现递归算法
int fac( int n )
{
if ( n == 1 )
return 1;
else
return ( n * fac( n - 1 ) );
}
基本情形更简单的原始问题
46
递归过程演示
5!
5*4!
4*3!
3*2!
2*1!
1
返回 5*24=120
返回 4*6=24
返回 3*2=6
返回 2*1=2
返回 1
将 n 个盘子从 A针移到 C针的三个步骤：
1,将 A 上 n-1个盘子移到 B针上（借助 C针） ;
2,把 A针上剩下的一个盘子移到 C针上 ;
3,将 n-1个盘子从 B针移到 C针上（借助 A针） ;
汉诺塔问题的递归算法：
A B C
void hanoi(int n,char A,char B,char C)
{
if (n==1)
move (A,C);
else
{ hanoi (n-1,A,C,B); //步骤 1
move(A,C); //步骤 2
hanoi(n-1,B,A,C); //步骤 3
}
}
汉诺塔问题的递归函数
49
void move(char getone,char putone)
{
cout<< getone <<"-->"<<putone<<endl;
}
汉诺塔递归算法步骤 2的函数
void hanoi(int,char,char,char );// 函数原型
void main()
{
int m;
cout<<"Enter the number of diskes:";
cin>>m;
cout<<"the steps to
moving"<<m<<"diskes:"<<endl;
hanoi(m,'A','B','C');// 调用函数
}
汉诺塔问题递归算法源程序
Enter the number of diskes,3
the steps to moving 3 diskes:
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
运行结果 (Demo)
52
递归函数的常见错误
忽略了基本情形，或错误地编写了递归步，以致程序无法运行到基本情形，而导致无限递归，最终内存耗尽。
忘记从递归函数中返回
53
递归与迭代的比较
int fac(int n) //求 n!的 迭代算法
{
int f=1;
for ( int i = 1; i <= n; i ++)
f *= i;
return f;
}
54
递归与迭代的比较
软件工程
递归方法更加自然、易于理解和调试
迭代方法的解决方案不明显
程序性能
递归方法占用更多的时间和内存
55
C++标准库
设计库来扩充功能要好过设计更多的语法。
——— C++之父 Bjarne Stroustrup
现实中,C++的库门类繁多，解决的问题也是极其广泛，库从轻量级到重量级的都有。不少都是让人眼界大开，亦或是望而生叹的思维杰作。
56
C++标准库函数
不属于 C++语言
由编译系统提供
分类：
数学函数（ math.h）
字符串函数（ string.h）
输入 /输出函数（ stdio.h）
,..
57
查找 C++库函数
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
->Run Time Routines by Category
-> by Category
58
查找 C++库函数
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
-> C++ Standard Library
-> Standard C++ Library Contents
59
库函数原型
使用预处理命令,# include
将 # include指定的文件内容包含进来两种形式：
# include "文件名 "
或 # include <文件名 >
60
预处理命令 #include
#include "文件名 "：
系统先在引用被包含文件的源文件 所在的文件目录中寻找要包含的文件，若找不到，再按系统指定的标准方式检索其它目录。
#include <文件名 >：
直接按系统指定的标准方式检索目录
61
C++改进
使用命名空间,namespace
解决名字污染问题
cmath：
namespace std {#include <math.h> };
把 <math.h>标准头文件包含在 std名字空间中。
62
C++标准库函数使用举例
实例：
从键盘输入一个角度值，求出该角度的正弦、
余弦值和正切值。
分析：
库函数中提供了求正弦值、余弦值和正切值的函数,sin(),cos(),tan()，函数的说明在头文件 math.h中。
#include<cmath>
using namespace std;
const double pi(3.14159265);
void main()
{
double a,b;
cin>>a;
b=a*pi/180;
cout<<"sin("<<a<<")="<<sin(b)<<endl;
cout<<"cos("<<a<<")="<<cos(b)<<endl;
cout<<"tan("<<a<<")="<<tan(b)<<endl;
}
运行结果：
30
sin(30)=0.5
cos(30)=0.866025
tan(30)=0.57735
65
内联 (inline)函数
不影响模块化程序设计
提高了程序性能但增加了程序大小
限定符 inline
在函数调用处复制被调用函数代码
编译器可能忽略 inline 限定符
除了最小的函数
任何对内联函数的改变都可能要求调用函数重新编译
66
C++对 #define的替代
inline函数：
替代带参数的宏
常变量 (const)
替代不带参数的宏 (符号常量 )
模板 (template)
替代带参数的宏
inline 函数示例
inline double f(double x)
{
return x*(x*(x-5)+16)-80;
}
int main()
{
double y;
for ( int k = 0; k < 10; k++ ) {
y += f( k );//10次函数调用
}
return 0;
}
68
函数重载
目的：
模块功能相同
但是数据不同
需要不同的模块
特点：
函数名相同
参数不同：类型、个数
69
函数重载示例
int square( int x ) { return x * x; }
double square( double y ) { return y * y; }
int main()
{
cout << "The square of integer 7 is " << square( 7 )
<< "\nThe square of double 7.5 is " << square( 7.5 )
<< endl;
return 0;
}
The square of integer 7 is 49
The square of double 7.5 is 56.25
70
函数模板
一种有效的编程工具：
生成若干重载函数
使用关键字
template
71
函数模板举例
template < class T >
T square( T val)
{
return val * val;
}
72
函数重载示例
template < class T >
T square( T x ) { return x * x; }
int main()
{
cout << "The square of integer 7 is " << square( 7 )
<< "\nThe square of double 7.5 is " << square( 7.5 )
<< endl;
return 0;
}
The square of integer 7 is 49
The square of double 7.5 is 56.25
73
函数模板
编译器 根据以下函数参数类型
square( 7 )
square( 7.5 )
将模板中的 T替换为 int和 double类型生成两个函数：
int square( int x ) { return x * x;}
double square(double x ){return x * x;}
函数模板示例
template < class T >
T maximum( T value1,T value2,T value3 )
{
T max = value1;
if ( value2 > max )
max = value2;
if ( value3 > max )
max = value3;
return max;
}
int main()
{
int i1,i2,i3;
double d1,d2,d3;
char c1,c2,c3;
...
cout <<,..<<maximum( i1,i2,i3 );
cout <<,..<<maximum( d1,d2,d3 );
cout <<,..<<maximum( c1,c2,c3 );
...
}
Input three integer values,1 2 3
The maximum integer value is,3
Input three double values,3.3 2.2 1.1
The maximum double value is,3.3
Input three characters,A C B
The maximum character value is,C
76
C++标准模板库
Standard Template Library
缩写 STL
中文翻译：标准模板库
77
查找 C++标准模板库
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
-> C++ Standard Library
-> Standard C++ Library Contents
具有 STL标记
78
本章小结
模块化程序设计
函数定义和调用
函数间参数传递
递归函数
标准函数
内联函数
函数重载
函数模板
79
本章作业
实验 4
复习第 4章，预习第 5章
习题,1,3,6,7,8,9,10，
11
80
第 2次大作业 (截止日期,4月 24日 )
1,编写函数 mySqrt(x)
计算平方根
2,编写函数 mySin(x)
计算三角函数 sin(x)
3,编写程序：定积分 (矩形法 )
计算以上函数注：精度或步长自定，积分区间为 [0,1]。
x
81
牛顿迭代法计算平方根
axxf 2)(
82
牛顿迭代法计算平方根
根号 a实际上就是 x^2-a=0的一个正实根
不断用 (x,f(x))的切线来逼近方程 x^2-a=0
的根
该函数的导数是 2x，函数上任一点 (x,f(x))处的切线斜率是 2x。
x-f(x)/(2x)是一个比 x更接近的近似值。
代入 f(x)=x^2-a得到近似值 (x+a/x)/2。
85
默认参数
在函数原型中设置默认参数
int add( int x=1,int y=2,int z=3 );
a = add();
b = add(2);
c = add(2,3);
cout<<a<<b<<c<<endl;
实际问题
1,用弦截法求方程的根
2,Hanoi(汉诺 )塔问题
2
用弦截法求方程的根设方程为：
f(x) = x3 - 5x2 + 16x - 80 = 0
用弦截法求方程的根图示
4
用弦截法求方程根的算法
1,选取两个不同点 x1,x2,使得
f(x1)*f(x2)<0;
2,计算弦与 x轴的交点 x；
3,若 f(x)与 f(x1)同符号，将 x作为新的 x1。
若 f(x)与 f(x2)同符号，则将 x作为新的 x2。
4,重复步骤 2和 3,直到｜ f(x)｜＜ ξ为止,
ξ为一个很小的正数,例如 10-6。此时认为
f(x)≈0。
5
问题分解和模块化
寻找根的区间：
f(x1)*f(x2)<0
计算函数值：
f(x) = x3 - 5x2 + 16x - 80
计算弦与 x轴的交点 x：
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
用弦截法逼近方程根：
｜ f(x)｜＜ ξ
6
模块化程序设计的优点
分而治之
代码可重用
抽象技术
便于实现
易于维护
7
模块化程序设计 图示主模块模块 1 模块 2 模块 3
模块 4
模块 6 模块 7
模块 5
模块化程序设计第 4章 函数
9
本章学习目标
通过本章学习，你能够
了解模块化程序设计
能够分解复杂问题
能够创建模块 (函数 )
能够使用模块 (函数 )
10
本章主要内容
函数定义和调用
函数间参数传递
递归函数
C++标准库函数
本章作业
内联函数
函数重载
函数模板
默认参数 (略 )
11
实例 1模块化
寻找根的区间：
f(x1)*f(x2)<0
计算函数值：
f(x) = x3 - 5x2 + 16x - 80
计算弦与 x轴的交点 x：
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
用弦截法逼近方程根：
｜ f(x)｜＜ ξ
定义函数（创建模块）
模块,f(x) = x3 - 5x2 + 16x - 80
double f(double x)
{
return x*(x*(x-5)+16)-80;
}
调用函数（使用模块）
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
int main()
{
...
y1=f(x1); y2=f(x2);
x=(x1*y2-x2*y1)/(y2-y1);
...
}
14
函数定义的格式返回值类型 函数名 (形式参数表 )
{
函数体
}
模块接口实现模块功能数据传递
15
关于函数定义的说明
函数名：
标识函数，表明函数功能，与变量名命名规则相同
函数形参：
传递数据，必须是变量，不能是表达式
返回值类型 (函数类型 )：
返回给上一层模块的数据的类型
通过 return实现
如果无返回值，则函数类型为 void
函数体：实现函数的功能
16
函数设计要求
执行单一的、明确的任务
函数名表达其任务内聚性强、耦合性弱
17
函数调用
double f(double x); // 函数原型
main()
{
...
y1=f(x1); y2=f(x2); //调用函数
x=(x1*y2-x2*y1)/(y2-y1);
...
}
18
关于函数调用的说明
1,调用前要给出函数原型：
类型 函数名 (形参表 );
例,double f(double x);
2,函数调用的形式：
函数名 (实参 表 );
例,f(10),f(a),f(10+a)
实参：可以是常量、变量或表达式
19
函数调用中的类型问题
按函数原型的参数类型强制转换例：
double maximum( int,int,int );
double x;
x = maximum(1.1,2.1,3.1);
x?
20
函数原型的作用
编译程序用以 检验函数的调用,以避免因错误调用而导致运行时错误：
返回值的类型
参数的个数
参数的类型
参数的顺序
21
函数调用的执行过程
main()
调用 f(x)
结束
f(x)
返回
① ②
④
⑥
⑦
保存：
返回地址当前现场
③
恢复：
主调程序现场返回地址
⑤
22
函数调用中的程序控制
主调函数 (caller)，通过函数名进入被调函数
被调函数 (callee)通过以下途径返回主调函数：
return
函数结束部分的右大括号
Demo
23
函数的参数传递
两种途径：
1,按值传递
被调函数生成 形参
实参值被复制到 形参
形参 的改变不会改变 实参
2,按引用传递
形参使用实参的存储空间
形参的改变会改变实参
两种途径均有各自的优缺点
24
函数参数的 按值 传递
在函数被调用时形参被分配存储单元。
实参可以是常量、变量或表达式。
数据只能从实参传递给形参，即 单向传递 。
当实参类型与形参不同时，按形参类型转换。
虚实结合：一一对应 (类型、个数、顺序 )
25
例：输入两整数交换后输出
void swap(int a,int b);
int main()
{
int x(5),y(10);
cout<<"x="<<x<<"y="<<y<<endl;
swap(x,y);
cout<<"x="<<x<<"y="<<y<<endl;
return 0;
}
void swap(int a,int b)
{
int t;
t=a; a=b; b=t;
cout<<"a="<<a<<"b="<<b<<endl;
}
运行结果,
x=5 y=10
a=10 b=5
x=5 y=10 原因何在？
27
按值传递
void swap( int,int );
void main(void)
{ int x(5),y(10);
…
swap(x,y);
…
}
void swap( int a,int b)
{
…
}
5x
a
x,y
为实参
a,b
为形参
10y
b
28
函数参数的 按引用 传递
在函数被调用时不为形参分配存储单元，
形参使用实参空间。
实参不能是常量或表达式，只能是变量，
而且类型必需与形参类型一致。
实参和形参共享数据，即 双向传递 。
29
何谓引用？
引用是标识符的 别名例如,
int i=10;
int &ri=i; //引用 ri是变量 i的一个别名
ri=100; // i?
声明一个引用时，必须同时对它进行初始化。
一个引用一旦被初始化后，就 不能改为其它对象的引用 。
30
例：输入两整数交换后输出
void swap(int &a,int &b);
int main()
{
int x(5),y(10);
cout<<"x="<<x<<"y="<<y<<endl;
swap(x,y);
cout<<"x="<<x<<"y="<<y<<endl;
return 0;
}
void swap(int &a,int &b)//函数定义
{
int t;
t=a; a=b; b=t;
cout<<"a="<<a<<"b="<<b<<endl;
}
运行结果,
x=5 y=10
a=10 b=5
x=10 y=5 原因何在？
32
函数参数按引用传递
void swap( int &,int &);
void main(void)
{ int x(5),y(10);
…
swap(x,y);
…
}
void swap( int &a,int &b)
{
…
}
5x
a
x,y
为实参
a,b
为形参
10y
b
33
模块化程序设计
设计
自上而下
编码
自下而上定义函数：计算弦与 x轴的交点 x
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
int main()
{
...
y1=f(x1); y2=f(x2);
x=(x1*y2-x2*y1)/(y2-y1);
...
}
定义函数：计算弦与 x轴的交点 x
x = x1·f(x2) - x2·f(x1)
f(x2) - f(x1)
...
double xpoint(double x1,double x2)
{
double y1,y2;
y1=f(x1); y2=f(x2);
return (x1*y2-x2*y1)/(y2-y1);
}
定义函数：用弦截法求方程的根
int main()
{
...//假设已测试得到根存在的区间,x1,x2
y1=f(x1);
do
{ x=xpoint(x1,x2);
y=f(x);
if (y*y1>0)
{ x1=x; y1=y;}
else
x2=x;
}while(fabs(y)>=1e-6);
cout<<"方程的根是,"<<x;
}
定义函数：用弦截法求方程的根
double root(double x1,double x2)
{
double x,y,y1;
y1=f(x1);
do
{ x=xpoint(x1,x2);
y=f(x);
if (y*y1>0)
{ x1=x; y1=y;}
else
x2=x;
}while(fabs(y)>=1e-6);
return x;
}
用弦截法求方程的根
int main( )
{
double x1,x2,f1,f2,x;
do
{ cout<<"input x1,x2,";
cin>>x1>>x2;
f1 = f(x1); f2 = f(x2);
} while(f1*f2>=0);
x = root(x1,x2);
cout<<″A root of equation is ″<<x<<endl;
return 0;
}
39
函数的嵌套调用 (demo)
40
实例
1,用弦截法求方程的根 (已解决 )
2,Hanoi(汉诺 )塔问题
41
汉诺塔问题有三根针 A,B,C。 A针上有 N个盘子，大的在下，小的在上，要求把这 N个盘子从 A针移到 C针，在移动过程中可以借助 B针，每次只允许移动一个盘，且在移动过程中在三根针上都保持大盘在下，小盘在上。
A B C
42
递归算法计算 n!的递归算法如下：
注：其迭代算法为：
n!=1*2*3*..*(n-1)*n
)0()!1(
)0(1
!
nnn
n
n
43
递归算法
由两部分组成：
1,已知部分
解基本情形,n!=1（ n=0）
2,未知部分
与原始问题类似，但更简单或更小：
n!=n*(n-1)!,n>0
44
递归算法
递归算法的两个过程：
1,递推：
4!=4× 3! → 3!=3× 2! → 2!=2× 1! → 1!=1
未知 已知
2,回归：
4!=4× 3!=24← 3!=3× 2!=6← 2!=2× 1!=2← 1!=1
未知 已知
45
用 递归函数 实现递归算法
int fac( int n )
{
if ( n == 1 )
return 1;
else
return ( n * fac( n - 1 ) );
}
基本情形更简单的原始问题
46
递归过程演示
5!
5*4!
4*3!
3*2!
2*1!
1
返回 5*24=120
返回 4*6=24
返回 3*2=6
返回 2*1=2
返回 1
将 n 个盘子从 A针移到 C针的三个步骤：
1,将 A 上 n-1个盘子移到 B针上（借助 C针） ;
2,把 A针上剩下的一个盘子移到 C针上 ;
3,将 n-1个盘子从 B针移到 C针上（借助 A针） ;
汉诺塔问题的递归算法：
A B C
void hanoi(int n,char A,char B,char C)
{
if (n==1)
move (A,C);
else
{ hanoi (n-1,A,C,B); //步骤 1
move(A,C); //步骤 2
hanoi(n-1,B,A,C); //步骤 3
}
}
汉诺塔问题的递归函数
49
void move(char getone,char putone)
{
cout<< getone <<"-->"<<putone<<endl;
}
汉诺塔递归算法步骤 2的函数
void hanoi(int,char,char,char );// 函数原型
void main()
{
int m;
cout<<"Enter the number of diskes:";
cin>>m;
cout<<"the steps to
moving"<<m<<"diskes:"<<endl;
hanoi(m,'A','B','C');// 调用函数
}
汉诺塔问题递归算法源程序
Enter the number of diskes,3
the steps to moving 3 diskes:
A-->C
A-->B
C-->B
A-->C
B-->A
B-->C
A-->C
运行结果 (Demo)
52
递归函数的常见错误
忽略了基本情形，或错误地编写了递归步，以致程序无法运行到基本情形，而导致无限递归，最终内存耗尽。
忘记从递归函数中返回
53
递归与迭代的比较
int fac(int n) //求 n!的 迭代算法
{
int f=1;
for ( int i = 1; i <= n; i ++)
f *= i;
return f;
}
54
递归与迭代的比较
软件工程
递归方法更加自然、易于理解和调试
迭代方法的解决方案不明显
程序性能
递归方法占用更多的时间和内存
55
C++标准库
设计库来扩充功能要好过设计更多的语法。
——— C++之父 Bjarne Stroustrup
现实中,C++的库门类繁多，解决的问题也是极其广泛，库从轻量级到重量级的都有。不少都是让人眼界大开，亦或是望而生叹的思维杰作。
56
C++标准库函数
不属于 C++语言
由编译系统提供
分类：
数学函数（ math.h）
字符串函数（ string.h）
输入 /输出函数（ stdio.h）
,..
57
查找 C++库函数
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
->Run Time Routines by Category
-> by Category
58
查找 C++库函数
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
-> C++ Standard Library
-> Standard C++ Library Contents
59
库函数原型
使用预处理命令,# include
将 # include指定的文件内容包含进来两种形式：
# include "文件名 "
或 # include <文件名 >
60
预处理命令 #include
#include "文件名 "：
系统先在引用被包含文件的源文件 所在的文件目录中寻找要包含的文件，若找不到，再按系统指定的标准方式检索其它目录。
#include <文件名 >：
直接按系统指定的标准方式检索目录
61
C++改进
使用命名空间,namespace
解决名字污染问题
cmath：
namespace std {#include <math.h> };
把 <math.h>标准头文件包含在 std名字空间中。
62
C++标准库函数使用举例
实例：
从键盘输入一个角度值，求出该角度的正弦、
余弦值和正切值。
分析：
库函数中提供了求正弦值、余弦值和正切值的函数,sin(),cos(),tan()，函数的说明在头文件 math.h中。
#include<cmath>
using namespace std;
const double pi(3.14159265);
void main()
{
double a,b;
cin>>a;
b=a*pi/180;
cout<<"sin("<<a<<")="<<sin(b)<<endl;
cout<<"cos("<<a<<")="<<cos(b)<<endl;
cout<<"tan("<<a<<")="<<tan(b)<<endl;
}
运行结果：
30
sin(30)=0.5
cos(30)=0.866025
tan(30)=0.57735
65
内联 (inline)函数
不影响模块化程序设计
提高了程序性能但增加了程序大小
限定符 inline
在函数调用处复制被调用函数代码
编译器可能忽略 inline 限定符
除了最小的函数
任何对内联函数的改变都可能要求调用函数重新编译
66
C++对 #define的替代
inline函数：
替代带参数的宏
常变量 (const)
替代不带参数的宏 (符号常量 )
模板 (template)
替代带参数的宏
inline 函数示例
inline double f(double x)
{
return x*(x*(x-5)+16)-80;
}
int main()
{
double y;
for ( int k = 0; k < 10; k++ ) {
y += f( k );//10次函数调用
}
return 0;
}
68
函数重载
目的：
模块功能相同
但是数据不同
需要不同的模块
特点：
函数名相同
参数不同：类型、个数
69
函数重载示例
int square( int x ) { return x * x; }
double square( double y ) { return y * y; }
int main()
{
cout << "The square of integer 7 is " << square( 7 )
<< "\nThe square of double 7.5 is " << square( 7.5 )
<< endl;
return 0;
}
The square of integer 7 is 49
The square of double 7.5 is 56.25
70
函数模板
一种有效的编程工具：
生成若干重载函数
使用关键字
template
71
函数模板举例
template < class T >
T square( T val)
{
return val * val;
}
72
函数重载示例
template < class T >
T square( T x ) { return x * x; }
int main()
{
cout << "The square of integer 7 is " << square( 7 )
<< "\nThe square of double 7.5 is " << square( 7.5 )
<< endl;
return 0;
}
The square of integer 7 is 49
The square of double 7.5 is 56.25
73
函数模板
编译器 根据以下函数参数类型
square( 7 )
square( 7.5 )
将模板中的 T替换为 int和 double类型生成两个函数：
int square( int x ) { return x * x;}
double square(double x ){return x * x;}
函数模板示例
template < class T >
T maximum( T value1,T value2,T value3 )
{
T max = value1;
if ( value2 > max )
max = value2;
if ( value3 > max )
max = value3;
return max;
}
int main()
{
int i1,i2,i3;
double d1,d2,d3;
char c1,c2,c3;
...
cout <<,..<<maximum( i1,i2,i3 );
cout <<,..<<maximum( d1,d2,d3 );
cout <<,..<<maximum( c1,c2,c3 );
...
}
Input three integer values,1 2 3
The maximum integer value is,3
Input three double values,3.3 2.2 1.1
The maximum double value is,3.3
Input three characters,A C B
The maximum character value is,C
76
C++标准模板库
Standard Template Library
缩写 STL
中文翻译：标准模板库
77
查找 C++标准模板库
编译系统的库函数手册
VC++6.0联机帮助的使用方法：
help/Contents
->(“活动子集”栏 )Visual C++ Documentation
-> Visual C++ Documentation
->Using Visual C++
-> Visual C++ Programmer's Guide
-> Run-Time Library Reference
-> C++ Standard Library
-> Standard C++ Library Contents
具有 STL标记
78
本章小结
模块化程序设计
函数定义和调用
函数间参数传递
递归函数
标准函数
内联函数
函数重载
函数模板
79
本章作业
实验 4
复习第 4章，预习第 5章
习题,1,3,6,7,8,9,10，
11
80
第 2次大作业 (截止日期,4月 24日 )
1,编写函数 mySqrt(x)
计算平方根
2,编写函数 mySin(x)
计算三角函数 sin(x)
3,编写程序：定积分 (矩形法 )
计算以上函数注：精度或步长自定，积分区间为 [0,1]。
x
81
牛顿迭代法计算平方根
axxf 2)(
82
牛顿迭代法计算平方根
根号 a实际上就是 x^2-a=0的一个正实根
不断用 (x,f(x))的切线来逼近方程 x^2-a=0
的根
该函数的导数是 2x，函数上任一点 (x,f(x))处的切线斜率是 2x。
x-f(x)/(2x)是一个比 x更接近的近似值。
代入 f(x)=x^2-a得到近似值 (x+a/x)/2。
85
默认参数
在函数原型中设置默认参数
int add( int x=1,int y=2,int z=3 );
a = add();
b = add(2);
c = add(2,3);
cout<<a<<b<<c<<endl;
