Partlayıcı konteynerlər (Həll təhlili)

Hər boş qutunu $0$, TNT olan qutunu isə $1$ ilə qeyd edək. Tapşırıq $0$ və $1$ dəyərlərindən ibarət, uzunluğu $n$ olan sətirlərin sayını tapmaqdan ibarətdir ki, iki ədəd yanaşı olmasın.

Məsələnin cavabı Fibonacci ədədi $f(n)$ olacaq:

Məsələnin həlli

Uzunluğu n = 1, n = 2, n = 3 olan müxtəlif qüllələri nəzərdən keçirək. Hər biri $0$ və $1$ ardıcıllığı ilə uyğun gəlir.

• uzunluğu $1$ olan iki qüllə: $"0","1"$;

• uzunluğu $2$ olan üç qüllə: "00", "01", "10";

• uzunluğu $3$ olan beş qüllə: "000", "001", "010", "100", "101";

Alqoritmin realizasiyası

İşçi massiv elan edək.

#define MAX 45
int fib[MAX];

Massivin $fib$ elementlərini rekurent formulaya uyğun olaraq Fibonacci ədədləri ilə doldururuq.

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

Daxil olan $n$ dəyərini oxuyuruq və cavabı çap edirik.

scanf("%d", &n);
printf("%d\n", fib[n]);

Alqoritmin realizasiyası — memorizasiya

İşçi massiv elan edək.

#define MAX 45
int fib[MAX];

f funksiyası $n$-ci Fibonacci ədədini hesablayır.

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

Proqramın əsas hissəsi. Daxil olan $n$ dəyərini oxuyuruq və cavabı çap edirik.

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

Java realizasiyası

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 realizasiyası — siyahı

Siyahı $lst$-nın elementlərini rekurent formulaya uyğun olaraq Fibonacci ədədləri ilə doldururuq.

lst = [0, 2, 3]
for i in range(3, 45):
  lst.append(lst[i - 2] + lst[i - 1])

Daxil olan $n$ dəyərini oxuyuruq və cavabı çap edirik.

n = int(input())
print(lst[n])

Python realizasiyası — memorizasiya

fib funksiyası $n$-ci Fibonacci ədədini hesablayır.

def fib(n):
  if dp[n] != -1:
    return dp[n]
  dp[n] = fib(n - 1) + fib(n - 2)
  return dp[n]

Proqramın əsas hissəsi. Daxil olan $n$ dəyərini oxuyuruq.

n = int(input())

Siyahı $dp$ Fibonacci ədədlərini saxlayacaq. Onun başlanğıc dəyərlərini təyin edirik.

dp = (n + 2) * [-1]
dp[1] = 2
dp[2] = 3

Hesablama aparırıq və cavabı çap edirik.

print(fib(n))