Numero di unità#44

Numero di unità (Editoriale)

Sia $f (n)$ — il numero minimo di unità con cui si può rappresentare il numero $n$ . Ovviamente, $f (1) = 1$ f(1) = 1.

Il numero $2$ può essere rappresentato solo come somma di due unità: $2 = 1 + 1$ 2 = 1 + 1. Quindi $f (2) = 2$ f(2) = 2. Analogamente, il numero $3$ si rappresenta solo come somma di tre unità: $3 = 1 + 1 + 1$ 3 = 1 + 1 + 1. Quindi $f (3) = 3$ f(3) = 3.

Il numero $4$ può essere scritto sia come somma di quattro unità: $4 = 1 + 1 + 1 + 1$ 4 = 1 + 1 + 1 + 1, sia come prodotto: $4 = (1 + 1) \cdot (1 + 1)$ 4 = (1 + 1) \cdot (1 + 1). Tuttavia in entrambi i casi si utilizzano $4$ unità, quindi $f (4) = 4$ f(4) = 4.

Consideriamo un'espressione il cui valore sia uguale a $n$ .

1. Supponiamo che l'ultima operazione eseguita sia l'addizione. Sia un addendo uguale a $i$ e composto da $f (i)$ unità, e il secondo addendo uguale a $n - i$ n - i e composto da $f (n - i)$ f(n - i) unità. Allora il valore di $i$ va scelto in modo che la somma $f (i) + f (n - i)$ f(i) + f(n - i) sia minima.

In questo caso è sufficiente far variare il valore di $i$ fino a $n /2$ , poiché si può assumere che il primo addendo non superi il secondo. In questo modo otteniamo la seguente relazione:

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. Supponiamo che l'ultima operazione eseguita sia la moltiplicazione. Supponiamo che il primo fattore $i$ sia composto da $f (i)$ unità, e il secondo fattore $n / i$ sia composto da $f (n / i)$ unità. Questo caso si verifica se $n$ è divisibile per $i$ senza resto.

Il valore di $i$ va scelto in modo che la somma $f (i) + f (n / i)$ f(i) + f(n / i) sia minima. In questo caso è sufficiente far variare i valori di $i$ nell'intervallo da $2$ a $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor. In questo modo otteniamo la seguente relazione:

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))

Quindi

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)

Esempio

Calcoliamo la risposta per $n = 7$ n = 7:

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

Il numero $7$ può essere rappresentato con $6$ unità, precisamente:

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

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

Implementazione dell'algoritmo

Dichiariamo un array $r es$ .

int res[5001];

Leggiamo il valore in ingresso $n$ .

scanf("%d",&n);

Inizializziamo $r es [1] = 1$ res[1] = 1.

res[1] = 1;

Di seguito calcoliamo in sequenza i valori $r es [2], r es [3], ..., r es [n]$ res[2], res[3], ..., res[n] secondo la formula sopra riportata.

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++

Stampiamo la risposta.

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