Вибухонебезпечні контейнери (Розбір)

Кожну порожню скриньку позначимо $0$, а скриньку з тротилом $1$. Завдання полягає в тому, щоб знайти кількість рядків довжини $n$, що складаються з $0$ та $1$, таких, що дві одиниці не стоять поруч.

Відповіддю на задачу буде число Фібоначчі $f(n)$:

Приклад

Розглянемо всі можливі башти висоти n = 1, n = 2, n = 3. Кожній з них відповідає послідовність з $0$ та $1$.

• дві башти висоти $1$: $"0","1"$;

• три башти висоти $2$: "00", "01", "10";

• п'ять башт висоти $3$: "000", "001", "010", "100", "101";

Реалізація алгоритму

Оголосимо робочий масив.

#define MAX 45
int fib[MAX];

Заповнимо елементи масиву $fib$ числами Фібоначчі відповідно до рекурентної формули.

fib[1] = 2; fib[2] = 3;
for (int i = 3; i < MAX; i++)
  fib[i] = fib[i - 1] + fib[i - 2];

Читаємо вхідне значення $n$ та виводимо відповідь.

scanf("%d", &n);
printf("%d\n", fib[n]);

Реалізація алгоритму — мемоізація

Оголосимо робочий масив.

#define MAX 45
int fib[MAX];

Функція f обчислює $n$-е число Фібоначчі.

int f(int n)
{
  if (n == 1) return 2;
  if (n == 2) return 3;
  if (fib[n] != -1) return fib[n];
  return fib[n] = f(n - 1) + f(n - 2);
}

Основна частина програми. Читаємо вхідне значення $n$ та виводимо відповідь.

scanf("%d", &n);
memset(fib, -1, sizeof(fib));
printf("%d\n", f(n));

Java реалізація

import java.util.*;

public class Main
{
  static int fib[] = new int[45];
  
  static int f(int n)
  {
    if (n == 1) return 2;
    if (n == 2) return 3;
    if (fib[n] != -1) return fib[n];
    return fib[n] = f(n-1) + f(n - 2);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Arrays.fill(fib, -1);
    System.out.println(f(n));     
    con.close();
  }
}

Python реалізація — список

Заповнимо елементи списку $lst$ числами Фібоначчі відповідно до рекурентної формули.

lst = [0, 2, 3]
for i in range(3, 45):
  lst.append(lst[i - 2] + lst[i - 1])

Читаємо вхідне значення $n$ та виводимо відповідь.

n = int(input())
print(lst[n])

Python реалізація — запам'ятовування

Функція fib обчислює $n$-е число Фібоначчі.

def fib(n):
  if dp[n] != -1:
    return dp[n]
  dp[n] = fib(n - 1) + fib(n - 2)
  return dp[n]

Основна частина програми. Читаємо вхідне значення $n$.

n = int(input())

Список $dp$ буде містити числа Фібоначчі. Ініціалізуємо його початкові значення.

dp = (n + 2) * [-1]
dp[1] = 2
dp[2] = 3

Обчислюємо та виводимо відповідь.

print(fib(n))