Alqoritm təhlili

$f(n)$-i $n$ ədədini təşkil edə biləcək ən kiçik birliklərin sayına bərabər edək. Açıq-aydındır ki, $f(1)=1$.

2 ədədi yalnız iki birliyin cəmi kimi təqdim etmək olar: $2=1+1$. Buna görə, $f(2)=2$. 3 ədədi yalnız üç birliyin cəmi kimi təqdim etmək olar: $3=1+1+1$. Buna görə, $f(3)=3$.

4 ədədi ya $4=1+1+1+1$ kimi, ya da $4=(1+1)\ast (1+1)$ kimi təqdim etmək olar. Lakin, hər iki halda dörd birlik istifadə edilir. Buna görə, $f(4)=4$.

Axtarılan ifadəni nəzərdən keçirək, nəticəsi $n$-ə bərabərdir.

Fərz edək ki, son əməliyyat toplama olub. Məsələn, birinci toplanan $i$ $f(i)$ birlikdən ibarətdir və ikinci toplanan $n-i$ $f(n-i)$ birlikdən ibarətdir. $i$ dəyəri belə seçilməlidir ki, $f(i)+f(n-i)$ cəmi minimal olsun.

Eyni zamanda, $i$ dəyərini $n/2$-yə qədər iterasiya 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ət qüvvədədir:

Fərz edək ki, son əməliyyat vurma olub. Məsələn, birinci çarpan $i$ $f(i)$ birlikdən ibarətdir və ikinci çarpan $n/i$ $f(n/i)$ birlikdən ibarətdir. Bu hal $n$ $i$-yə bölünərsə baş verir.

$i$ dəyəri belə seçilməlidir ki, $f(i)+f(n/i)$ cəmi minimal olsun. $i$ dəyərini 2-dən $\sqrt{n}$-ə qədər iterasiya etmək kifayətdir. Aşağıdakı münasibət qüvvədədir:

Beləliklə

Nümunə

$f(n)=7$ üçün cavabı hesablayaq:

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

7 ədədi 6 birliklə təqdim edilə bilər, yəni:

$7=(1+1)\ast (1+1+1)+1$

int res[5001];
scanf("%d",&n);
res[1] = 1;

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];
}
printf("%d\n",res[n]);