8.3. Задача «Простой калькулятор»

У вас есть калькулятор, который выполняет с целым числом только следующие операции: сложить и , умножить на или умножить на . Имея положительное целое число , вы должны найти минимальное количество операций, необходимых для получения числа из числа .

Попробуем решить эту задачу с помощью «жадной» стратегии: если текущее число не превышает , то умножим его на 3; если оно больше , но не больше , то умножим его на 2; в остальных случаях добавим к нему 1. Это приводит к следующему псевдокоду.

GreedyCalculator(n):
    numOperations = 0
    currentNumber = 1
    while currentNumber<n:
        if currentNumber <= n/3:
            currentNumber = 3*currentNumber
        else if currentNumber <= n/2:
            currentNumber = 2*currentNumber
        else: 
            currentNumber = 1+currentNumber
        numOperations = numOperations+1
    return numOperations

💡 Остановитесь и подумайте:
Сможете ли вы найти такое число , при котором GreedyCalculator(n) приводит к неправильному ответу?

• Входные данные: Целое число .

• Выходные данные: В первой строке: — минимальное число необходимых операций для получения из . Во второй строке: последовательность промежуточных чисел. Так, вторая строка должна содержать положительные целые числа , при которых , , и для всех равно , или . Если таких последовательностей много, то можно вывести любую из них.

• Ограничения: .

Пример 1

Ввод	Вывод
1	0 1

Пример 2

Ввод	Вывод
96234	14 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

• Ещё один корректный вывод в этом случае — это «1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234».

Рассмотрим решение задачи. Пусть — минимальное количество операций, необходимых для получения числа из числа . Так как последняя операция в оптимальной последовательности — это «», «» или «», мы получаем следующее рекуррентное соотношение для :

Данное рекуррентное соотношение, вместе с базовым случаем , можно трансформировать в рекурсивный, а затем в итерационный алгоритм.

Calculator(n):
    table[1..n]←[+infinity,…,+infinity]
    table[1] = 0
    
    for k from 2 to n:
        table[k]=1+table[k−1]
        if k is divisible by 2:
            table[k]=min(table[k],1+table[k/2])
        if k is divisible by 3:
            table[k]=min(table[k],1+table[k/3])
    return table[n]

Помните, что помимо оптимального значения необходимо вывести оптимальную последовательность операций. Для этого обратим внимание на то, что мы можем найти последнюю операцию следующим образом:

• это «», если ;
• это «», если можно разделить на и ;
• это «», если можно разделить на и .

Эти действия позволяют нам выявить оптимальную последовательность:

• найти последнюю операцию;
• заменить на , или (в зависимости от того, какой это из трёх случаев выше);
• повторить (пока ).

Calculator(n):
    table[1..n]←[+infinity,…,+infinity]
    table[1] = 0
    
    for k from 2 to n:
        table[k]=1+table[k−1]
        if k is divisible by 2:
            table[k]=min(table[k],1+table[k/2])
        if k is divisible by 3:
            table[k]=min(table[k],1+table[k/3])
    
    operations = empty list
    while n > 1:
        append n to operations
        if table[n]=1+table[n−1]:
            n = n - 1
        else if n is divisible by 2 and table[n]=1+table[n/2]:
            n = n/2
        else if n is divisible by 3 and table[n]=1+table[n/3]:
            n = n/3
    return operations

Время выполнения алгоритма составляет .