T1002-翊(范怡鑫) A- 数字反转 解析:运用递归,将某个数拆分成该数与10的商和该数取10的模,递归出口为该数不可再拆分,即小于10,再一次将相应位乘10、乘100······即得到反转后的数字。 代码:
#include<iostream>
using namespace std;
int a=10;
long long n;
int ovt(long long x)
{
long long N=0;
if(x/10==0)
{
a=10;
return x;
}
N=ovt(x/10)+x%10*a;
a*=10;
return N;
}
int main()
{
cin>>n;
cout<<ovt(n)<<endl;
}s
B- s01串 解析:写出前几个字串不难发现从第三个字串开始,字串即为前两个字串连起来。运用递归,将第n个字串拆成第n-2个字串与第n-1个字串,当n=1时,字串为1,当n=0时,字串为0。 代码:
#include<iostream>
using namespace std;
void change(int n)
{
if(n==0)
cout<<0;
else if(n==1)
cout<<1;
else
{
change(n-2);
change(n-1);
}
}
int main()
{
int n;
cin>>n;
change(n);
}
C- benTuTuT的表面兄弟 解析:运用递归,将向第n个兄弟借钱拆分成向第n-1和第n-2个兄弟借钱,当n=2时,只能向第一个兄弟借钱,即输出"Brother 1:I don't have money"。当当前测试数据不为最后一组时,输出一个空行。 代码:
#include<iostream>
using namespace std;
int t,i;
void my_printf(int n)
{
if(n==2)
cout<<"Brother 1:I don't have money"<<endl;
else if(n>2)
{
my_printf(n-1);
cout<<"Brother "<<n-1<<":I don't have money"<<endl;
my_printf(n-2);
cout<<"Brother "<<n-2<<":I don't have money"<<endl;
}
}
int main()
{
cin>>t;
int a[t];
for(i=0;i<t;i++)
cin>>a[i];
for(i=0;i<t;i++)
{
my_printf(a[i]);
if(i<t-1)
cout<<endl;
}
}
D- The biggest water problem 若输入的数小于10,则直接返回该数。否则运用取模运算将每一位数字拆分出来依次加和,若加和的数仍大于10,则运用递归再次拆分加和,直到结果小于10为止。 代码:
#include<iostream>
using namespace std;
int a;
int sum(long long n)
{
if(n<10)
return n;
else
a=n%10+sum(n/10);
return sum(a);
}
int main()
{
long long n;
cin>>n;
cout<<sum(n)<<endl;
}
E- 跳台阶 解析:设n级台阶的跳法种数为f[n],则f[n]=f[1]+f[2]+······+f[n-1],而f[n-1]=f[1]+f[2]+······+f[n-2],两式相减可得f[n]-f[n-1]=f[n-1],即f[n]=2f[n-1]。运用递归,当n=1时返回1。 代码:
#include<iostream>
using namespace std;
int T,i,a;
int num(int n)
{
if(n==1)
return 1;
else
return 2*num(n-1);
}
int main()
{
cin>>T;
int a[T];
for(i=0;i<T;i++)
cin>>a[i];
for(i=0;i<T;i++)
cout<<num(a[i])<<endl;
}
F- 香冈吉哲跑得快 解析:运用迭代,从v=1开始,判断是否满足条件,若不满足,v加1,若满足,则跳出循环,输出v。若v大于10,仍然跳出循环,输出-1. 代码:
#include<iostream>
using namespace std;
int H,C,p,v,W,t;
int main()
{
cin>>H>>C>>p;
for(v=1;;v++)
{
t=H/v;
if(H%v!=0)
t++;
W=C-p*t;
if(v>10)
{
cout<<-1;
break;
}
if(W>=0)
{
cout<<v;
break;
}
}
}
G- 大吉大利,今晚吃鸡 解析:该问题为汉诺塔问题。当有n(n>1)个圆盘时,需要把1---n-1圆盘从a移动到c,再将最底下的圆盘n移动到b,把1---n-1圆盘从c移动到a,把圆盘n从b移动c,1---n-1圆盘从a移动到c。当n=1时,把圆盘从a移动到b,再从b移动到c。 代码:
#include <iostream>
using namespace std;
int i;
long long movetower(int m)
{
if(m==0)
return 0;
if(m==1)
i+=2;
else
{
movetower(m-1);
i++;
movetower(m-1);
i++;
movetower(m-1);
}
return i;
}
int main()
{
int n;
cin>>n;
cout<<movetower(n)<<endl;
return 0;
}
H- 小q的数列 解析:若n为偶数,则f[n]=f[n/2],若n为奇数,则f[n]=f[n/2]+1,递归则可求出f[n]。n’=2^f[n]-1。 代码:
#include<iostream>
#include<cmath>
using namespace std;
int t,i,r;
int fun(long long n)
{
if(n==0)
return 0;
else if(n==1)
return 1;
else if(n%2==0)
return fun(n/2);
else
return fun(n/2)+1;
}
long long num(int r)
{
return pow(2,r)-1;
}
int main()
{
cin>>t;
long long a[t];
for(i=0;i<t;i++)
cin>>a[i];
for(i=0;i<t;i++)
{
r=fun(a[i]);
cout<<r<<" "<<num(r)<<endl;
}
}
J-生日快乐 解析:从某一边的i/n处下刀,此时的i可以是从1到n-1中的任意数,左右两边又可以分成i份和n-i份,运用递归,将n份最终分解为一份,此时所有长边与短边比值中取最小值。 代码:
#include<iostream>
#include<iomanip>
using namespace std;
int n;
double x,y;
double ratio(double x,double y,int n)
{
double a,b;
if(n==1)
return max(x,y)/min(x,y);
double r=10001;
for(int i=1;i<n;i++)
{
r=min(r,max(ratio(x/n*i,y,i),ratio(x/n*(n-i),y,n-i)));
r=min(r,max(ratio(x,y/n*i,i),ratio(x,y/n*(n-i),n-i)));
}
return r;
}
int main()
{
cin>>x>>y>>n;
cout<<fixed<<setprecision(6)<<ratio(x,y,n)<<endl;
}