递归二
-
递归不仅包括函数直接调用自身，还可以多函数互相调用，形成间接调用
eg.求表达式的值
# include<iostream> using namespace std; //因为要相互调用，所以要提前声明 double expression_value(); double factor_value(); double term_value(); double expression_value(){ double result = term_value(); //保证把所有的项都读到；所以用一个while循环，里面没必要用while用了不知道为什么是错的 while(true){ //cin.peek()是从输入流里看一看，而不取走这个字符 char op = cin.peek(); if(op=='+') { getchar(); result += term_value(); } if(op=='-') { getchar(); result -= term_value(); } else if(op != '+' && op!='-'){ break; } } return result; } double term_value(){ double result = factor_value(); while(true){ char ch = cin.peek(); if(ch == '*'){ getchar(); result *= factor_value(); } if(ch=='/'){ getchar(); result /= factor_value(); } else if(ch != '*'&&ch != '/'){ break; } } return result; } double factor_value(){ double result = 0; char ch = cin.peek(); if(ch == '('){ getchar(); result = expression_value(); getchar(); }else{ while(isdigit(ch)){ //isdigit()是判断是不是数字 result = result*10 + ch-'0'; cin.get(); ch = cin.peek(); } } return result; } int main(){ //其实整个读入输入的过程都是在factor_value里面进行的 cout << expression_value() << endl; }
-
递推公式的问题——注意边界情况
爬楼梯：
# include<iostream>
using namespace std;
int stairs(int n){
if (n <= 0) return 0;
if(n==1) return 1;
if(n==2) return 2;
return stairs(n-1) + stairs(n-2);
}
int main(){
int n;
cin >> n;
cout << stairs(n);
}
放苹果——m个苹果放到n个盘子里
# include<iostream>
using namespace std;
int f(int m,int n){
if(n>m) return f(m,m);
//0个剩余，说明有了一种放法C_n ^0 =1
if(m == 0) return 1;
if(n == 0) return 0;
//有空盘+无空盘
return f(m-n,n) + f(m,n-1);
}
int main(){
int m,n;
cin >> m,n;
cout << f(m,n);
}
算24
输入5个整数，计算他们能否通过四则运算得到24；
# include<iostream>
# include<cmath>
//double没有==
# define EPS 1e-8
using namespace std;
int comput_24(double a[],int len){
//终止条件
if(len == 1){
if(fabs(a[0]-24) < EPS) return 1;
}else if(len == 1){
return 0;
}
double temp[6];
//其实还是枚举
for(int i = 0;i<len-1;i++){
for(int j = i+1;j<len;j++){
//p用来指示b中有多少数
int p = 0;
// 把不参与四则运算的 放到temp里面
for(int k= 0;k<len;k++){
if(k != i && k != j){
temp[p] = a[k];
p++;
}
}
//下面注意，加法和乘法有交换律，除法和减法没有
temp[p] = a[i]+a[j];
if(comput_24(temp,p+1) ){
return true;
}
temp[p] = a[i]*a[j];
if(comput_24(temp,p+1) ){
return true;
}
if(a[i] != 0){
temp[p] = a[j]/a[i];
if(comput_24(temp,p+1) ){
return true;
}
}
//而且除法还要注意，分母不为零
if(a[j] != 0){
temp[p] = a[i]/a[j];
if(comput_24(temp,p+1) ){
return true;
}
}
temp[p] = a[i]-a[j];
if(comput_24(temp,p+1) ){
return true;
}
temp[p] = a[j]-a[i];
if(comput_24(temp,p+1) ){
return true;
}
}
}
return false;
}
int main(){
double a[5];
//int b[5];
for(int i = 0;i<5;i++){
cin >> a[i];
}
cout << comput_24(a,5);
}
