Коза Ностра#5103

Коза Ностра (Розбір)

Нехай $g (n)$ — це кількість способів роздати карти $n$ викладачам, вишикуваним у ряд (перший і останній при цьому не вважаються сусідами). Це завдання еквівалентне підрахунку бінарних послідовностей довжини $n$ , що складаються з $0$ та $1$ , у яких ніякі дві одиниці не стоять поруч. Рішенням є послідовність Фібоначчі, задана наступною рекурентною формулою:

g (n) = ⎩ ⎨ ⎧ 2, n = 1, 3, n = 2, g (n - 1) + g (n - 2), n \geq 3.

g(n)= \begin{cases} 2, n = 1, \\ 3, n = 2, \\ g(n - 1) + g(n - 2), n \ge 3. \end{cases}

Нехай $f (n)$ — це кількість способів роздати карти $n$ викладачам, розташованим по колу.

Якщо першому викладачу туз не виданий, то решті $n - 1$ n - 1 викладачам тузи можна роздати $g (n - 1)$ g(n - 1) способами.
Якщо ж першому викладачу виданий туз, то другому і останньому викладачам туз давати не можна. Тоді решті $n - 3$ n - 3 викладачам тузи можна роздати $g (n - 3)$ g(n - 3) способами.

Таким чином, отримуємо співвідношення:

f (n) = g (n - 1) + g (n - 3), якщо n \geq 3

f(n) = g(n - 1) + g(n - 3),~якщо~n \ge 3

Приклад

При $n = 3$ n = 3 нам знадобиться значення $g (0)$ . Його можна знайти з рівності $g (0) + g (1) = g (2)$ g(0) + g(1) = g(2), звідки

g (0) = g (2) - g (1) = 3 - 2 = 1

g(0) = g(2) - g(1) = 3 - 2 = 1

Отже

f (3) = g (2) + g (0) = 3 + 1 = 4

f(3) = g(2) + g(0) = 3 + 1 = 4

Базові випадки мають вигляд:

f (1) = 2 f (2) = 3

f(1) = 2 \\ f(2) = 3

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

Оголосимо масив $f ib$ для зберігання чисел Фібоначчі.

#define MAX 46
int fib[MAX];

Основна частина програми. Обчислюємо числа Фібоначчі.

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

Читаємо вхідне число $n$ .

scanf("%d", &n);

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

if (n == 1) res = 2; else 
if (n == 2) res = 3; else
res = fib[n - 1] + fib[n - 3];

Виводимо відповідь.

printf("%d\n", res);

Java реалізація

import java.util.*;

public class Main 
{
  private static final int MAX = 46;
  public static void main(String[] args) 
  {

Java

Оголосимо масив $f ib$ для зберігання чисел Фібоначчі.

    int[] fib = new int[MAX];

Обчислюємо числа Фібоначчі.

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

Читаємо вхідне число $n$ .

    Scanner con = new Scanner(System.in);
    int n = con.nextInt();

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

    int res;
    if (n == 1) res = 2;
    else if (n == 2) res = 3;
    else res = fib[n - 1] + fib[n - 3];

Виводимо відповідь.

    System.out.println(res);
  }
}

Python реалізація

Оголосимо список $f ib$ для зберігання чисел Фібоначчі.

fib = [0] * 46

Обчислюємо числа Фібоначчі.

fib[0] = 1
fib[1] = 2
for i in range(2, 46):
  fib[i] = fib[i - 1] + fib[i - 2]

Читаємо вхідне число $n$ .

n = int(input())

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

if n == 1: res = 2
elif n == 2: res = 3
else: res = fib[n - 1] + fib[n - 3]

Виводимо відповідь.

print(res)