python中任何给定数字的路径复杂性(最快路径)

Question

今天我参加了数学竞赛,有一个问题是这样的:

你有一个给定的数字n,现在你必须要计算到这个数字的最短路径,但是有规则.

1. 你从数字开始 1
2. 当你到达时结束 n
3. 您可以n通过将之前的号码加倍,或者添加前两个号码来获得.

例: n = 25

最慢的路线 :( 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25 你只是继续添加1)

最快的路线:1,2,4,8,16,24,25,复杂度= 6

示例:n = 8 最快路线:1,2,4,8,复杂度= 3

示例:n = 15 最快路线:1,2,3,6,9,15,复杂度= 5

如何使一个程序,可以计算出给定数量的复杂性n(用n <= 32)？

我已经知道,对于任何给定数量n(n <= 32),复杂度低于1.45 x 2log(n).所以现在我只需要计算复杂度低于1.45 x 2log(n)的所有路径,然后比较它们,看看哪一条是最快的"路线".但我不知道如何将所有路由和所有这些路由放在python中,因为当给定的数字n发生变化时路由的数量会发生变化.

这就是我现在所拥有的:

number = raw_input('Enter your number here : ')
startnumber = 1
complexity = 0

while startnumber <= number

Answer 1

您的问题有一个动态规划解决方案，因为您可以将任意两个数字相加或将一个数字乘以 2，我们可以尝试所有这些情况，并选择最小的一个，如果 25 的复杂性为 5 并且路线包含 9 那么我们知道9 的解为 4，我们可以使用 9 的解来生成 25 的解。我们还需要跟踪 m 的每个可能的最小解，以便能够使用它来求解 n，其中 m < n

def solve(m):
    p = [set([frozenset([])]) for i in xrange(m+1)] #contains all paths to reach n
    a = [9999 for _ in xrange(m+1)]
    #contains all complexities initialized with a big number
    a[1] = 0
    p[1] = set([frozenset([1])])
    for i in xrange(1,m+1):
        for pos in p[i]:
            for j in pos: #try adding any two numbers and 2*any number
                for k in pos:
                    if (j+k <= m):
                        if a[j+k] > a[i]+1:
                            a[j+k] = a[i] + 1
                            p[j+k] = set([frozenset(list(pos) + [j+k])])
                        elif a[j+k] == a[i]+1:
                            p[j+k].add(frozenset(list(pos) + [j+k]))
    return a[m],sorted(list(p[m].pop()))

n = int(raw_input())
print solve(n)

这最多可以求解 n = 100

对于较大的数字，您可以通过添加几行从内部循环中删除一些冗余计算来获得 30% 或更多的加速。为此，pos2在每次迭代时创建并修剪变量：

def solve(m):
    p = [set([frozenset([])]) for i in xrange(m+1)] #contains all paths to reach n
    a = [9999 for _ in xrange(m+1)]
    #contains all complexities initialized with a big number
    a[1] = 0
    p[1] = set([frozenset([1])])
    for i in xrange(1,m+1):
        for pos in p[i]:
            pos2 = set(pos)
            for j in pos: #try adding any two numbers and 2*any number
                for k in pos2:
                    if (j+k <= m):
                        if a[j+k] > a[i]+1:
                            a[j+k] = a[i] + 1
                            p[j+k] = set([frozenset(list(pos) + [j+k])])
                        elif a[j+k] == a[i]+1:
                            p[j+k].add(frozenset(list(pos) + [j+k]))
                pos2.remove(j)
    return a[m],sorted(list(p[m].pop()))