5092. Соты

Пчелка в сотах может ходить так, как показано на рисунке – ходами 1 и 2 из верхнего ряда и ходом 3 из нижнего.

Вход. Количество шестиугольников n (1 ≤ n ≤ 45) в верхнем ряду, в нижнем ряду их число на 1 меньше.

Выход. Выведите число способов добраться из первой клетки верхнего ряда до последней клетки этого же ряда.

Пример входа	Пример выхода
3	2

РЕШЕНИЕ

динамическое программирование – числа Фибоначчи

Анализ алгоритма

Пронумеруем соты следующим образом:

Пусть f(k) – количество способов попасть из первой соты в k-ую. Если верхний ряд содержит n сот, то номер самой правой соты верхнего ряда имеет номер 2n – 1. Таким образом ответом к задаче будет значение f(2n – 1).

Если k-ая сота расположена в верхнем ряду, то в нее можно попасть либо из (k – 2)-ой соты, либо из (k – 3)-ей. То есть f(k) = f(k – 2) + f(k – 3) при нечетном k.

Если k-ая сота расположена в нижнем ряду, то в нее можно попасть только из (k – 1)-ой. То есть f(k) = f(k – 1) при четном k.

Базовые случаи посчитаем отдельно: f(1) = 1, f(2) = 1, f(3) = 1.

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

Объявим рабочий массив.

#define MAX 100

int fib[MAX];

Заполним ячейки массива fib согласно рекуррентности.

fib[0] = 0; fib[1] = 1; fib[2] = 1;

for(int i = 3; i < MAX; i++)

if (i % 2 == 1) fib[i] = fib[i-2] + fib[i-3];

else fib[i] = fib[i-1];

Читаем значение n и выводим ответ f(2n – 1).

scanf("%d",&n);

printf("%d\n",fib[2*n-1]);

Реализация алгоритма – рекурсия + запоминание

#include <stdio.h>

#include <string.h>

int n, fib[90];

int f(int n)

{

if (n == 1) return 1;

if (n == 2) return 1;

if (n == 3) return 1;

if (fib[n] != -1) return fib[n];

if (n % 2 == 1) return fib[n] = f(n - 1) + f(n - 3);

return fib[n] = f(n - 1);

}

int main(void)

{

scanf("%d",&n);

memset(fib,-1,sizeof(fib));

printf("%d\n",f(2*n-1));

return 0;

}

Java реализация

import java.util.*;

public class Main

{

static int fib[] = new int[90];

static int f(int n)

{

if (n <= 3) return 1;

if (fib[n] != -1) return fib[n];

if (n % 2 == 1) return fib[n] = f(n - 1) + f(n - 3);

return fib[n] = f(n - 1);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Arrays.fill(fib, -1);

System.out.println(f(2*n-1));

con.close();

}

}