Kosa Nostro#5103

Kosa Nostro (Həll təhlili)

Tutaq ki, $g (n)$ — xət ilə düzülmüş $n$ müəllimə kartları paylama üsullarının sayıdır (bu zaman ilk və sonuncu qonşu hesab edilmir). Bu məsələ, heç bir iki ədədinin yan-yana olmadığı uzunluqları $n$ olan ikilik ardıcıllıqların sayını hesablamaqla ekvivalentdir. Həll Fibonaccinin ardıcıllığıdır ki, aşağıdakı rekursiv düsturla verilir:

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}

Tutaq ki, $f (n)$ — dairəvi şəkildə yerləşən $n$ müəllimə kart paylama üsullarının sayıdır.

Əgər birinci müəllimə tüz verilməyibsə, onda qalan $n - 1$ n - 1 müəllimlərə tüzləri $g (n - 1)$ g(n - 1) şəkildə paylamaq olar.
Əgər birinci müəllimə tüz verilibsə, onda ikinci və sonuncu müəllimlərə tüz vermək olmaz. Bu halda qalan $n - 3$ n - 3 müəllimlərə tüzləri $g (n - 3)$ g(n - 3) şəkildə paylamaq olar.

Beləliklə, aşağıdakı ifadəni alırıq:

f (n) = g (n - 1) + g (n - 3), ə g ə r n \geq 3

f(n) = g(n - 1) + g(n - 3),~əgər~n \ge 3

Nümunə

$n = 3$ n = 3 üçün bizə $g (0)$ dəyəri lazım olacaq. Bu $g (0) + g (1) = g (2)$ g(0) + g(1) = g(2) bərabərliyindən tapıla bilər, buradan isə

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

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

Beləliklə

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

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

Əsas hallar aşağıdakı kimidir:

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

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

Alqoritmin reallaşdırılması

Fibonacci ədədlərini saxlamaq üçün $f ib$ massivi elan edirik.

#define MAX 46
int fib[MAX];

Proqramın əsas hissəsi. Fibonacci ədədlərini hesablayırıq.

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

Girişdə olan $n$ ədədini oxuyuruq.

scanf("%d", &n);

Cavab $r es$ -i hesablayırıq.

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

Cavabı çap edirik.

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

Java reallaşdırılması

import java.util.*;

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

Java

Fibonacci ədədlərini saxlamaq üçün $f ib$ massivi elan edirik.

    int[] fib = new int[MAX];

Fibonacci ədədlərini hesablayırıq.

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

Girişdə olan $n$ ədədini oxuyuruq.

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

Cavab $r es$ -i hesablayırıq.

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

Cavabı çap edirik.

    System.out.println(res);
  }
}

Python reallaşdırılması

Fibonacci ədədlərini saxlamaq üçün $f ib$ siyahısı elan edirik.

fib = [0] * 46

Fibonacci ədədlərini hesablayırıq.

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

Girişdə olan $n$ ədədini oxuyuruq.

n = int(input())

Cavab $r es$ -i hesablayırıq.

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

Cavabı çap edirik.

print(res)