原始计算器的动态规划
Dynamic programming for primitive calculator
我正在处理这个问题,这与零钱问题非常相似。
我需要实现一个简单的计算器,它可以对当前数字 x 执行以下三种运算:x 乘以 2、x 乘以 3 或 x 加 1。
目标是给定一个正整数n,从数字1开始求得到数字n所需的最少运算次数。
我对此采取了贪婪的方法,但它显示的结果不正确
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个步骤:
Output:
3
1 3 9 10
我看了动态规划,希望能在这里实现。但是,我不知道如何在特定情况下正确使用它,有人可以给我一个建议吗?
用一个简单的递归就可以解决Memoization:
代码:
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) returns一个元组(a,b),其中a
表示从1得到x的最少步数,b
表示前面的数以获得最优解。 b
仅用于打印解决方案。
输出:
4 # solution for 10
1 3 9 10
7 # solution for 111
1 2 4 12 36 37 111
您可以调试我的代码并了解它是如何工作的。如果你是 DP 的初学者,你可以阅读我的另一篇关于 DP 的文章 以快速入门。
由于Python不能递归很多(10000左右),我写一个迭代版本:
# 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
我正在处理这个问题,这与零钱问题非常相似。
我需要实现一个简单的计算器,它可以对当前数字 x 执行以下三种运算:x 乘以 2、x 乘以 3 或 x 加 1。
目标是给定一个正整数n,从数字1开始求得到数字n所需的最少运算次数。
我对此采取了贪婪的方法,但它显示的结果不正确
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个步骤:
Output:
3
1 3 9 10
我看了动态规划,希望能在这里实现。但是,我不知道如何在特定情况下正确使用它,有人可以给我一个建议吗?
用一个简单的递归就可以解决Memoization:
代码:
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) returns一个元组(a,b),其中a
表示从1得到x的最少步数,b
表示前面的数以获得最优解。 b
仅用于打印解决方案。
输出:
4 # solution for 10
1 3 9 10
7 # solution for 111
1 2 4 12 36 37 111
您可以调试我的代码并了解它是如何工作的。如果你是 DP 的初学者,你可以阅读我的另一篇关于 DP 的文章
由于Python不能递归很多(10000左右),我写一个迭代版本:
# 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