Кролики Фибоначчи умирают после произвольного числа месяцев
Итак, я видел несколько решений этой проблемы или аналогичных проблем, но я действительно хочу знать, почему у меня не работает. Это намного легче читать, чем много решений, которые я нашел, поэтому я бы хотел, чтобы это сработало!
Начиная с 1 пары кроликов, которые начнут размножаться через 2 месяца. Бежать в течение n месяцев, где кролики умирают после того, как они жили в течение m месяцев. Ввод '6 3' должен возвращать 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))
Спасибо =]
5 ответов
Это скопировано из ответа на вопрос SpaceCadets, чтобы помочь вычеркнуть его из списка вопросов без ответа.
Двумя ключами здесь было вытягивание дерева для большого числа, И обязательно включение проверки базового случая для первого и второго поколений смертей (в обоих случаях это -1, а затем это зависит от входных данных).
Итак, 3 возможных случая. Обычная последовательность выдумки, когда нам не нужно учитывать смерти, первое и второе поколения смертей для инициализации нашей окончательной последовательности с рекуррентным соотношением 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))
Использование рекурсии.
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);
}
Есть 2 случая для рекуррентных отношений здесь. Учитывая n - количество месяцев, в течение которых выполняется последовательность, а m - количество месяцев, в течение которых пара будет жить:
1) Если индекс в последовательности (от нуля) меньше, чем m:
Нормальный Фибоначчи (текущий термин = предыдущий термин + предыдущий термин).
2) Если индекс больше или равен m:
Текущий термин = сумма (m - 1) предыдущих терминов (игнорируя тот, что был непосредственно перед).
Вот пример с последовательностью с именем A и m = 5:
A5 = A0 + A1 + A2 + A3 (4 члена, т. Е. M - 1, игнорируя тот, что был непосредственно перед)
,
Если m = 3, то:
A3 = A0 + A1 (только 2 члена, м - 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
Игнорируя осложнения, уравнение для числа пар кроликов в поколении
Если мы используем список, это создает проблему, потому что когда n == mнам нужно значение, которое находится в положении -1, что, очевидно, за пределами.
def rabbit_pairs(n, m):
sequence = list()
for i in range(n):
if i < 2:
# Normal Fibonacci initialization
total = 1
sequence.append(total)
elif (i < m) or (m == 0):
# Normal Fibonacci calculation
total = sequence[i - 1] + sequence[i - 2]
sequence.append(total)
elif i == m:
# Now we need R(n - (m + 1)), but i - (m + 1) < 0, so we have to
# provide the missing value
total = sequence[i - 1] + sequence[i - 2] - 1
sequence.append(total)
else:
# i - (m + 1) >= 0, so we can get the value from the sequence
total = sequence[i - 1] + sequence[i - 2] - sequence[i - (m + 1)]
sequence.append(total)
return total
Код, наивно имитирующий поведение в задаче, может быть быстрее с парами, я думаю
def fibm(n,m):
seq = [[0,0],[0,1],[1,0],[1,1]]
#(old,new)
for i in range(4,n+1):
new = seq[i-1][0]#new = previous old
old = seq[i-1][0] + seq[i-1][1] #old = prev old + prev new
if i>m:
old = old - seq[i-m][1] #new from m ago die off
seq.append([old,new])
return(seq)
n,m = 95,16
print(sum(fibm(n,m)[-1]))