题解 | #专题二题解#
专题二题解
https://ac.nowcoder.com/acm/contest/28145/A
解析：
本题的目的是反转数字，那递归出口就是这个数是个位数的时候。调用函数时，应该先取出单独位上的数字再乘十最后累加到结果上。
#include <iostream>
typedef long long ll;
int a=10;
using namespace std;
int change(ll n)
{
int N=0;
if(n/10==0)
{
a=10;
return n;
}
N=change(n/10)+n%10*a;
a*=10;
return N;
}
int main()
{
ll n;
cin>>n;
cout<<change(n)<<endl;
}
B. S01串：
解析：
本题输入的是变换次数，第n次的字符是第n-2次字符加上第n-1次字符，归出口应该是次数为0和次数为1，递归位置应该为n-2,n-1。
#include <iostream>
using namespace std;
void fun(int n)
{
if(n==0)
cout <<0;
else if(n==1)
cout <<1;
else
{
fun(n-2);
fun(n-1);
}
}
int main()
{
int n;
cin>>n;
fun(n);
}
C. benTuTuTuT的表面兄弟：
解析：
首先自定义一个函数用于输出想要的结果格式，再运用递归来达到效果，递归出口应该是总人数为1或者2时输出的只有bother1 don’t have money，递归方程在于第n个人向第n-1和n-2个人借钱，所以每一次都是递归n-1和n-2。
#include <iostream>
using namespace std;
void pt(int n)
{
cout<<"Brother "<<n<<":I don't have money"<<endl;
}
void fun(int n)
{
if(n==1||n==2)
{
pt(1);
}
else if(n==3)
{
pt(1);
pt(2);
pt(1);
}
else if(n==4)
{
fun(3);
pt(3);
pt(1);
pt(2);
}
else
{
fun(n-1);
pt(n-1);
fun(n-2);
pt(n-2);
}
}
int main()
{
int T,n;
cin>>T;
while(T--)
{
cin>>n;
fun(n);
cout<<endl;
}
}
D. The Biggest Water Problem:
解析：
本题的目的是求各个位上的数字累加之和，那递归出口就是这个数是个位数的时候。每次递归的时候应该先取出单独位上的数字累加到结果上。
#include <iostream>
using namespace std;
int sum(int n)
{
int a=0;
if (n <10)
return n;
else
{
a= n%10+sum(n/10);
return sum(a);
}
}
int main()
{
int n;
cin >> n;
cout << sum(n);
return 0;
}
E. 跳台阶：
解析：
通过分析题意可得，fun（n）= fun（1）+ fun（2）+……+ fun（n-1）①
fun（n-1）= fun（1）+ fun（2）+……+ fun（n-2）②
由①-②得fun（n）=fun(n-1)*2；递归出口应该为n=1时，递归方程为fun（n）=fun(n-1)*2。
#include <iostream>
using namespace std;
int fun(int n)
{
if(n<=0)
return 0;
if(n==1)
return n;
return fun(n-1)*2;
}
int main()
{
int n,T;
cin>>T;
while(T--)
{
cin>>n;
cout<<fun(n)<<endl;
}
return 0;
}
F. 香冈吉哲跑得快：
解析：
因为最大速度为10m/s，所以只需要自定义一个函数，从1开始计算，取满足条件的最大速度即可。自定义函数的功能应该包括计算当前速度所需要的时间和判断瞬时体力值是不是大于零。
#include<iostream>
using namespace std;
int h,c,p;
int v;
int fun(int x)
{
int t=h/x;
if(h%x!=0) t++;
if(c-p*t<0)
{
return 0;
}
return 1;
}
int main()
{
cin>>h>>c>>p;
v=-1;
for(int i=1;i<=10;i++)
{
if(fun(i))
{
v=i;
break;
}
}
cout<<v<<endl;
}
G. 大吉大利，今晚吃鸡：
解析：
这道题其实是典型的汉诺塔问题，递归出口为n=0的时候，假设有三根柱子ABC，则需要三步，第一步将n-1个圆盘从A移到C，将最下面的圆盘从A移到B，第二步将n-1个圆盘从C移到A，将最下面的圆盘从B移到C，第三步将n-1个圆盘从A移到C。
递归的位置就在于每一次的移动n-1个圆盘。
#include <iostream>
using namespace std;
typedef long long ll;
ll sum=0;
void fun(int n,char a,char b,char c)
{
if(n==0)
return;
if(n==1)
{
sum+=2;
return;
}
fun(n-1,a,b,c);
sum++;
fun(n-1,c,b,a);
sum++;
fun(n-1,a,b,c);
}
int main()
{
int n;
while(cin>>n)
{
sum=0;
fun(n,'a','b','c');
cout<<sum<<endl;
}
}
H. 小q的数列：
解析：
本题可以看出需要分奇偶讨论，奇数时：f(n)=f(n/2)+1，偶数时：f(n)=f(n/2)。递归出口在于n<=1时，其它情况分奇偶递归即可。
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
int fun1(ll n)
{
if(n<=1)
return n;
if(n&1)
return fun1(n/2)+1;
return fun1(n/2);
}
ll fun2(ll a)
{
if(a==0)
{
return 1;
}
return fun2(a-1)*2;
}
int main()
{
ll n;
ll a;
int T;
cin>>T;
while(T--)
{
cin>>n;
a=fun1(n);
cout<<a<<" "<<fun2(a)-1<<endl;
}
return 0;
}
I. 拖米航空公司：
解析：
本题的关键在于判断每一个位置是否左边和前面是否有人，如果没人该座位可选，然后用每一次递归寻找所有可能的方案数即可；递归出口在合法座位数h为0时，每一次选好一个位置，标记为h，表示该位置已经被选，然后递归调用选下一个，直到 h == 0 ，即 k 个座位已经选好，递归结束。
#include <iostream>
#include <string>
int M, N, K, T;
using namespace std;
typedef long long ll;
int a[85][85];
int fun(int k, int b ,int c)
{
ll sum = 0;
if( k == 0)
return 1;
for(int i = b; i < N; i++)
{
for(int j = c; j < M; j++)
{
if( i-1 >= 0 && j-1 >= 0 && a[i-1][j] ==0 && a[i][j-1] ==0)
{
a[i][j] = k;
sum += fun( k-1, i ,j+1);
}
else if(i-1 <0 && j -1 <0 )
{
a[i][j] = k;
sum += fun( k-1, i ,j+1);
}
else if(i-1 < 0 && j -1 >= 0 && a[i][j-1] ==0)
{
a[i][j] = k;
sum += fun( k-1, i ,j+1);
}
else if(j-1 < 0 && i-1 >=0 &&a[i-1][j] ==0)
{
a[i][j] = k;
sum += fun( k-1, i ,j+1);
}
a[i][j] =0;
}
c = 0;
}
return sum;
}
int main()
{
cin>>T;
while(T--)
{
cin>>M>>N>>K;
cout<<fun( K, 0, 0)%420047<<endl;
}
return 0;
}
J. [SCOI2009]生日快乐：
解析：
对于要切n刀的边长为x和y的蛋糕，我们可以在(ix/n)的位置切一刀，也可以在（iy/n）的位置切一刀，ix/n的位置切一刀后，左边还需要切i次，右边还要切n-i次，
递归过程中需要有一个足够大的数来比较从而挑出最小值，每一次的递归就是判断切的位置，递归出口在n=1时。
#include <iostream>
#include <algorithm>
using namespace std;
double fun(double x, double y, int n)
{
if(n == 1)
return max(x,y)/min(x,y);
double s =1000000000;
for(int i = 1; i < n; i++)
{
s = min(s, max(fun(x/n*i, y, i), fun(x/n*(n-i), y, n-i)));
s = min(s, max(fun(x, y/n*i, i), fun(x, y/n*(n-i), n-i)));
}
return s;
}
int main()
{
double x, y;
int n;
scanf("%lf%lf%d", &x,&y,&n);
printf("%.6lf\n",fun(x,y,n));
return 0;
}