Azalan ədəd (Həll təhlili)

$n$ ədədini $1$-ə çevirmək üçün tələb olunan minimum əməliyyat sayını $f(n)$ ilə işarə edək. Məsələn,

• f(1) = 0, çünki artıq $1$ ədədinə sahibik;

• f(2) = 1, 2 → 1 əməliyyatını yerinə yetiririk;

• f(5) = 3, 5 → 4 → 2 → 1 əməliyyatlarını yerinə yetiririk;

• f(10) = 3, 10 → 9 → 3 → 1 əməliyyatlarını yerinə yetiririk;

n = 10 halında, acgöz yanaşmadan istifadə edib $2$-yə bölmək əvəzinə əvvəlcə $1$ çıxmaq daha sərfəlidir.

$f(n)$ funksiyasının hesablanması prosesinə baxaq.

• Əgər $n$ ədədini $3$-ə bölsək (fərz edək ki, $n$ ədədi $3$-ə bölünür), onda

  f(n) = f(n / 3) + 1

• Əgər $n$ ədədini $2$-yə bölsək (fərz edək ki, $n$ ədədi $2$-yə bölünür), onda

  f(n) = f(n / 2) + 1

• Əgər $n$ ədədindən $1$ çıxsaq, onda

  f(n) = f(n - 1) + 1

$n$ ədədindən $n/3$, $n/2$ və ya n - 1 ədədlərindən birini əldə edə bilərik. Bu ədədlərin hər birini $1$-ə endirmək üçün tələb olunan əməliyyat sayı müvafiq olaraq $f(n/3)$, $f(n/2)$ və f(i - 1)-ə bərabərdir. Bizi minimum əməliyyat sayı maraqlandırdığından, aşağıdakı əlaqəyə sahibik:

Əgər $n$ ədədi $2$-yə (və ya $3$-ə) bölünmürsə, onda $min$ funksiyasında müvafiq element ($f(n/2)$ və ya $f(n/3)$) olmur. Məsələn, n = 8 üçün:

Eyni şəkildə, n = 7 üçün əldə edirik:

$f(n)$ funksiyasının qiymətləri d[MAX] massivinin xanalarında saxlanılacaq, burada MAX = 10^6 + 1. $d$ massivinin xanalarını $1$-dən 10^6-a qədər verilmiş rekurrent asılılığa uyğun doldurun. Məsələn, aşağıdakı cədvəldə 1 \le i \le 11 üçün $d[i]$ qiymətləri göstərilib:

Məsələn,

Başqa sözlə, $10$-u $2$-yə bölmək əvəzinə ondan $1$ çıxmaq daha səmərəlidir.

Məşq

Aşağıdakı $i$ qiymətləri üçün $d[i]$ qiymətlərini tapın:

Alqoritmin tətbiqi

$d$ massivini elan edin, burada $i$-ci xana $i$ ədədini $1$-ə çevirmək üçün tələb olunan minimum əməliyyat sayını saxlayır.

#define MAX 1000001
int d[MAX];

$d$ massivinin xanalarını verilmiş düsturlara uyğun doldurun.

d[1] = 0;
for (i = 2; i < MAX; i++)
{
  // d[i] = min(d[i/3],d[i/2],d[i-1]) + 1
  d[i] = d[i - 1];
  if (i % 2 == 0) d[i] = min(d[i], d[i / 2]);
  if (i % 3 == 0) d[i] = min(d[i], d[i / 3]);
  d[i]++;
}

Hər bir $n$ giriş qiyməti üçün $d[n]$ cavabını çap edin.

while(scanf("%d",&n) == 1)
  printf("%d\n",d[n]);

Alqoritmin tətbiqi — rekursiya

#include <stdio.h>
#include <string.h>
#define INF 2000000000

int i, res, n;
int dp[1000001];

int min(int a, int b, int c)
{
  int res = a;
  if (b < res) res = b;
  if (c < res) res = c;
  return res;
}

int f(int n)
{
  if (n == 1) return 0;
  if (dp[n] != -1) return dp[n];
  int a = f(n - 1);
  int b = (n % 2 == 0) ? f(n / 2) : INF;
  int c = (n % 3 == 0) ? f(n / 3) : INF;
  return dp[n] = min(a,b,c) + 1;
}

int main(void)
{
  memset(dp, -1, sizeof(dp));
  while (scanf("%d", &n) == 1)
  {
    res = f(n);
    printf("%d\n", res);
  }
  return 0;
}

Java tətbiqi

import java.util.*;

public class Main
{
  public static int MAX = 1000001;    
  static int d[] = new int[MAX];

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    d[1] = 0;
    for(int i = 2; i < MAX; i++)
    {
      d[i] = d[i-1] + 1;
      if (i % 2 == 0) d[i] = Math.min(d[i], d[i/2] + 1);
      if (i % 3 == 0) d[i] = Math.min(d[i], d[i/3] + 1);
   }

    while(con.hasNext())
    {
      int n = con.nextInt();
      System.out.println(d[n]);
    }
  }
}

Python tətbiqi

$d$ siyahısını yaradın, burada $i$-ci xana $i$ ədədini $1$-ə çevirmək üçün tələb olunan minimum əməliyyat sayını saxlayır.

d = [0] * 1000001

$d$ massivinin xanalarını verilmiş düsturlara uyğun doldurun.

d[1] = 0
for i in range(2, 1000001):
  d[i] = d[i - 1]
  if i % 2 == 0 and d[i // 2] < d[i]:
    d[i] = d[i // 2]
  if i % 3 == 0 and d[i // 3] < d[i]:
    d[i] = d[i // 3]
  d[i] += 1

Hər bir $n$ giriş qiyməti üçün $d[n]$ cavabını çap edin.

while True:
  try:
    n = int(input())
    print(d[n])
  except EOFError:
    break