5091. Взрывоопасные
контейнеры
Все
контейнеры в мире делятся на две категории – с тротилом и без. Только глупец
поставит ящик с тротилом на другой ящик с тротилом. Поскольку вы не глупец
(хм…), вы точно знаете, что тротил взрывается, особенно,
если на нем стоит еще один ящик с тротилом. Вы находитесь в комнате, в которой
находятся ящики обоих видов в гигантском количестве. Вдруг в комнате из люка
появляется подъемник. Он сбоит. Он вознамерился построить башню из n ящиков. Для того, чтобы оценить ваши
шансы на выживание, вам надо посчитать количество исходов, при которых ничего
не взорвется.
Кстати,
а что такой здравомыслящий человек, как вы, делает в комнате с кучей тротила?
Вход. Одно число n (1 ≤ n < 45).
Выход. Выведите количество хороших
исходов.
|
Пример
входа 1 |
Пример
выхода 1 |
|
1 |
2 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
2 |
3 |
РЕШЕНИЕ
числа
Фибоначчи
Анализ алгоритма
Пустой ящик
закодируем 0, ящик с тротилом – 1. В задаче следует найти количество строк
длины n из 0 и 1, в которых две единицы не стоят
рядом. Ответом на
задачу будет число Фибоначчи f(n):
Пример
Рассмотрим всевозможные
башни высоты n = 1, n = 2, n = 3. Каждой из них
соответствует последовательность из 0 и 1. Имеются:
·
две башни высоты 1;
·
три башни высоты 2;
·
пять башен высоты 3;
Реализация алгоритма
Объявим рабочий
массив.
#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]);
Реализация алгоритма –
меморизация
#include <stdio.h>
#include <string.h>
#define MAX 45
int n, fib[MAX];
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);
}
int main(void)
{
scanf("%d", &n);
memset(fib,
-1, sizeof(fib));
printf("%d\n", f(n));
return 0;
}
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 = [0, 2, 3]
for i in range(3, 45):
lst.append(lst[i - 2] + lst[i - 1])
n = int(input())
print(lst[n])
Python реализация – запоминание
n = int(input())
dp = (n + 2) * [-1]
def fib(n):
if dp[n] != -1:
return dp[n]
dp[n] = fib(n - 1) + fib(n - 2)
return dp[n]
dp[1] = 2
dp[2] = 3
print(fib(n))