Матч 45, Уменьшающееся число (DecreasingNumber)

Над целым числом можно производить следующие операции:

1. Если число делится на 3, то делить его на 3;

2. Если число делится на 2, то делить его на 2;

3. Вычитать 1.

По заданному натуральному числу n найти наименьшее количество операций, после выполнения которых получится 1.

Класс: DecreasingNumber

Метод: int numberOfOperations(int n)

Ограничения: 1 £ n £ 10⁶.

Вход. Целое число n.

Выход. Наименьшее количество операций, выполнение которых преобразует число n в 1.

Пример входа

n

1

5

10

Пример выхода

0

3

3

РЕШЕНИЕ

динамическое программирование

Пусть d[i] содержит наименьшее количество операций, выполнение которых преобразует число i в 1. Тогда имеем соотношение:

d[i] = min(d[i – 1], d[i / 2],d[i / 3]) + 1, d[1] = 0

При этом если i не делится на 2 (или на 3), то соответствующий элемент (d[i / 2] или d[i / 3]) отсутствует в функции min. Например, для i = 8 имеем:

d[8] = min(d[7], d[4]) + 1

Соответственно для i = 7 получим:

d[7] = min(d[6]) + 1 = d[6] + 1

Заполняем ячейки массива d от 1 до n согласно приведенному рекуррентному соотношению и возвращаем d[n]. Например, в следующей таблице приведены значения d[i] для 1 £ i £ 11:

i	1	2	3	4	5	6	7	8	9	10	11
d[i]	0	1	1	2	3	2	3	3	2	3	4

ПРОГРАММА

#include <stdio.h>

#define min(i,j) (i<j)?i:j

int i, d[1000001];

class DecreasingNumber

{

public:

int numberOfOperations(int n)

{

d[1] = 0;

for(i = 2; i <= n; i++)

{

d[i] = d[i-1] + 1;

if (i % 2 == 0) d[i] = min(d[i], d[i/2] + 1);

if (i % 3 == 0) d[i] = min(d[i], d[i/3] + 1);

}

return d[n];

}

};