上周的一道笔试题
递归计算
根据两组参数，使用递归完成编程。
递归方法
参数1 [1,3]
参数2 n
当参数2 < 小于参数1中元素个数的时候，不输出。
当n = 3 时 输出 [1,3,4]
当n = 4 时 输出 [1,3,4,7]
当 n = 11 使用递归程序输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void test(List<Integer> list , Integer end) {
if(list.isEmpty() || list.size() < 1 || end == null || end < 0){
throw new RuntimeException("初始化参数异常");
}
if (list.size() < end) {
int length = list.size();
list.add(list.get(length - 1) + list.get(length - 2));
test(list , end);
}
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{1,3};
List<Integer> list = new ArrayList(Arrays.asList(arr));
test(list , 11);
System.out.println(list.toString());
}
>>
[1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199]
|
不过当时写的时候并没有判断异常。当时紧张硬编码。
古典问题：⼀对兔⼦
有⼀对兔⼦，从出⽣后第 3 个⽉起每个⽉都⽣⼀对兔⼦，⼩兔⼦⻓到第三个⽉后每个⽉⼜⽣⼀对兔⼦，
假如兔⼦都不死，问每个⽉的兔⼦对数为多少？
思路：斐波那契数列（Fibonacci sequence）
程序分析： 兔⼦的规律为数列 1,1,2,3,5,8,13,21…，当 n=1 或 n=2时，分别为 1。
从 n=3 开始 f(n) = f(n-1) + f(n-2)。所以转化为程序则如下：
1
2
3
4
5
6
7
8
9
10
| public static void main(String[] args) {
int n = 10;
System.out.println("第" + n + "个⽉兔⼦总数为" + fun(n));
}
private static int fun(int n) {
if (n == 1 || n == 2)
return 1;
else
return fun(n - 1) + fun(n - 2);
}
|
使⽤递归实现 n! 的阶乘
思路：求⼀个数的阶乘，既可以使⽤循环，也可以使⽤递归。本地要求使⽤递归。
把公式分解后 n! = n*(n-1)! ；但是 1的阶乘为 1。所以我们可以定义⼀个⽅法 jie(int n)，假定⽅法就是
求阶乘的⽅法，则每次 n! = n * jie(n-1)。这样就实现了⽅法逻辑了。
1
2
3
4
5
6
7
8
9
10
11
| public static void main(String[] args) {
int n = 10;
System.out.println(n+"阶乘为：" + jie(n));
}
private static int jie(int n) {
if(n==1) {
return 1;
}else {
return n*jie(n-1);
}
}
|
⽤递归实现字符串倒转
思路：字符串倒序可以有多种实现⽅法，但是本地要求递归。所以我们需要找出相同的可以重复的⽅法来递归完成。
例如：“hello”
第⼀次：截取第⼀个字符“h”，截取剩下“ello”，使⽤“ello”+“h”；
第⼆次：那么“ello”字符串，可以使⽤相同的⽅法，“llo”+“e”；
第三次：“lo”+“l”；
第四次：“o”+“l”；
第五次：“o”⻓度已经是⼀个了，所以依次返回给上⼀步“olleh”。
1
2
3
4
5
6
7
8
9
10
11
| public class StringReverse {
public static String reverse(String originStr) {
if(originStr == null || originStr.length()== 1) {
return originStr;
}
return reverse(originStr.substring(1))+ originStr.charAt(0);
}
public static void main(String[] args) {
System.out.println(reverse("hello"));
}
}
|