Task 102. Минимальное кол-во операций

Задача: дано натуральное число N. Вы можете выполнять след.операции над числом: вычитать 1, делить на 2 (если делится), делить на 3 (если делится).

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

Входные данные: N - натуральное число от 1 до 10^6

Вывод: число X - наименьшее кол-во операций, ктр приведут число N к 1.

Пример: N = 9

Answer = 2

Идея: воспользуемся методом динамического программирования. Заведем массив numOperations, ктр для каждого iго числа будет хранить наименьшее кол-во операций, после выполнения ктр оно преобразуется в 1. Исходя из условий получаем след.соотношения:

1. Если число i делится на 3, то numOperations[i] = numOperations[i / 3] + 1
2. Если число i делится на 2, то numOperations[i] = numOperations[i / 2] + 1
3. Если из числа i вычесть 1, то numOperations[i] = numOperations[i - 1] + 1

Видим, что от числа i мы можем перейти к одному из 3-х чисел: (i / 3), (i / 2), (i - 1), а кол-во операций для этих чисел будет равно соот-но numOperations[i / 3], numOperations[i / 2], numOperations[i - 1]. В нашем случае нам нужно взять наименьшее кол-во операций, поэтому получаем:

numOperations[i]=Min(numOperations[i/3],numOperations[i/2],numOperations[i-1])+1

Очевидно, что для 1 кол-во операций необходимых для приведения к 1 равно 0.

Рассмотрим пример для N = 10:

numOperations[10] =

Min (numOperations[10 / 3], numOperations[10 / 2], numOperations[10 - 1]) + 1 =

Min (numOperations[5], numOperations[9]) + 1 = Min(2, 3) + 1 = 3.

Реализация:

https://gist.github.com/unilecs/4de96c8ce2dd205d94c46374e0d5ec0a

Test:

https://dotnetfiddle.net/aQklKp