函数章节课程笔记
-
基础知识
函数的定义
数据类型 函数名(形势参数表)
{
函数体
}
数据类型是函数的返回值类型,若数据类型为void,是无返回值类型;
形参必须要有有类型说明,形参可以是变量名,数组名或指针名,它的作用是实现主调函数与被调函数之间的关系;
函数不允许有嵌套定义,但是允许嵌套使用.
-
-
函数的声明
类型说明符 被调函数名(含类型说明的参数表);
如果是在所有函数定义之前声明了函数原形,那么该函数原形只在本程序文件中任何的地方都有效,也就是说在本程序文件中任何地方都可以依照该原形调用相应的函数.如果是在某个主调函数内部声明了被调用函数的原形,那么该原形就只能在这个函数内部有效.
-
函数的传值调用
-
传值调用
这种调用方式是将实参的数据值传递给形参，即将实参值拷贝一个副本存放在被调用函数的栈区中。在被调用函数中，形参值可以改变，但是影响主调函数的实参值。参数传递的方向只是从实参到形参，简称单向值传递。
例如以下代码：
#include<iostream>
using namespace std;
Void swap(int a,int b)
{ int tmp=a;
a=b;
b=tmp;}
int main()
{int c=1,d=2;
swap(c,d);
cout<<c<<’ ‘<<d<<endl;
return 0;
} //程序输出为：1 2
在此例中，虽然swap函数中交换了a,b两数的值，但是在main函数中却没有交换因为swap函数只是交换c,d两变量的副本值，实参值并没有改变，并没有达到交换的目的。
-
地址传递
如果在函数定义时将形参说明成指针，调用函数时就需要指定地址形式的实参。这时的参数传递方式就是按地址传递方式。
按地址传递与按指值传递的不同在于：形参指针和实参指针指向同一个地址。因此，被调用函数中对形参指针所指向的地址中内容的任何改变都会影响到实参。
#include<iostream>
using namespace std;
void swap(int*,int*);
int main()
{ int a=3,b=4;
cout<<”a=”<<a<<”,b=”<<b<<endl;
system(“pause”);
return 0;
}
void swap(int *x,int *y)
{int t=*x;
*x=*y;
*y=t;
}
-
引用传递
如果以引用为参数，则既可以使得对形参的任何操作都能改变相应的数据，又使得函数调用显得方便，自然。引用传递方式是在函数定义时在形参前面加上引用运算符”&”。
#include<iostream>
using namespace std;
void swap(int &,int &);
int main()
{int a=3,b=4;
cout<<”a=”<<a<<”,b=”<<endl;
swap(a,b);
cout<<”a=”<<a<<”,b=”<<b<<endl;
system(“pause”);
return 0;
}
Void swap(int &x,int &y)
{int t=x;
x=y;
y=t;
}
-
-
递归算法
-
概念
当函数的定义中，其内部操作又直接间接的出现对自身的调用，则称这样的程序嵌套定义为递归定义。
函数直接调用其自身，称为直接递归；函数间接调用其自身，称为间接递归。
-
简单的说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。
在递归程序的递归过程中，一般具有如下模式：
将调用程序的返回地址，相应的调用前的变量都保存在系统栈队中。
执行被调用的函数.
若满足退出递归的条件,则退出递归,并从栈顶上弹回返回地址，取回保存起来的变量值，继续沿着返回地址，向下执行程序；
否则继续递归调用，只是递归调用的参数发生变化：增加一个量或减少一个量，重复执行直到递归调用结束。
-
能够用递归算法解决的问题，一般满足如下要求：
需要求解的问题可以化为子问题求解，其子问题的求解方法与原问题相同之时规模上的增加或减少；
递归调用的次数是有限的，必须有递归结束的条件（称为递归边界）
-
-
2．经典例题
（1）函数的简单题
① 以验证哥德巴赫猜想为例
验证“歌德巴赫猜想”，即：任意一个大于2的偶数均可表示成两个素数之和。
输入
输入只有一个正整数x。(x是偶数，x <= 2000且 x > 2)
输出
输出这个数的所有分解形式，形式为：
x = y + z
其中x为待验证的数，y和z满足y + z = x，而且 y<= z，y和z均是素数。
如果存在多组分解形式，则按照y的升序输出所有的分解，每行一个分解表达式。
Codeing
#include <iostream>
#include <cmath>
using namespace std;
int main()
{void godbaha(int);
int n;
cin>>n;
godbaha(n);
return 0;
}
void godbaha(int n)
{int prime(int);
int a,b;
for(a=3;a<=n/2;a=a+2)
{if(prime(a))
{b=n-a;
if(prime(b))
cout<<n<<" "<<"="<<""<<a<<" "<<"+"<<" "<<b<<endl;}
}
}
int prime(int m)
{int i,k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0) break;
if (i>k) return1;
else return 0;
}
这道题定义了两个函数，一个是哥德巴赫猜想的输出形式，其次就是 素数的判断方法。
②求两个正整数的最大公约数
输入
两个正整数
输出
最大公约数
Codeing
#include<iostream>
using namespace std;
int gcd(int,int);
int main()
{ int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
return 0;
}
int gcd(int x,int y)
{ int g;
if(y==0) g=x;
else g=gcd(y,x%y);
return g;
}
这道题用到了递归的简单算法，在函数中调用了自身
这种求最大公约数的算法就叫做 辗转相除法
求m%n的余数
如果余数不为0，则让m=n,n=余数，重复上一步，
如果余数为0，则终止调用子程序
此时输出n的值；
③求两个正整数的最小公倍数
描述
输入两个正整数，求最小公倍数
输入
两个正整数
输出
最小公倍数
Codeing
#include<iostream>
using namespace std;
int gad(int,int);
int main()
{ int a,b;
cin>>a>>b;
cout<<(a*b)/gad(a,b)<<endl;
return 0;
}
int gad(int x,int y)
{ int g;
if(y==0) g=x;
else g=gad(y,x%y);
return g;
}
最小公倍数=两个数的乘积/最大公约数
（2）递归算法的题目
描述
给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1<= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a= a也是一种分解。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)
输出
n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数
样例输入
2
2
20
样例输出
1
4
Codeing
#include<iostream>
using namespace std;
int find(int a,int b)
{
int sum=0;
if(a==1) return 1;
for(int i=b;i<=a;i++)
if(a%i==0)
{sum+=find(a/i,i);}
return sum;
}
int main()
{int n,a,i;
cin>>n;
for(i=1;i<=n;++i)
{cin>>a;
cout<<find(a,2)<<endl;}
return 0;
}
这道题运用了递归算法，把可能的方式一一枚举出来即可
②八皇后的问题
描述
在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。
输入
无输入。
输出
按给定顺序和格式输出所有八皇后问题的解（见Sample Output）。
样例输入
样例输出
No. 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
No. 2
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
……
Codeing
#include<bits/stdc++.h>
using namespace std;
int b[101]={0},c[101]={0},d[101]={0};
int a[101];
int sum=0;
int print();
int search(int i);
int main()
{search(1);//从第一个皇后开始
return 0;}
int search(int i)
{
for(int j=1;j<=8;j++)//每个皇后都有八个位置可以摆放
{if((b[j]==0)&&(c[i+j]==0)&&(d[i-j+7]==0))//寻找方皇后的位置，d数组的下标不能为负，可以通过+7来比较
{a[i]=j;//摆放皇后，表示的是第i行第j列放了皇后
b[j]=1;//下面的bool类型表示的是宣布占领
c[i+j]=1;
d[i-j+7]=1;
if(i==8)
{sum++;
print();
}
else search(i+1);//继续递归之下一个
b[j]=0;//回溯一步
c[i+j]=0;
d[i-j+7]=0;
}
}
}
int print()
{cout<<"No. "<<sum<<endl;
for(int j=1;j<=8;++j)
{for(int i=1;i<=8;++i)
if(j==a[i]) cout<<1<<" ";
else cout<<0<<" ";
cout<<endl;
}
}
这道题运用到了回溯的方法
可以从矩阵的特点上找到规律
如果在同一行则行号相同，同一列则列号相同
，在/对角线上，则行列之和相同，在\对角线上，则行列之差的绝对值相同；
3.学习心得
对于函数部分 我觉得首先是一个在调试程序时，方便的方法，
对于程序的运行时间，占用内存并无帮助，还有传值调用不能返回两个值，可以用传引用和传地址的方式来实现
然后，是递归算法的那一部分，我觉得递归算法最重要的一个部分是找到递归表达式，也就是找到问题与问题之间的联系，还有就是找到递归边界，比如算一个数的阶乘，可以转化为 1！=1，0！=1，
int Factorial(int n)
{
if(n==1)
return 1;
return n*Factorial(n-1);
-
}
这样 可以看到 递归的问题边界是n==1，递归表达式是n*factorial(n-1)；
递归算法中还有就是 搜索与回溯，比如八皇后的问题，在考虑这个问题的时候，要想到 八个皇后只能独占一列一行两个方向的对角线，那么我们可以这样考虑 要将所在的位置用bool类型的数组定义占领，还要继续向下一步搜寻，最后回溯一步，就完成。
再比如著名的斐波那契数列
题目大体意思是 后一项数的大小等于前两项的数之和
1 1 2 3 5 8 13……
那么这个程序可以这样来写
1. int fib2(int n)
2. {
3. if(n == 0)
4. return 0;
5. if(n == 1)
6. return 1;
7. return fib2(n-1)+fib2(n-2);
8. }