找到最小操作，使得N在3次操作后变为1

Question

给定N为自然数，我们可以用它做这3个运算。

1) N

减12)如果是偶数，除以2

3)如果它能除3，则除以3

在N等于1时停止。我们需要找到最小运算使N变成1

#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'count' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER num as parameter.
#
def count(num):

count = 0 
while num != 1:

if (num % 3 ==0 ):
count += 1
num = num / 3
elif((num -1) % 3 == 0):
count += 2
num = (num - 1) / 3
elif (num % 2 ==0):
count += 1
num = num / 2
else:
num = num - 1
count += 1 

return count

这是我的代码。在11个测试用例中，它通过了9个，给出了2个错误的答案。我不知道对于哪些测试用例，我的代码给出了错误的答案。你能帮我了解问题在哪里吗?

Answer 1

你假设如果可以，最好先减1再除以3，但这并不总是正确的。

考虑16

你的解决方案是16-15-5-4-3-1 = 5步

更好的解决方案:2016-8-4 -2-1 = 4步

Answer 2

可能不是最有效的解决方案，但是:

def count(num):
count1, count2 = float('inf'), float('inf')
if num == 1:
return 0
if num % 3 == 0:
count1 = 1 + count(num // 3)
if num % 2 == 0:
count2 = 1 + count(num // 2)
count3 = 1 + count(num - 1)
return min(count1, count2, count3)

Answer 3

这些类型的问题通常有一组产生最佳答案的规则。

然而，你的根本问题是，你假设你的规则集是最优的，没有任何证据。你真的没有理由相信它会产生正确的计数。

不幸的是，这些问题的答案有时会提供正确的规则集，但似乎总是忽略任何证明规则集是最优的。

你必须做一些保证有效的事情，所以除非你有这样的证据，你应该回到A*搜索或类似的。

Answer 4

您可以使用非递归的宽度优先策略。

假设有一个队列保存数字列表。最初，在队列中输入一个仅包含N的列表。然后重复以下操作，直到队列为空:

1. 选择队列中的第一个列表
2. 三种操作重复3。
3. 选择一项操作。如果可能，将其应用于最后一个列表号，并将结果添加到列表末尾。如果列表是一个解决方案，将它存储在某个地方。如果没有，则将其添加到队列末尾。

这个策略是详尽的，可以找到所有的解。因为我们只关心最小值，所以我们引入一个极限界。一旦有了可用的解决方案列表，我们就不会将超过这个长度的列表输入到队列中，如果它们已经在队列中，我们也不会考虑它们。