2020.11.04 四道算法题

2020.11.04 四道算法题

1.上台阶（递归）

题目描述：有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

解题思路：写代码之前在纸上写下来m=1，2，3，4，5时的走法，分别是1，1，2，3，5，可以看出来是斐波那契数列的规律，应该是意在考察递归。

我的代码：

#include <stdio.h>
int dp(int m){if(m==0) return 0;if(m==1) return 1;else return dp(m-2)+dp(m-1);
}
int main(){int m;scanf("%d",&m);printf("%d",dp(m));
}

2.核反应堆（递归）

题目描述：核反应堆中有α和β两种粒子。每秒钟内一个α粒子可以产生3个β粒子，而一个β粒子可以产生1个α粒子和2个β粒子。若在t=0时刻反应堆中有一个α粒子，求t时刻反应堆中分别有多少个α粒子和β粒子。
输入
输入有多个整数t，每个一行。
输出
输出t时刻反应堆里分别有多少个α粒子和β粒子
样例输入
6
样例输出
183 546

解题思路：看到这个题的时候有点傻眼了，因为这个题我做过！但是忘了！想了好久函数的返回参数应该用void还是int，先用了void在函数里写了printf，结果做不出来，又改成了int。

我的代码：

#include <stdio.h>
int fa(int t);//先声明函数 
int fb(int t);//先声明函数
int fa(int t){int a;if(t==0) a=1;else a=fb(t-1);return a;
} 
int fb(int t){int b;if(t==0) b=0;else b=3*fa(t-1)+2*fb(t-1);return b;
}
int main(){int t;while(scanf("%d",&t)!=EOF){printf("%d %d",fa(t),fb(t));}
}

总感觉自己的代码写的两个递归函数有点麻烦，回来搜了一下网上其他人的做法，是直接用了一个递归函数，在函数里写了数组，刚才写了一下但是不对，下次写了再贴上来

3.英文姓名排序（排序）

题目描述：在汉语里，对汉语姓名可以按拼音排序，也可以按笔画顺序排序。在英语里，对英语姓名主要按字母顺序排序。本题要求给定的一组英文姓名按长短顺序排序。
输入
输入文件中包含多个测试数据。每个测试数据的第1行是一个正整数N（0 < N < 100），表示该测试数据中英文姓名的数目；接下来有N行，每行为一个英文姓名，姓名中允许出现的字符有大小写英文字母、空格和点号（.），每个英文姓名长度至少为2、但不超过50.N=0表示输入结束。
输出
对输入文件中的每个测试数据，输出排序后的姓名。排序方法为：先按姓名长度从长到短的顺序排序，对长度相同的姓名，则按字母顺序排序。每2个测试数据的输出之间输出一个空行。
样例输入
4
David A. Forsyth
Jean Ponce
Tom M. Mitchell
Thomas H. Cormen
0
样例输出
David A. Forsyth
Thomas H. Cormen
Tom M. Mitchell
Jean Ponce

解题思路：这个题看到了真的一点思路都没有，等我先好好学一下排序再来补这篇博客

参考代码：