Соти (Розбір)

Пронумеруємо всі соти послідовно зліва направо, зверху вниз, як показано на схемі. При цьому:

• соти верхнього ряду мають непарні номери;

• соти нижнього ряду мають парні номери.

Якщо у верхньому ряду міститься $n$ сот, то найправа сота верхнього ряду матиме номер 2n - 1.

Позначимо через $f(k)$ кількість способів потрапити з першої соти в соту з номером $k$. Оскільки бджола повинна потрапити в соту номер 2n - 1, то відповіддю до задачі буде значення f(2n - 1).

Розглянемо переходи по сотах.

• Нехай сота $k$ знаходиться у верхньому ряду (непарний номер). Тоді бджола може потрапити в неї або з соти з номером k - 2, або з соти з номером k - 3. Відповідно, для непарних $k$ виконується рекурентне співвідношення:

• Нехай сота $k$ знаходиться у нижньому ряду (парний номер). Тоді можливий лише один варіант переходу — з попередньої соти:

Для реалізації рекурсії необхідно задати початкові значення:

Вони легко перевіряються безпосередньо за схемою руху бджоли.

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

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

#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]);

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

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

int fib[90];

Реалізуємо рекурсивне обчислення функції f з використанням мемоізації.

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);
}

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

scanf("%d",&n);

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

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

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();
  }
}