python 最小步长为1

abithluo 于 2023-05-16 发布在 Python

关注(0)|答案(1)|浏览(152)

给定一个正整数'n'，找到并返回'n'要减少到1所需的最小步骤数。您可以执行以下3个步骤中的任何一个：
1.减去1。（n = n -1）
1.如果n可被2整除，则除以2。（如果n % 2 == 0，则n = n / 2）
1.如果n能被3整除，就除以3。（如果n % 3 == 0，则n = n / 3）
输入格式：
输入的第一行也是唯一的一行包含一个整数值“n”。
输出格式：
打印最小步数。
制约因素：
1 <= n <= 10 ^ 6
时间限制：1秒

以下为代码

from sys import maxsize as MAX_VALUE 

dic = {}
def countMinStepsToOne(n) :
    if n == 1:
        return 0
    if n % 3 == 0:
        if n/3 not in dic:
            dic[n/3] = countMinStepsToOne(n/3)
    if n % 2 == 0:
        if n/2 not in dic:
            dic[n/2] = countMinStepsToOne(n/2)
    if n-1 not in dic:    
        dic[n-1] = countMinStepsToOne(n-1)
    return 1 + min(dic.get(n/3,MAX_VALUE),dic.get(n/2,MAX_VALUE),dic.get(n-1,MAX_VALUE))


#main
n = int(input())
print(countMinStepsToOne(n))

**对于n的小值，它给出了正确的输出，但当我尝试更大的值时，让我们取5685，powershell杀死没有输出的进程，在jupyter notebook内核中死亡。

据我所知，我认为字典是造成问题的原因，因为当我试图打印dic它是空的，但仍然没有得到它是如何工作的较小的值，而不是较大的。

python

来源：https://stackoverflow.com/questions/76249424/minimum-steps-to-1

1条答案

按热度按时间

7eumitmz1#

递归地做这件事意味着你本质上是在做一个可能性空间的DFS，这将创建一个非常深的堆栈（当在一个大输入上运行你的代码时，我得到了一个RecursionError），并且可能会浪费大量时间计算非常长的路径，你最终会重新计算以找到一个更短的路径到相同的值。输入越大，这种效果越差。
我建议将此作为BFS来执行，例如：

def steps_to_one(n):
    visited = set()
    depth = 0
    level = {n}
    while 1 not in level:
        depth += 1
        next_level = set()
        for n in level:
            if n in visited:
                continue
            visited.add(n)
            if n % 3 == 0:
                next_level.add(n // 3)
            if n % 2 == 0:
                next_level.add(n // 2)
            next_level.add(n - 1)
        level = next_level
    return depth

这非常快速地返回输入5685的结果15。
在每次迭代中，level是搜索空间的当前级别，depth是我们到目前为止遍历的级别数。
我们跟踪visited，以便如果我们在上一个搜索路径中已经访问过的值处结束，我们可以快速忽略它（例如如果我们沿着n - 1路径前进，发现了一个我们已经能够以更快的方式获得的值，那么从该点重新计算路径就没有意义了）。我们不需要一个dict来跟踪我们找到这个值时的深度，我们只需要知道它是一个已经在探索过程中的可能性。
如果我们在while循环的底部添加一个print：

print(depth, sorted(level - visited))

我们可以看到在BFS的每个级别上正在探索的内容：

1000
1 [500, 999]
2 [250, 333, 499, 998]
3 [111, 125, 249, 332, 498, 997]
4 [37, 83, 110, 124, 166, 248, 331, 497, 996]
5 [36, 55, 62, 82, 109, 123, 165, 247, 330, 496, 995]
6 [12, 18, 31, 35, 41, 54, 61, 81, 108, 122, 164, 246, 329, 495, 994]
7 [4, 6, 9, 11, 17, 27, 30, 34, 40, 53, 60, 80, 107, 121, 163, 245, 328, 494, 993]
8 [2, 3, 5, 8, 10, 15, 16, 20, 26, 29, 33, 39, 52, 59, 79, 106, 120, 162, 244, 327, 493, 992]
9 [1, 7, 13, 14, 19, 25, 28, 32, 38, 51, 58, 78, 105, 119, 161, 243, 326, 492, 991]
9

赞(0）回复(0）举报 2023-05-16

我来回答

python 最小步长为1

1条答案

相关问题

热门标签

最新问答