Pətək (Həll təhlili)

Bütün hüceyrələri soldan sağa, yuxarıdan aşağıya ardıcıl nömrələyək, şəkildə göstərildiyi kimi. Beləliklə:

• yuxarı sıra hüceyrələri tək nömrələniblər;

• aşağı sıra hüceyrələri cüt nömrələniblər.

Əgər yuxarı sırada $n$ hüceyrə varsa, onda yuxarı sıranın ən sağındakı hüceyrə 2n - 1 nömrəyə malik olacaq.

$f(k)$ ilə birinci hüceyrədən nömrəsi $k$ olan hüceyrəyə çatmağın sayını göstərək. Arının 2n - 1 nömrəli hüceyrəyə çatmalı olduğundan, problemin cavabı f(2n - 1) əvəzləməsidir.

Hüceyrələr üzrə keçidləri nəzərdən keçirək.

• Tutaq ki, hüceyrə $k$ yuxarı sıradadır (tək nömrə). Bu halda arı ya k - 2 nömrəli hüceyrədən, ya da k - 3 nömrəli hüceyrədən keçə bilər. Deməli, tək $k$ üçün rekursiv olma şərti:

• Tutaq ki, hüceyrə $k$ aşağı sıradadır (cüt nömrə). Bu halda, yalnız bir keçid variantı mümkündür — əvvəlki hüceyrədən:

Rekursiyası həyata keçirmək üçün başlanğıc dəyərlər tapmaq lazımdır:

Bunlar arının hərəkət ardıcıllığına asanlıqla yoxlanılır.

Alqoritmin həyata keçirilməsi

İşçi massiv elan edək.

#define MAX 100
int fib[MAX];

$fib$ massivinin elementlərini rekursiv olma şərti ilə dolduraq.

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

$n$ dəyərini oxuyuruq və cavabı çıxarırıq f(2n - 1).

scanf("%d",&n);
printf("%d\n",fib[2*n-1]);

Alqoritmi həyata keçirilməsi – rekursiya + yaddaş

İşçi massiv elan edək.

int fib[90];

Məmoizasiya istifadə edərək f funksiyasının rekursiv hesablama keçirilməsini həyata keçirin.

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

Proqramın əsas hissəsi. Giriş dəyəri $n$ oxuyuruq.

scanf("%d",&n);

Hesablama və cavabı çıxarmaq.

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

Java həyata keçirilməsi

import java.util.*;

public class Main
{
  static int fib[] = new int[90];    
  
  static int f(int n)
  {
    if (n <= 3) return 1;
    if (fib[n] != -1) return fib[n];
    if (n % 2 == 1) return fib[n] = f(n - 1) + f(n - 3);
    return fib[n] = f(n - 1);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Arrays.fill(fib, -1);
    System.out.println(f(2*n-1));     
    con.close();
  }
}