我在获得以下问题的正确解决方案时遇到一些困难:
你的目标是一个正整数n,找到最少的数量
从数字 1 开始获取数字 n 所需的操作。
更具体地说,我在下面的评论中有测试用例。
# Failed case #3/16: (Wrong answer)
# got: 15 expected: 14
# Input:
# 96234
#
# Your output:
# 15
# 1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
# Correct output:
# 14
# 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
# (Time used: 0.10/5.50, memory used: 8601600/134217728.)
def optimal_sequence(n):
sequence = []
while n >= 1:
sequence.append(n)
if n % 3 == 0:
n = n // 3
optimal_sequence(n)
elif n % 2 == 0:
n = n // 2
optimal_sequence(n)
else:
n = n - 1
optimal_sequence(n)
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, end=' ')
看起来我应该在输出 4 和 5 的地方输出 9,但我不确定为什么情况并非如此。解决此问题的最佳方法是什么?
你正在做一种贪婪的方法。
当 n == 10 时,您会检查它是否能被 2 整除,假设这是最佳步骤,但在本例中这是错误的。
您需要做的是适当的动态规划。v[x]
将保留获得结果的最少步骤数x
.
def solve(n):
v = [0]*(n+1) # so that v[n] is there
v[1] = 1 # length of the sequence to 1 is 1
for i in range(1,n):
if not v[i]: continue
if v[i+1] == 0 or v[i+1] > v[i] + 1: v[i+1] = v[i] + 1
# Similar for i*2 and i*3
solution = []
while n > 1:
solution.append(n)
if v[n-1] == v[n] - 1: n = n-1
if n%2 == 0 and v[n//2] == v[n] -1: n = n//2
# Likewise for n//3
solution.append(1)
return reverse(solution)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)