C++ 基础算法 - 递推 & 递归

1198：逆波兰表达式

虽然逆波兰表达式将符号提前了，但是仍然能够计算，因为对于一个逆波兰表达式，最先找到的就是一个式子的运算符号，运算符号是紧挨着两个算式的，意思就是如果发现了一个符号，接下来就会有两个算式，当输入完成两个算式后，就可以使用符号，一旦用完了符号，就说明算式结束了

代码如下

#include<iostream>

#include<cstdio>
#include<cstdlib>//atof()所需的头文件
using namespace std;
char a[55];
double f()
{
scanf("%s",&a);
if(a[0]=='+') return nbl()+nbl();
else if(a[0]=='-') return nbl()-nbl();
else if(a[0]=='*') return nbl()*nbl();
else if(a[0]=='/') return nbl()/nbl();//将符号应用于之后的算式中
else return atof(a);
//递归的出口,找到了数字就返回,atof()的作用是将char类型的数组转化为double类型
//例如"12345.6789"就会变成12345.6789
}
int **in()
{
printf("%f\n",f());
return 0;
}

递归相较于递推较好理解，只需按照递归的层次顺序去模拟过程就能够明白

1199：全排列

全排列比较难的地方在于需要标记某个数字选没选过，方便下一次的选取

#include<iostream>

#include<cstdio>
#include<string>
using namespace std;
bool b[27];
string s;
int l;
void search(int i,string x)
{
 for(int j=0;j<l;++j)
 {
if(!b[s[j]-'a'])
{
 b[s[j]-'a']=true;//将选过的字母标记为true
 if(i==l-1) printf("%s%c\n",x.c_str(),s[j]);//输出
 else search(i+1,x+s[j]);//位置增加,x+s[j]就是将字符串拼起来
 b[s[j]-'a']=false;//用完了随手放回(标记为为选过,让后面能够选)
}
 }
}
int **in()
{
 getline(cin,s);//输入
 l=s.size();//计算长度
 search(0,"");//搜索
 return 0;
}

1200：分解因数

这里的分解可以从**小 2 开始分解，值得注意的是每次的分解因数不能够小于上一次的分解因数

#include<iostream>

#include<cstdio>
using namespace std;
int sum;
void decomposition(int n,int last)//n为分解出来的数,last为上一次用于分解的除数
{
 if(n==1)//如果完全分解了
 {
sum++;//分解方案数增加
return;//返回上一层分解式
 }
 int i;
 for(i=last;i<=n;++i) if(n%i==0) decomposition(n/i,i);
 //循环从上一次的分解除数开始,结束于n,因为n除以大于n的数是不能分解的
 //成功就可以进行下一层的分解式
}
int **in()
{
 int n,x;
 scanf("%d",&n);
 while(n--)//这个也是同样可供输入n次的循环
 {
scanf("%d",&x);//输入
decomposition(x,2);//进行分解
printf("%d\n",sum);
sum=0;
 }
 return 0;
}

1201：菲波那契数列

斐波那契数列的递归版本，在递归示范中就已经有了这里就不讲了

#include<iostream>

#include<cstdio>
using namespace std;
int Fibonacii(int x)
{
 if(x==1||x==2) return 1;
 return Fibonacii(x-1)+Fibonacii(x-2);
}
int **in()
{
 int i,n,x;
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
scanf("%d",&x);
printf("%d\n",Fibonacii(x));
 }
 return 0;
}

1202：Pell数列

按照斐波那契数列的方法就能过做出来，在这里教大家一个方法去减少代码量

#include<iostream>

#include<cstdio>
#define M 32767//下面会讲
using namespace std;
int ans[1000000];
int Pell(int x)
{
 if(ans[x]!=0) return ans[x];//记忆化搜索,下面会讲
 if(x==1) return ans[x]=1;
 if(x==2) return ans[x]=2;
 return ans[x]=(2*Pell(x-1)%M+Pell(x-2)%M)%M;
 //反复进行取模运算,防止爆空间
}
int **in()
{
 int i,n,x;
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
scanf("%d",&x);
printf("%d\n",Pell(x));
 }
 return 0;
}

如何减少代码量

例如本题中将取模的常数定义为了 M，编译器就会将所有 M 替换成为 M 后面的东西，当然 M 是类似于变量的一种存在，不会将所有字符 M 都替换的

M 后面的东西不一定是数字，也可以是一些其它的东西

记忆化搜索

当一个递归或者搜索在进行时，会将问题分解成小问题进行计算，但是这些小问题可能会被重复计算过了，所以我们可以把答案放入一个答案数组当中去，要用的时候可以直接使用，不必重新计算，可以节约时间

1203：扩号匹配问题

还是比较简单的一题的，有不懂的看代码中的注释

#include<iostream>

#include<cstring>
#include<cstdio>
using namespace std;
char a[101],b[101];
int up(int c)
{
 if(c==-1) return c;//如果找出界了就表示不匹配
 else if(b[c]=='$') return c;//找到了同样不匹配的右括号就返回其位置
 else return up(c-1);//没找到就接着往前找
}
int **in()
{
 int i,s,l;
 while(scanf("%s",a)!=EOF)//读不到就退出
 {
printf("%s\n",a);//先输出
l=strlen(a);
memset(b,' ',sizeof(b));//需要清空一下才行
for(i=0;i<l;i++)
{
 if(a=='(') b='$';//先默认a是不匹配的左括号

 else if(a==')')//如果找到右括号

 {
s=up(i-1);//向前找
if(s==-1) b='?';//如果没找到就表示这个右括号是不匹配的

else b[s]=' ';//否则将匹配到的左括号的不匹配符给去掉
 }
}
printf("%s\n",b);//输出
 }
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int climb(int x)
{
 if(x==1||x==2) return x;//即返回对应的
 return climb(x-1)+climb(x-2);//进行查找
}
int **in()
{
 int n;
 while(scanf("%d",&n)!=EOF) printf("%d\n",climb(n));//读入
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
void Hanoi(int n,char a,char c,char b)
{
 if(n==1)
 {
printf("%c->%d->%c\n",a,n,b);
return;
 }
 Hanoi(n-1,a,b,c);
 printf("%c->%d->%c\n",a,n,b);
 Hanoi(n-1,c,a,b);
}
int **in()
{
 int n;
 char a,b,c;
 scanf("%d%c%c%c",&n,&a,&b,&c);
 Hanoi(n,a,c,b);
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int apple(int m,int n)
{
 if(m==0||n==1) return 1;//没有苹果或只有1个盘子时分法为1种
 if(m<n) return apple(m,m);
 return apple(m,n-1)+apple(m-n,n);
}
int **in()
{
 int i,t,m,n;
 scanf("%d",&t);
 for(i=1;i<=t;i++)
 {
scanf("%d%d",&m,&n);//输入
printf("%d\n",apple(m,n));//输出
 }
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int **(int a,int b)//辗转相除法
{
 if(b==0) return a;
 return **(b,a%b);
}
int **in()
{
 int x,y;
 scanf("%d%d",&x,&y);
 if(x<y) swap(x,y);
 printf("%d\n",**(x,y));
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
string decomposition(int n)
{
 if(n==0) return "0";
 int i,t;
 string ans;
 for(i=0,t=1;t<n;i++) t*=2;//判断t的多少次方为n
 i--;//多加了一次,要减去1
 t/=2;//多乘了一次,要除以2
 if(i==1) ans="2";//如果是1次方
 else
 {
ans="2(";//如果不是1次方,就继续将次方分解
ans+=decomposition(i);
ans+=")";
 }
 if(n-t)//如果单项式不够,就多几个式子
 {
ans+="+";
ans+=decomposition(n-t);
 }
 return ans;
}
int **in()
{
 int n;
 scanf("%d",&n);
 printf("%s\n",decomposition(n).c_str());
 return 0;
}

#include<iostream>

#include<cstdio>
int **(int a,int b)
{
if(a%b==0) return b;
else return **(b,a%b);
}
int **in()
{
 int n,m,i,a,b,c,d;
 scanf("%d%d/%d",&n,&a,&b);
 for(i=2;i<=n;i++)
 {
scanf("%d/%d",&c,&d);
m=b*d/**(b,d);
a*=m/b,b=m;
a+=c*(m/d);//通分并相加
 }
 m=**(a,b);
 a/=m,b/=m;
 if(b==1) printf("%d\n",a);//如果分母为1
 else printf("%d/%d\n",a,b);//分母不为1
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int f=0;
void decomposition(int n,int x)
{
 if(n==1) return;//分解完成
 int y=0;
 while(n%x==0)//如果能够进行分解
 {
++y;
n/=x;//进行分解
 }
 if(y!=0)//如果成功分解过
 {
if(f==1) printf("*");
if(y!=1) printf("%d^%d",x,y);
else printf("%d",x);
f=1;
 }
 decomposition(n,++x);
}
int **in()
{
 int n;
 scanf("%d",&n);
 decomposition(n,2);
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
bool flag;
bool search(int k,int x)
{
 if(k==x) return true;//如果符合**元素
 if(k>x) return false;//不可能达到
 return search(2*k+1,x)||search(3*k+1,x);//按照式子查找
}
int **in()
{
 int k,x;
 scanf("%d,%d",&k,&x);
 if(search(k,x)) printf("YES\n");//输出
 else printf("NO\n");
 return 0;
}