任意数月后死亡的斐波那契兔

Question

所以，我已经看到了一些解决这个问题或类似问题的方法，但我真的想知道为什么我的方法不起作用。它比我找到的许多解决方案更容易阅读，所以我很想让它起作用！

从1对兔子开始，2个月后开始繁殖。跑n个月，兔子活了m个月就死了。 “63”的输入应返回4，但它返回3。

#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split() 
n, m = int(n), int(m)
generations = [1, 1, 2] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
    count = 3 #we start at the 3rd generation.
    while (count < i):
        if (count < j):
            generations.append(generations[count-2] + generations[count-1]) #recurrence relation before rabbits start dying
        else:                                                               #is just the fib seq (Fn = Fn-2 + Fn-1)
            generations.append((generations[count-2] + generations[count-1]) - generations[(count-j)])  #Our recurrence relation when rabbits die every month
        count += 1                                                          #is (Fn = Fn-2 + Fn-1 - Fn-j)
    return (generations[count-1])


print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))

谢谢=]

Answer 1

这里有两个复发关系的病例。考虑到n是序列运行的月数，而m是一对生命将持续的月数：

1）如果序列中的索引（基于零）小于m：
正态Fibonacci（当前项=前一项+前一项）。

2）如果指数大于或等于m：
当前项=以前项的总和（m-1）（忽略前面的项）。

Here's an example with a sequence named A and m = 5:
A5 = A0 + A1 + A2 + A3 (4 terms, i.e.m - 1, ignoring the one immediately before)
.
If m = 3 then:
A3 = A0 + A1 (only 2 terms, m - 1)

是的。

下面的代码（在Python中）有一个偏移量为2，这是因为序列开头的初始值[1，1]。

def mortal_rabbits(n, m):
    sequence = [1, 1]

    for i in range(n - 2):
        new_num = 0
        if i + 2 < m:
            #Normal fibonacci - No deaths yet
            new_num = sequence[i] + sequence[i + 1]
        else:
            #Different reoccurence relation - Accounting for death
            for j in range(m - 1):
                new_num += sequence[i - j]

        sequence.append(new_num)

    return sequence

Answer 2

使用递归。

public static int fibRec(int months, int dieAfter) {
    if(months <= 0) return 0;
    if(months == 1) return 1;
    if(months <= dieAfter)
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter);
    else if (months == dieAfter+1)
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter) - 1;
    else
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter) 
                 - fibRec(months-(dieAfter+1), dieAfter);
}

Answer 3

这是从太空学员问题的答案中复制出来的，以帮助rbump将其从“未回答”的问题列表中剔除。

---

这里的两个关键点是绘制出大量的树，并确保包括第一代和第二代死亡的基本病例检查（两种情况下都是-1，然后是依赖于输入的结果）。

3个潜在病例。常规fib序列当我们不需要解释死亡，第一代和第二代死亡初始化我们的最终序列与复发关系Fn-2+Fn-1-Fn-（monthsAlive+1）

我确信有一种方法可以合并这些检查中的1到2个，使算法更有效，但是到现在为止，它立即正确地解决了一个大型测试用例（90，17）。所以我很高兴。

经验教训：使用整个白板。

#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split() 
n, m = int(n), int(m)
generations = [1, 1] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
    count = 2
    while (count < i):
        if (count < j):
            generations.append(generations[-2] + generations[-1]) #recurrence relation before rabbits start dying (simply fib seq Fn = Fn-2 + Fn-1)
        elif (count == j or count == j+1):
            print ("in base cases for newborns (1st+2nd gen. deaths)") #Base cases for subtracting rabbit deaths (1 death in first 2 death gens)
            generations.append((generations[-2] + generations[-1]) - 1)#Fn = Fn-2 + Fn-1 - 1
        else:
            generations.append((generations[-2] + generations[-1]) - (generations[-(j+1)])) #Our recurrence relation here is Fn-2 + Fn-1 - Fn-(j+1)
        count += 1
    return (generations[-1])


print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))