每日两小时编程之旅（七）
每日两小时编程之旅（七）
算法篇-mooc学习
递归
1.汉诺塔问题
#include<bits/stdc++.h>
using namespace std;
void Hanoi(int n, char src, char mid, char dest)
//将src座上的n个盘子，以mid为中转，移动到dest座
{
if(n==1)//只需要移动一个盘子
{
cout<<src<<"->"<<dest<<endl;//直接将盘中从src移动到dest即可
return;//递归终止
}
Hanoi(n-1,src,dest,mid);//先将n-1个盘子从src移动到mid
cout<<src<<"->"<<dest<<endl;//再将一个盘子从src移动到dest
Hanoi(n-1,mid,src,dest);//最后将n-1个盘子从mid移动到dest
return;
}
int main()
{
int n;
char a,b,c;
cin>>n>>a>>b>>c;
Hanoi(n,a,b,c);
return 0;
} 2.n皇后问题（不知道为什么没有输出）
#include<bits/stdc++.h>
using namespace std;
int N;
int queenPos[100];
//用来存放算好的皇后位置。最左上角是[0,0]
void NQueen(int k)//在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后
{
int i;
if(k==N)
{
for(i=0;i<N;i++)
{
cout<<queenPos[i]+1<<" ";
}
cout<<endl;
return;
}
for(i=0;i<N;i++)
{
int j;
for(j=0;j<k;j++)//和已经摆好的k个皇后的位置比较，看是否冲突
{
if(queenPos[j]==i||abs(queenPos[j]-i)==abs(k-j)) break;//冲突，则试下一个位置
}
if(j==k)//当前选的位置i不冲突
{
queenPos[k]==i;//将第k个皇后摆放在位置i
NQueen(k+1);
}
}
}
int main()
{
cin>>N;
NQueen(0);//从第0行开始摆皇后
return 0;
}
3.(逆)波兰表达式（难以理解）
#include<bits/stdc++.h>
using namespace std;
double exp()//读入一个逆波兰表达式，并计算其值
{
char s[20];
cin>>s;
switch(s[0])
{
case '+':return exp()+exp();
case '-':return exp()-exp();
case '*':return exp()*exp();
case '/':return exp()/exp();
default: return atof(s);//atof()将字符串转换为浮点型数
break;
}
}
int main()
{
printf("%lf",exp());
return 0;
} 4.表达式求值
#include<bits/stdc++.h>
using namespace std;
int factor_value();//因子
int term_value();//项
int expression_value();//表达式
int main()
{
cout<<expression_value()<<endl;
return 0;
}
int expression_value()//求一个表达式的值
{
int result=term_value();//求第一个项的值
bool more=true;
while(more)
{
char op=cin.peek();//看一个字符，不取走
if(op=='+'||op=='-')
{
cin.get();//从输入中取走一个字符
int value=term_value();
if(op=='+') result+=value;
else result-=value;
}
else more=false;
}
return result;
}
int term_value()//求一个项的值
{
int result=factor_value();//求第一个因子的值
while(true)
{
char op=cin.peek();
if(op=='*'||op=='/')
{
cin.get();
int value=factor_value();
if(op=='*') result*=value;
else result/=value;
}
else break;
}
return result;
}
int factor_value()//求一个因子的值
{
int result=0;
char c=cin.peek();
if(c=='(')
{
cin.get();
result=expression_value();
cin.get();
}
else
{
while(isdigit(c))//isdigit字面意思，是整数返回true不是返回false
{
result=10*result+c-'0';
cin.get();
c=cin.peek();
}
}
return result;
} 5.上台阶(斐波那契数列)
#include<bits./stdc++.h>
using namespace std;
int N;
int stairs(int n)
{
if(n<0) return 0;
if(n==0) return 1;
return stairs(n-1)+stairs(n-2);
}
int main()
{
while(cin>>N)
{
cout<<stairs(N)<<endl;
}
return 0;
} 6.放苹果
#include<bits/stdc++.h>
using namespace std;
int f(int m,int n)
{
if(n>m) return f(m,m);
if(m==0) return 1;
if(n==0) return 0;
return f(m,n-1)+f(m-n,n);
}
int main()
{
int t,m,n;//m表示苹果，n表示盘子
cin>>t;
while(t--)
{
cin>>m>>n;
cout<<f(m,n)<<endl;
}
return 0;
} 7.算24
#include<bits/stdc++.h>
using namespace std;
double a[5];
#define EPS 1e-6
bool isZero(double x)
{
return fabs(x)<=EPS;
}
bool count24(double a[],int n)
{
if(n==1)
{
if(isZero(a[0]-24)) return true;
else return false;
}
double b[5];
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)//枚举两个数的组合
{
int m=0;//还剩下m个数，m=n-2
for(int k=0;k<n;k++)
{
if(k!=i&&k!=j) b[m++]=a[k];//把其余数放入b
}
b[m]=a[i]+a[j];
if(count24(b,m+1)) return true;
b[m]=a[i]-a[j];
if(count24(b,m+1)) return true;
b[m]=a[j]-a[i];
if(count24(b,m+1)) return true;
b[m]=a[i]*a[j];
if(count24(b,m+1)) return true;
if(!isZero(a[j]))
{
b[m]=a[i]/a[j];
if(count24(b,m+1)) return true;
}
if(!isZero(a[i]))
{
b[m]=a[j]/a[i];
if(count24(b,m+1)) return true;
}
}
}
return false;
}
int main()
{
for(int i=0;i<4;i++) cin>>a[i];
if(count24(a,4)) cout<<"YES!"<<endl;
else cout<<"NO!"<<endl;
return 0;
}