华为上机题-递归

发表于 | 阅读次数:

统计每个月兔子的总数

1
2
题目描述
有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？
1
2
3
4
5
6
7
8
9
10
11
输入描述:
输入int型表示month

输出描述:
输出兔子总数int型

示例1
输入
9
输出
34

这道题贼简单,就是一个斐波那契数列递归实现:
F(N)=F(N-1)+F(N-2)
F(1)=1
F(2)=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def Feibo(N):
    if N==1:
        return 1
    elif N==2:
        return 1
    else:
        return Feibo(N-1)+Feibo(N-2)
    
    
while True:
    try:
        n=int(raw_input())
        r=Feibo(n)
        print r
    except:
        break

放苹果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
题目描述
题目描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。


输入

每个用例包含二个整数M和N。0<=m<=10，1<=n<=10。


样例输入

7 3


样例输出

8

这道题想到递归的确有点绕,一位博主的解题思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
放苹果分为两种情况，一种是有盘子为空，一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空，则(m,n)问题转化为将m个苹果放在n-1个盘子上，即求得(m,n-1)即可
2.假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上
即求(m-n，n)
递归还需要确定递归基准条件
m=1或n=1时,只有一种摆法
m=0时,苹果不存在,就不存在摆法-->0
综上所述：
(m，n)=(m,n-1)+(m-n,n);
(m,1)=(1,n)=1,m>0,n>0
(0,n)=0
还有边界问题需要考虑
但是这么做还是有个致命的问题!!!
针对第二个条件的时候,m-n等于0的时候,根本不存在递归的问题了,只能放一种,但是(0,n)的递归限制,会在(m，n)=(m,n-1)+(m-n,n);对最后一项变为0!!!!就比原来的少了!!!!
So 现在给出精确的解法:
(0,n)=0
(1,n)=(m,1)=(1,1)=1 m>0,n>0
(m,n)=(m,n-1)+(m-n,n) m-n>0,n>0
(m,n)=(m,n-1)+1 m-n=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def putApple(M,N):
    if M<=0:
        return 0
    if M==1 or N==1:
        return 1
    if M>0 and M-N==0:
        return putApple(M,N-1)+1

    return putApple(M,N-1)+putApple(M-N,N)


while True:
    try:
        M,N=map(int,raw_input().split())
        r=putApple(M,N)
        print r
    except:
        break

热评文章