Üç bir (Həll təhlili)

$n$ uzunluğunda $0$ və $1$-lərdən ibarət axtarılan ardıcıllıqların sayını $f(n)$ ilə işarə edək. Ardıcıllığın qurulmasına birinci simvola görə baxaq.

Əgər birinci yerdə $0$ dayanırsa, onda ardıcıllığın qalan hissəsi n - 1 uzunluğunda istənilən düzgün ardıcıllıq ola bilər. Deməli, bu cür variantların sayı f(n - 1)-dir.

Əgər birinci yerdə $1$ dayanırsa, onda mümkün davamlara baxaq:

• əgər ikinci yerdə $0$ dayanırsa, onda qalan n - 2 mövqe n - 2 uzunluğunda istənilən düzgün ardıcıllığı təşkil edir, yəni f(n - 2) variant;

• əgər ikinci yerdə $1$ dayanırsa, onda ard-arda üç vahidin yaranmasının qarşısını almaq üçün üçüncü yerdə mütləq $0$ olmalıdır. Bundan sonra n - 3 mövqe qalır, onları istənilən düzgün ardıcıllıqla doldurmaq olar, yəni f(n - 3) variant.

Beləliklə, aşağıdakı rekurrent asılılığı alırıq:

Qalır ki, ilkin qiymətləri hesablayaq:

• f(1) = 2, çünki $1$ uzunluğunda iki ardıcıllıq mövcuddur: $0$ və $1$.

• f(2) = 4, çünki $2$ uzunluğunda dörd ardıcıllıq mövcuddur: $00,01,10$ və $11$.

• f(3) = 7, çünki $3$ uzunluğunda yeddi ardıcıllıq mövcuddur: 000, 001, 010, 011, 100, 101 və $110$.

Nümunə

Alqoritmin realizasiyası

f(1), f(2), ..., f(n) qiymətlərini saxlayacağımız $f$ massivini elan edək.

int f[100010];

$n$ giriş qiymətini oxuyuruq.

scanf("%d",\&n);

Massivin baza qiymətlərini ilkinləşdiririk.

f[1] = 2; f[2] = 4; f[3] = 7;

$f(i)$ qiymətlərini rekurrent düstura görə hesablayırıq. Bütün hesablamaları $12345$ modulu üzrə aparırıq.

for(i = 4; i <= n; i++)
  f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

Cavabı çap edirik.

printf("%d\n",f[n]);

Alqoritmin realizasiyası – rekursiya + yaddaşda saxlama

Aralıq nəticələri saxlamaq üçün $dp$ massivini elan edək:

• $dp[i]$ $f(i)$ qiymətini saxlayacaq

int dp[100001];

$n$ uzunluğunda $0$ və $1$-lərdən ibarət axtarılan ardıcıllıqların sayını qaytaran $f(n)$ funksiyasını realizə edirik. Memoizasiya texnikasından istifadə edirik.

int f(int n)
{
  if (n == 1) return 2;
  if (n == 2) return 4;
  if (n == 3) return 7;
  if (dp[n] != -1) return dp[n];
  return dp[n] = (f(n-1) + f(n-2) + f(n-3)) % 12345;
}

Proqramın əsas hissəsi. $n$ giriş qiymətini oxuyuruq.

scanf("%d",\&n);

$dp$ massivini ilkinləşdiririk.

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

$f(n)$ qiymətini hesablayıb çap edirik.

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

Java realizasiyası

import java.util.*;

public class Main
{
  public static int MAX = 100010;
  static int f[] = new int[MAX];

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    f[1] = 2; f[2] = 4; f[3] = 7;
    for(int i = 4; i <= n; i++)
      f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
    System.out.println(f[n]);
    con.close();
  }
}

Python realizasiyası

$n$ giriş qiymətini oxuyuruq.

n = int(input())

$dp$ siyahısını ilkinləşdiririk. Müvafiq xanalara f(1), f(2) və $f(3)$ qiymətlərini yerləşdiririk.

dp = [0] * (n + 4)
dp[1], dp[2], dp[3] = 2, 4, 7

$f(i)$ qiymətlərini rekurrent düstura görə hesablayırıq. Bütün hesablamaları $12345$ modulu üzrə aparırıq.

for i in range(4, n + 1):
  dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 12345;

Cavabı çap edirik.

print(dp[n])

Python realizasiyası – yaddaşda saxlama ilə rekursiya

Rekursiya üçün stəki artıraq.

import sys
sys.setrecursionlimit(10000)

$n$ uzunluğunda $0$ və $1$-lərdən ibarət axtarılan ardıcıllıqların sayını qaytaran $f(n)$ funksiyasını realizə edirik. Memoizasiya texnikasından istifadə edirik.

def f(n):
  if n == 1: return 2
  if n == 2: return 4
  if n == 3: return 7
  if dp[n] != -1: return dp[n]

  dp[n] = (f(n - 1) + f(n - 2) + f(n - 3)) % 12345
  return dp[n]

Proqramın əsas hissəsi. $n$ giriş qiymətini oxuyuruq.

n = int(input())

$dp$ siyahısını ilkinləşdiririk.

dp = [-1] * 100001

$f(n)$ qiymətini hesablayıb çap edirik.

print(f(n))