Фібоначчі Кролики вмирають після довільного числа місяців

Отже, я бачив кілька рішень для цієї проблеми або подібних проблем, але я дійсно хочу знати, чому моя не працює. Нам набагато простіше читати, ніж багато знайдені рішення, тому я хотів би це зробити!

Починаючи з 1 пари кроликів, які почнуть розмножуватися через 2 місяці. Біжи за n місяців, де кролики вмирають після того, як вони прожили протягом декількох місяців. Вхід "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))

Спасибо =]

11
Ви впевнені, що у вас не є індивідуальний у вашому час порівняння? Він повертає 4 для введення 6, 3, якщо ви змінюєте під час підрахунку до while count <= i .
додано Автор lightlike, джерело
Ви впевнені, що у вас не є індивідуальний у вашому час порівняння? Він повертає 4 для введення 6, 3, якщо ви змінюєте під час підрахунку до while count <= i .
додано Автор lightlike, джерело
Якщо ви працюєте через нього вручну або надрукуєте стан програми на кожній ітерації, це виглядає так, як (6, 3) слід дати вам 3: рівняння для елемента, доданого на останній ітерації, становить 2 + 3 - 2. Це дає вам однакова проблема для (7, 4), оскільки для обох вхідних значень різниця між F (nj) і F (nj-1) становить 1. Які входи це "розбивають" і що це робить?
додано Автор lightlike, джерело
Якщо ви працюєте через нього вручну або надрукуєте стан програми на кожній ітерації, це виглядає так, як (6, 3) слід дати вам 3: рівняння для елемента, доданого на останній ітерації, становить 2 + 3 - 2. Це дає вам однакова проблема для (7, 4), оскільки для обох вхідних значень різниця між F (nj) і F (nj-1) становить 1. Які входи це "розбивають" і що це робить?
додано Автор lightlike, джерело
Щоб отримати останні та другі останні елементи, просто використовуйте покоління [-1] і покоління [-2]
додано Автор John La Rooy, джерело
Щоб отримати останні та другі останні елементи, просто використовуйте покоління [-1] і покоління [-2]
додано Автор John La Rooy, джерело
Ви повинні надати правильну відповідь і відповідь, щоб ви могли прийняти вашу відповідь, і ми можемо проголосувати за вашу відповідь :)
додано Автор James Polley, джерело
Ви повинні надати правильну відповідь і відповідь, щоб ви могли прийняти вашу відповідь, і ми можемо проголосувати за вашу відповідь :)
додано Автор James Polley, джерело
@spacecadet, будь ласка, додайте відповідь і позначте її як прийнятну (для цього ви отримаєте навіть бали!). Ваше запитання відображається як без відповіді, відволікаючись від реальних без відповіді.
додано Автор trapicki, джерело
@spacecadet, будь ласка, додайте відповідь і позначте її як прийнятну (для цього ви отримаєте навіть бали!). Ваше запитання відображається як без відповіді, відволікаючись від реальних без відповіді.
додано Автор trapicki, джерело
Також варто зауважити, що зміна останнього елемента на +1 працює лише для невеликих входів. Деякі місця знаходяться під великими входами ... і це важче відстежувати.
додано Автор spacecadet, джерело
Також варто зауважити, що зміна останнього елемента на +1 працює лише для невеликих входів. Деякі місця знаходяться під великими входами ... і це важче відстежувати.
додано Автор spacecadet, джерело
@lightlike In Hand, 6, 3 слід дати 4 (діаграма, що містить питання). Це виглядає так, де цифри вказують, скільки місяців існує пара кролів. [1] [2] [3,1] [1,2] [2,3,1] [3,1,1,2] Я помітив проблему в моєму змінному кількості. Вона друкується таким чином: Кількість: .......... 3, 4, 5, 3. Список: [1, 1, 2, 2, 3, 3] Оператор print (count) знаходиться в циклі мого часу. Що стосується великого вхідного сигналу, автоматична перевірка позначається неправильно на входах, таких як 88 17, навіть після того, як я насильно додаю +1 до останнього елемента.
додано Автор spacecadet, джерело
@lightlike In Hand, 6, 3 слід дати 4 (діаграма, що містить питання). Це виглядає так, де цифри вказують, скільки місяців існує пара кролів. [1] [2] [3,1] [1,2] [2,3,1] [3,1,1,2] Я помітив проблему в моєму змінному кількості. Вона друкується таким чином: Кількість: .......... 3, 4, 5, 3. Список: [1, 1, 2, 2, 3, 3] Оператор print (count) знаходиться в циклі мого часу. Що стосується великого вхідного сигналу, автоматична перевірка позначається неправильно на входах, таких як 88 17, навіть після того, як я насильно додаю +1 до останнього елемента.
додано Автор spacecadet, джерело
Проблема полягає в моєму алгоритмі. Я прийшов до висновку, що все, що живе 3 місяці тому, є мертвим (правда), але не припадає на речі, які не тільки 1 місяць. Іншими словами, я вираховую речі, які вже не живі, правда, але деякі з них вже вимерли.
додано Автор spacecadet, джерело
Проблема полягає в моєму алгоритмі. Я прийшов до висновку, що все, що живе 3 місяці тому, є мертвим (правда), але не припадає на речі, які не тільки 1 місяць. Іншими словами, я вираховую речі, які вже не живі, правда, але деякі з них вже вимерли.
додано Автор spacecadet, джерело
Вирішено та оновлено.
додано Автор spacecadet, джерело
Вирішено та оновлено.
додано Автор spacecadet, джерело
@lightlike додавання <= робить його працювати для 7 поколінь, а не вхід 6. Як і це, він встановлює список, як [1, 1, 2, 2, 3, 3], коли він повинен закінчуватися в 4, а не 3. Інший Наприклад, 7, 4 слід повернути [1, 1, 2, 3, 4, 6, 9]. Замість цього ми отримуємо [1, 1, 2, 3, 4, 6, 8]. Тенденція із кожним тестовим прикладом, здається, полягає в тому, що остання цифра не відображається на 1. . Я можу обманювати і просто змінити це число до повернення ... але це обман;) .. не знаю, чому це робиться.
додано Автор spacecadet, джерело
@lightlike додавання <= робить його працювати для 7 поколінь, а не вхід 6. Як і це, він встановлює список, як [1, 1, 2, 2, 3, 3], коли він повинен закінчуватися в 4, а не 3. Інший Наприклад, 7, 4 слід повернути [1, 1, 2, 3, 4, 6, 9]. Замість цього ми отримуємо [1, 1, 2, 3, 4, 6, 8]. Тенденція із кожним тестовим прикладом, здається, полягає в тому, що остання цифра не відображається на 1. . Я можу обманювати і просто змінити це число до повернення ... але це обман;) .. не знаю, чому це робиться.
додано Автор spacecadet, джерело

6 Відповіді

Це скопійовано з відповіді у питанні 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))
2
додано

Ігноруючи ускладнення, рівняння кількості пари кроликів у поколінні становить

rabbit_pairs

Якщо ми використовуємо список, це ставить проблему, тому що коли 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
1
додано

Використання рекурсії.

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);
}
1
додано

Використання рекурсії.

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);
}
1
додано

Існує 2 випадки рецидивних відносин тут. Розглядаючи n , це число місяців, протягом яких запущено послідовність, а m - це кількість місяців, протягом яких пара буде жити:

1) Якщо індекс у послідовності (на основі нуля) менше, ніж m :
Норма Фібоначчі (поточний термін = попередній термін + попередній термін).

2) If the index is greater than or equal to m:
Current term = sum of (m - 1) previous terms (ignoring the one immediately before).

Ось приклад із послідовністю A та m = 5 :
  A5 = A0 + A1 + A2 + A3 (4 терміни, тобто m - 1 , ігноруючи його безпосередньо перед)
    .
  Якщо m = 3 , то: ::   A3 = A0 + A1 (лише 2 терміни, m - 1 )

.

The code below (in Python) has an offset by 2 because of the initial [1, 1] at the beginning of the sequence.

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
1
додано
Ви можете замінити цикл for j за допомогою new_num = sum (послідовність [i - (m - 2): i + 1]) , що також неможливо визначити.
додано Автор David Cullen, джерело

Існує 2 випадки рецидивних відносин тут. Розглядаючи n , це число місяців, протягом яких запущено послідовність, а m - це кількість місяців, протягом яких пара буде жити:

1) Якщо індекс у послідовності (на основі нуля) менше, ніж m :
Норма Фібоначчі (поточний термін = попередній термін + попередній термін).

2) If the index is greater than or equal to m:
Current term = sum of (m - 1) previous terms (ignoring the one immediately before).

Ось приклад із послідовністю A та m = 5 :
  A5 = A0 + A1 + A2 + A3 (4 терміни, тобто m - 1 , ігноруючи його безпосередньо перед)
    .
  Якщо m = 3 , то: ::   A3 = A0 + A1 (лише 2 терміни, m - 1 )

.

The code below (in Python) has an offset by 2 because of the initial [1, 1] at the beginning of the sequence.

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
1
додано
Ви можете замінити цикл for j за допомогою new_num = sum (послідовність [i - (m - 2): i + 1]) , що також неможливо визначити.
додано Автор David Cullen, джерело
ІТ КПІ - Python
ІТ КПІ - Python
625 учасників

Канал обговорень про всякі штуки зі світу пайтону. Прохання: 0. мати повагу одне до одного; 1. не матюкатися в сторону людей; 2. не захламляти тред повідомленнями по одному слову;