函数2.txt

绝对的ｐｒｉｍｅｒ的源代码 值得珍藏。第五版 外加清华讲义

函数 



内联函数 



q内联函数提高程序的运行效率
§4.内联函数 
q如输入一字符串，判断是否为数字 
p编译器为内联函
inline int isnumber(char); 

§5.重载函数 
void main() 数创建代码，替换
{ char c; 该函数

§6.默认参数的函数 
while((c=cin.get())!='\n'){ 
if(isnumber(c )) p先声明后调用

§一些实例程序 
cout <<c<<" is a digit \n"; 

else p对内联函数的函
cout <<c<<" is a non-digit \n"; 数体的限制： 


§函数的递归调用问题 
§数组应用 
} 

} ü非递归函数

§解题及程序调试 
int isnumber(char ch) ü为小函数 


{ return (ch>='0'&&ch<='9')?1:0; 

40

} 41

重载函数 



默认参数的函数 



q函数重载：对不同类型作不同运算，而有相同的函数名 
q为函数定义默认值 
void display( double a ) 

#include <iostream> 
{ cout <<a<<" a double\n";} 匹配重载函数的顺序 


using namespace std;
void display( int a ) §严格匹配 


void fun1(int a=1, intb=2 ); 

{ cout <<a<<" a int\n";} 

void fun1(int a, int b) 

void display( char a ) §内部转换后，再匹配 


{

{ cout <<a<<" a char\n";} §通过用户定义的转换寻

cout <<a<<" "<<b<<endl; 

void main( ) 求匹配 


}

{ double a; float b; 

void main()

int c; char d; short e; 

{ fun1( ); //输出1 2 

cin >>a; display(a); cin >>b; display(b); 

fun1( 5 ); //输出5 2

cin >>c; display(c); cin >>d; display(d); 

fun1(3,4); //输出3 4 

cin >>e; display(e); 

}

}

42

43


在库函数中定义的函数重载及默认参数的函数

默认参数的函数 



qvoid fun(int a, int b=2,int c=3,int d=4); 
fun(2,3,4,5); fun(2); 
fun( ); //error 
fun(2,3); 
q#include <iostream> 
using namespace std; 
void main() 
{ char a[80]; 
cin.getline(a,79); //回车时，结束字符串的读取 
cin.getline(a,79,‘*’); //遇到*时，结束字符串的读取 
cout<<a<<endl; 
} 
44

int& get(); 

istream & get( char* pch, int nCount, char delim = 
'\n' ); 

istream & get( unsigned char* puch, int nCount, 
char delim = '\n' ); 

istream & get( signed char* psch, int nCount, char 

delim = '\n' ); 

istream & get( char& rch ); 

istream & get( unsigned char& ruch ); 

istream & get( signed char& rsch ); 

istream & get( streambuf& rsb, char delim = '\n' ); 


快速排序：.. main函数

快速排序：分段交换排序 



q要排序的一组数，选取一个数（如第1个数、或中间
数）作参考数(pivot) 
q将所有数与之进行比较。凡大者置于右边，小者置
于左边，它占据应占的位置 
q将整个数组分成两部分，然后对两部分重复上述方
法，直到各数均排到相应位置为止 
pivot 
第1次交换3, 13, 12, 10, 4, 5, 11 

第2次交换.. 3, 5, 12, 10, 4, 13, 11 

3, 5, 4, 10, 12, 13, 11


46


快速排序：.. main函数 



void qsort(int item[], int left, int right) 

{ int i,j, x,y; 
i=left; j=right; 
x=item[(left+right)/2]; // x为参考数.. 
do { 

while (item[i]<x) ++i; //自左向右，找首个不小于x的元素的位置i 
while (x<item[j]) --j; //自右向左，找首个不大于x的元素的位置j 

if (i<=j){//对应位置的元素交换.. 
y=item[i]; item[i]=item[j]; 
item[j]=y; i++; j --;// i向右移1，j向左移1; 

} 
}while (i<j);//继续，直到确立了X的位置.. 
if(left<j) qsort(item, left, j); 
if(i<right) qsort(item, i, right); 

}

数字旋转方阵（续） 


#include <iostream> 

using namespace std; 

#define N 6 

int p[N][N]; 

void fill(int number, int begin, int size); 

void main() 

{ int i,j; 
fill(1,0,N); 
for(i=0;i<N;i ++){ 
for(j=0;j<N;j ++) 
cout<<p[i][j]<<'\t'; 
cout<<endl; 
} 
} 

48 


50

#include <iostream> 
#include <iomanip> 
using namespace std; 
void qsort(int item[], int left, int right); 
void main() 
{ int i,len; 


int ix[]={4,7,2,9,6,1,8,3,5}; 
len = sizeof(ix)/sizeof(int); 
qsort(ix,0,len-1); 
for(i=0;i<len;i++) 


cout <<setw(4)<<ix[i]; 
} 

数字旋转方阵


编程输出NxN的数字旋转方阵。 
6X6的方阵如图所
示 
1 2019 18 1716 
2 2132 31 3015 

q分析 
3 2233 36 2914 
|寻找数字位置的规律 
4 2334 35 2813 
5 2425 26 2712 


|先填最外层，逆时针方向； 
6 7 8 91011 
|再填第二层、第三层 
——函数递归 
|方阵的尺寸size 
|方阵的行h、列 
v 
|方阵每层起始位置的值begin 
|当前要填的数字number 
1 20 19 18 17 16 
15 2 
3 14 
4 13 
5 12 
6 7 8 9 10 11 

数字旋转方阵（续） 



void fill( int number, int begin, int size) 
{ if(size==0) 
return; 

if(size==1){ 
p[begin][begin]=number; 
return; 


} 
int h=begin, v=begin, i=0; 
p[h][v ]=number; number++; 
for(i=0;i<size-1;i++){ h++; p[h][v ]=number; number++; } 
for(i=0;i<size-1;i++){ v++; p[h][v ]=number; number++; } 
for(i=0;i<size-1;i++){ h--; p[h][v ]=number; number++; } 
for(i=0;i<size-2;i++){ v--; p[h][v ]=number; number++; } 
fill(number,v,size-2); 


} 51


打印杨辉三角形 



52
打印杨辉三角形
例：杨辉三角形中的数，为（x+y）n展开式各
项的系数
q分析：
行数i=1,…
每行的项数j：=i
每行的首项值c为1
通项值c(i, j)：=1 j=1 或j=i时
=c(i-1, j-1)+c(i-1, j) 
#include <iostream.h> 
#include <iomanip.h> 
#define N 6 
int c(int x, int y) 
{ if(( y==1)||(y==x)) 


return 1; 

return c(x-1,y-1)+c(x-1,y); 
} 
void main() 
{ int n,i,j ; cin>>n; 

for(i=1;i<=n;i++) { 
cout<<setw((n-i)*N/2)<<' '; 
for(j=1;j<=i; j++){ cout<<c(i,j)<<setw(N); } 
cout<<endl; 

} 53} 

54
打印杨辉三角形
分析：
行数i
每行的项数j：与行数一致
每行的首项值c=1；每行前的空格数
通项值c = c*(i-j+1)/j；
打印杨辉三角形的完整程序 



#include <iostream.h> 
#include <iomanip.h> 
#define N 6 
void main() 
{ short int i,j,c,n; 


cin>>n; 

for(i=0;i<n;i ++){ 
c=1; cout <<setw((n-i)*N/2)<<c; 
for(j=1;j<=i;j ++){ 


c = c*(i-j+1)/j; cout <<setw(N)<<c; } 
cout<<endl; 
} 
} 55

程序举例


程序实例：验证卡布列克运算 



例：验证卡布列克运算，即：任意四位数，只
要各位数字是不相同的，就有如下规律：

（1）将四位数字构成最大数及最小数。
（2）求最大数与最小数之差，得到新的四位数。
（3）重复以上过程，最后得到的数总是 
6174，这
个数称为卡布列克常数。 
q分析： 
|…… 
56

#include <iostream.h> 

void convert(int num, int a[]); //数拆分为4位数字 


int min(int a[]); //4位数字构成的最小数 


int max(int a[]); //4位数字构成的最大数 


void check(int num); //检验卡布列克运算 


void main() 

{ 
int n; cin>>n; 
cout <<n<<endl; 
check(n); 

} 


程序实例：验证卡布列克运算 



程序实例：验证卡布列克运算 



void check(int num) int max(int a[]) 
{ int a[4]; { int i,j,k,temp; 
if((num!=6174) && num){ for(i=0;i<4;i++){ //排序 
convert(num, a); num=max(a)-min(a); k=i; 
check(num); for(j=i+1;j<4;j++){ if(a[k ]<a[j ]) k=j; } 
} if(k!=i) { temp=a[k ]; a[k]=a[i]; a[i]=temp;} 
else if(num==6174) } 
cout <<num<<endl; temp=0; 
} for(i=0;i<4;i++) temp=temp*10+a[i]; 
void convert(int num, int a[]) return temp; 
{ int i; } 
for(i=0;i<4;i++){ int min(int a[]) 
a[i]=num%10; num/=10; { int temp=0; 
} for(int i=3;i>=0;i--) temp=temp*10+a[i]; 
} 58return temp; 59} 

本讲要点 



q掌握函数的定义和调用 
q变量的存储类型：全局变量、局部变量、静
态局部变量 
q理解并运用递归、内联、重载和默认参数 
q递归算法设计及解题 
q遗留的递归问题 
|计算组合数、青蛙过河、分书问题、下楼问题 
|跳马问题、八皇后问题
60

解题过程中的问题及程序调试 


袁帅问： 
ACM2889有关函数定义及调用 



袁帅问： 
ACM2758 


q矩阵交换行：编写一个函数，输入参数是 
5*5
的二维数组，和 
n，m两个行下标。功能：判
断n，m是否在数组范围内，如果不在，则返
回0；如果在范围内，则将 
n行和m行交换，
并返回1。在 
main函数中，生成一个 
5*5的矩
阵，输入矩阵数据，并输入 
n，m的值。调用
前面的函数。如果返回值为 
0，输出 
error。如
果返回值为1，输出交换 
n，m后的新矩阵。 
q演示—— 2889-袁帅.cpp 
q函数形参为数组的函数调用 
qDescription
菲波那契数列是指这样的数列: 数列的第一个和第二
个数都为1，接下来每个数都等于前面 
2个数之和。
给出一个正整数a，要求菲波那契数列中第 
a个数对 
1000取模的结果是多少。 
qInput
第1行是测试数据的组数n，后面跟着 
n行输入。每
组测试数据占1行，包括一个正整数 
a(1 <= a <= 
1000000)。 
qOutput 
n行，每行输出对应一个输入。输出应是一个正整
数，为菲波那契数列中第 
a个数对1000取模得到的
结果。
62


熊学禹问：我觉得没错的程序怎么交上 
ACM上老错！ 



练习题


//e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n! 求e 

#include <iostream> int fact (int n) 
#include <iomanip> 

{

using namespace std; 

if(n==1) 

int fact (int n); 
void main() return 1; 
{ int n,i;else 


double e=1,k=0; 

return

cin>>n;
for(i=1;i<=n;i++){n*fact(n-1); 
k=1/(double)fact(i); 

}

e=e+k;
} 
cout<<fixed<<setprecision(10); 
cout <<e<<endl; 
} 64

例：输入 
5×5的整型数组，输出（ 
1）每行元素之和；

（2）每行元素最大值及其位置。 
q分析： 
int a[5][5],sum[5]={0},pos[5]={0}; 
q程序框架： 
int main() 
{ int a[5][5]; 
int i , j, sum[5]={0},pos[5]={0},max; 
//Input 
for(i=0;i<5;i++){ 
for(j=0;j<5;j++){ 
cin>>a[i][j ]; 
} 


} 65

66
练习题（续）
//Calculate 
for(i=0;i<5;i++){ 
sum[i ]=0; pos[i]=0; 
for(j=0;j<5;j++){ 
sum[i ]+=a[i][j]; 
if(a[i][pos[i]]<a[i][j]) 
pos[i ]=j; 
} 
} 
//Output 
for(i=0;i<5;i++){ 
cout <<"sum:"<<sum[i ]; 
cout <<"pos"<<pos[i]+1<<endl; 
} 
} 67
练习题（续）
q程序调试
int main() 
{ int a[5][5]={{1,2,3,4,5},{5,4,3,2,1},{4,5,3,2,6},{1,3,6,2,4},{8,7,3,1,5}}; 
// int a[5][5]; 
int i,j,sum[5]={0},pos[5]={0},max; 
//Input 
/* for(i=0;i<5;i++){ 
for(j=0;j<5;j++){ 
cin>>a[i][j ]; 
} 
}*/ 
//Display for DEBUG 
for(i=0;i<5;i++){ 
for(j=0;j<5;j++) cout<<a[i][j ]<<'\t'; 
cout<<endl; 
} 
程序调试技巧 



1.将题目剪贴到当前编程窗口 
2.当输入参数比较多时，用已知数据输入，例如 
ACM
的Input 
|减少输入时间 
|预知输出结果，便于调试，与 
ACM的Output进行对比 
3.输出中间结果 
|输入数据后，立刻输出，检验读入数据是否正确 
|重要的中间数据 
4.调试完成后，将与题目 
Output无关的输出语句注释
掉 
5.注意输出格式控制
68