Alqoritm Analizi

Gəlin $n$ uzunluğunda axtarılan 0 və 1 ardıcıllıqlarının sayını $f(n)$ ilə işarə edək. Ardıcıllığın ilk mövqeyi 0 əgər içərsə, onda ikinci mövqeydən başlayaraq $f(n-1)$ ardıcıllıq qura bilərik. İlk mövqe 1 əgər içərsə, ikinci mövqe üçün hər iki variant mümkündür. 0 varsa, növbəti $n-2$ boş mövqelərdə $f(n-2)$ ardıcıllıq qura bilərik. 1 varsa, üçüncü mövqedə 0 olmalıdır və dördüncü mövqedən başlayaraq $f(n-3)$ ardıcıllıq qura bilərik.

Bizdə təkrarlanma əlaqəsi var: $f(n)=f(n-1)+f(n-2)+f(n-3)$. İlkin dəyərləri hesablamaq qalır:

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

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

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

Nümunə

Alqoritm Tətbiqi

f adlı bir massiv elan edin, burada f(1), f(2), …, f(n) dəyərlərini saxlayacağıq.

int f[100010];

Giriş dəyəri n-i oxuyun.

scanf("%d",&n);

Massivin müvafiq hüceyrələrində f(1), f(2), və f(3) dəyərlərini saxlayın.

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

Təkrarlanma formulundan istifadə edərək f(i) dəyərini hesablayın. Hesablamaları 12345-ə bölərək edin.

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

Cavabı çıxarın.

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

Alqoritm Tətbiqi – Rekursiya + Memoizasiya

Nəticələri memoizasiya etmək üçün dp adlı bir massiv elan edin: dp[i] f(i) dəyərini saxlayacaq.

int dp[100001];

f(n) funksiyasını tətbiq edin – uzunluğu $n$ olan 0 və 1 ardıcıllıqlarının sayı. Memoizasiya texnikasından istifadə edin.

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. Giriş dəyəri n-i oxuyun.

scanf("%d",&n);

dp massivini başlanğıc qiymətlərlə doldurun.

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

f(n) dəyərini hesablayın və çıxarın.

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

Java Tətbiqi

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 Tətbiqi

n = int(input())

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

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

print(dp[n])

Python Tətbiqi – Rekursiya ilə Memoizasiya

Rekursiya üçün yığın ölçüsünü artırın.

import sys
sys.setrecursionlimit(10000)

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]

n = int(input())

dp = [-1] * 100001

print(f(n))