原始计算器的动态编程 [英] Dynamic programming for primitive calculator

问题描述

我正在处理该问题，这与找零硬币问题非常相似。

I'm dealing with the problem, that is pretty similar to change coins problem.

我需要实现一个简单的计算器，该计算器可以执行以下三个操作使用当前数字x：将x乘以2，将x乘以3，或将1加到x。

I need to implement a simple calculator, that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x.

目标给出一个正整数n，找到从数字1开始获得数字n所需的最小操作数。

Goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

我对此采取了一种贪婪的方法，但结果显示不正确

I made a greedy approach to that, bur it shows incorrect results

import sys

def optimal_sequence(n):
    sequence = []
    while n >= 1:
        sequence.append(n)
        if n % 3 == 0:
            n = n // 3
        elif n % 2 == 0:
            n = n // 2
        else:
            n = n - 1
    return reversed(sequence)

input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
    print(x)

例如：

Input: 10
Output: 
4
1 2 4 5 10

4个步骤。但是正确的步骤是3个步骤：

4 steps. But the correct one is 3 steps:

Output: 
3
1 3 9 10

我了解了动态编程，希望可以在这里实现。但是，在特定情况下我无法正确使用它，有人可以给我提建议吗？

I read about dynamic programming, and hope I could implement it here. But, I can't get how to use it properly in particular case, can someone give me an advice?

推荐答案

通过简单的递归和记忆力：

代码：

d = {}

def f(n):
    if n == 1:
        return 1, -1
    if d.get(n) is not None:
        return d[n]
    ans = (f(n - 1)[0] + 1, n - 1)

    if n % 2 == 0:
        ret = f(n // 2)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 2)

    if n % 3 == 0:
        ret = f(n // 3)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 3)

    d[n] = ans
    return ans

def print_solution(n):
    if f(n)[1] != -1:
        print_solution(f(n)[1])
    print n,

def solve(n):
    print f(n)[0]
    print_solution(n)
    print ''

solve(10)

提示：f（x）返回一个元组（a，b），其中 a 表示从1得到x的最小步骤，而 b 表示得到最佳解的前一个数字。 b 仅用于打印解决方案。

Hint: f(x) returns a tuple (a, b), which a denotes the minimum steps to get x from 1, and b denotes the previous number to get the optimum solution. b is only used for print the solution.

输出：

4 # solution for 10
1 3 9 10 

7 # solution for 111
1 2 4 12 36 37 111

您可以调试我的代码并了解其工作方式。如果您是DP的初学者，则可以阅读我的另一个关于DP的SO帖子，以快速入门。

You may debug my code and to learn how it works. If you are beginner at DP, you could read my another SO post about DP to get a quick start.

由于Python不能大量递归（大约10000个），所以我编写了一个迭代版本：

Since Python can't recurse a lot (about 10000), I write an iterative version:

# only modified function print_solution(n) and solve(n)

def print_solution(n):
    ans = []
    while f(n)[1] != -1:
        ans.append(n)
        n = f(n)[1]
    ans.append(1)
    ans.reverse()
    for x in ans:
        print x,

def solve(n):
    for i in range(1, n):
        f(i)[0]
    print_solution(n)
    print ''

solve(96234) # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 

这篇关于原始计算器的动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！