Vahidlərin sayı#44

Vahidlərin sayı (Həll təhlili)

$f (n)$ — verilmiş $n$ ədədini ifadə etmək üçün istifadə oluna bilən minimal vahidlərin (bir ədədlərin) sayı olsun. Aydındır ki, $f (1) = 1$ f(1) = 1.

$2$ ədədini yalnız iki vahidin cəmi kimi göstərmək olar: $2 = 1 + 1$ 2 = 1 + 1. Buna görə $f (2) = 2$ f(2) = 2. Eynilə, $3$ ədədi yalnız üç vahidin cəmi şəklində göstərilir: $3 = 1 + 1 + 1$ 3 = 1 + 1 + 1. Buna görə $f (3) = 3$ f(3) = 3.

$4$ ədədini ya dörd vahidin cəmi kimi: $4 = 1 + 1 + 1 + 1$ 4 = 1 + 1 + 1 + 1, ya da hasil kimi yazmaq olar: $4 = (1 + 1) \cdot (1 + 1)$ 4 = (1 + 1) \cdot (1 + 1). Lakin hər iki halda $4$ vahid istifadə olunur, buna görə $f (4) = 4$ f(4) = 4.

Dəyəri $n$ -ə bərabər olan ifadəyə baxaq.

1. Fərz edək ki, son yerinə yetirilən əməliyyat toplamadır. Tutaq ki, bir toplanan $i$ -yə bərabərdir və $f (i)$ vahiddən ibarətdir, ikinci toplanan isə $n - i$ n - i-yə bərabərdir və $f (n - i)$ f(n - i) vahiddən ibarətdir. Onda $i$ qiymətini elə seçmək lazımdır ki, $f (i) + f (n - i)$ f(i) + f(n - i) cəmi minimal olsun.

Bu zaman $i$ qiymətini $n /2$ -yə qədər perebirat etmək kifayətdir, çünki birinci toplananın ikincidən böyük olmadığını fərz etmək olar. Beləliklə, aşağıdakı münasibəti alırıq:

f (n) = 1 \leq i \leq n /2 min (f (i) + f (n - i))

f(n) = \min_{1 \le i \le n/2} (f(i)+f(n - i))

2. Fərz edək ki, son yerinə yetirilən əməliyyat vurmadır. Tutaq ki, birinci vuruq $i$ $f (i)$ vahiddən, ikinci vuruq $n / i$ isə $f (n / i)$ vahiddən ibarətdir. Bu hal o zaman baş verir ki, $n$ $i$ -yə qalıqsız bölünsün.

$i$ qiymətini elə seçmək lazımdır ki, $f (i) + f (n / i)$ f(i) + f(n / i) cəmi minimal olsun. Bu zaman $i$ qiymətlərini $2$ -dən $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor-ə qədər olan diapazonda perebirat etmək kifayətdir. Beləliklə, aşağıdakı münasibəti alırıq:

f (n) = 1 \leq i \leq n min (f (i) + f (n / i))

f(n) = \min_{1 \le i \le \sqrt{n}} (f(i)+f(n/i))

Beləliklə

f (n) = min (1 \leq i \leq n /2 min (f (i) + f (n - i)), 1 \leq i \leq n min (f (i) + f (n / i)))

f(n) = \min\left( \min_{1 \le i \le n/2} \bigl(f(i) + f(n - i)\bigr),\; \min_{1 \le i \le \sqrt{n}} \bigl(f(i) + f(n / i)\bigr) \right)

Nümunə

$n = 7$ n = 7 üçün cavabı hesablayaq:

f (7) = f (6) + f (1) = (f (2) + f (3)) + f (1) = 2 + 3 + 1 = 6

f(7) = f(6) + f(1) = (f(2) + f(3)) + f(1) = 2 + 3 + 1 = 6

$7$ ədədini $6$ vahid vasitəsilə göstərmək olar, məhz:

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

Alqoritmin realizasiyası

$r es$ massivini elan edək.

int res[5001];

$n$ giriş qiymətini oxuyuruq.

scanf("%d",&n);

$r es [1] = 1$ res[1] = 1 inisializasiya edirik.

res[1] = 1;

Sonra yuxarıda verilmiş düstura əsasən $r es [2], r es [3], ..., r es [n]$ res[2], res[3], ..., res[n] qiymətlərini ardıcıl olaraq hesablayırıq.

for (i = 2; i <= n; i++)
{
  res[i] = i;
  for (j = 1; 2 * j < i; j++)
    if (res[j] + res[i - j] < res[i]) res[i] = res[j] + res[i - j];
  for (j = 2; j * j <= i; j++)
    if (i % j == 0) 
      if (res[j] + res[i / j] < res[i]) res[i] = res[j] + res[i / j];
}

C++

Cavabı çap edirik.

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