今天去参加数学竞赛，题目是这样的:

You have a given number n, now you have to like calculate what's the shortest route to that number, but there are rules.

1. You start with number 1
2. You end when you reach n
3. You can get to n either by doubling your previous number, or by adding two previous numbers.

Example: n = 25

Slowest route : 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 (You just keep adding 1)

Fastest route : 1,2,4,8,16,24,25, complexity = 6

Example: n = 8 Fastest route : 1,2,4,8, complexity = 3

Example : n = 15 Fastest route : 1,2,3,6,9,15, complexity = 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

最佳答案

我接受挑战:)

算法比较快。它在我的计算机上以 50ms 计算前 32 个数字的复杂度，而且我没有使用多线程。 (或前 100 个数字 370 毫秒。)

这是一个递归的分支和切割算法。 _shortest 函数有 3 个参数:优化在于 max_len 参数。例如。如果函数找到长度为 9 的解决方案，它将停止考虑长度 > 9 的任何路径。找到的第一条路径总是非常好的，它直接来自数字的二进制表示形式。例如。二进制:111001 => [1,10,100,1000,10000,100000,110000,111000,111001]。这并不总是最快的路径，但如果您只搜索速度最低的路径，则可以削减大部分搜索树。

#!/usr/bin/env python

# Find the shortest addition chain...
# @param acc List of integers, the "accumulator". A strictly monotonous
#        addition chain with at least two elements.
# @param target An integer > 2. The number that should be reached.
# @param max_len An integer > 2. The maximum length of the addition chain
# @return A addition chain starting with acc and ending with target, with
#         at most max_len elements. Or None if such an addition chain
#         does not exist. The solution is optimal! There is no addition
#         chain with these properties which can be shorter.
def _shortest(acc, target, max_len):
    length = len(acc)
    if length > max_len:
        return None
    last = acc[-1]
    if last == target:
        return acc;
    if last > target:
        return None
    if length == max_len:
        return None
    last_half = (last / 2)
    solution = None
    potential_solution = None
    good_len = max_len

    # Quick check: can we make this work?
    # (this improves the performance considerably for target > 70)
    max_value = last
    for _ in xrange(length, max_len):
        max_value *= 2
        if max_value >= target:
            break
    if max_value < target:
        return None

    for i in xrange(length-1, -1, -1):
        a = acc[i]
        if a < last_half:
            break

        for j in xrange(i, -1, -1):
            b = acc[j]
            s = a+b
            if s <= last:
                break

            # modifying acc in-place has much better performance than copying
            # the list and doing
            #   new_acc = list(acc)
            #   potential_solution = _shortest(new_acc, target, good_len)

            acc.append(s)
            potential_solution = _shortest(acc, target, good_len)
            if potential_solution is not None:
                new_len = len(potential_solution)
                solution = list(potential_solution)
                good_len = new_len-1

            # since we didn't copy the list, we have to truncate it to its
            # original length now.
            del acc[length:]

    return solution

# Finds the shortest addition chain reaching to n.
# E.g. 9 => [1,2,3,6,9]
def shortest(n):
    if n > 3:
        # common case first
        return _shortest([1,2], n, n)
    if n < 1:
        raise ValueError("n must be >= 1")
    return list(xrange(1,n+1))

for i in xrange(1,33):
    s = shortest(i)
    c = len(s) - 1
    print ("complexity of %2d is %d: e.g. %s" % (i,c,s))

输出:

complexity of  1 is 0: e.g. [1]
complexity of  2 is 1: e.g. [1, 2]
complexity of  3 is 2: e.g. [1, 2, 3]
complexity of  4 is 2: e.g. [1, 2, 4]
complexity of  5 is 3: e.g. [1, 2, 4, 5]
complexity of  6 is 3: e.g. [1, 2, 4, 6]
complexity of  7 is 4: e.g. [1, 2, 4, 6, 7]
complexity of  8 is 3: e.g. [1, 2, 4, 8]
complexity of  9 is 4: e.g. [1, 2, 4, 8, 9]
complexity of 10 is 4: e.g. [1, 2, 4, 8, 10]
complexity of 11 is 5: e.g. [1, 2, 4, 8, 10, 11]
complexity of 12 is 4: e.g. [1, 2, 4, 8, 12]
complexity of 13 is 5: e.g. [1, 2, 4, 8, 12, 13]
complexity of 14 is 5: e.g. [1, 2, 4, 8, 12, 14]
complexity of 15 is 5: e.g. [1, 2, 4, 5, 10, 15]
complexity of 16 is 4: e.g. [1, 2, 4, 8, 16]
complexity of 17 is 5: e.g. [1, 2, 4, 8, 16, 17]
complexity of 18 is 5: e.g. [1, 2, 4, 8, 16, 18]
complexity of 19 is 6: e.g. [1, 2, 4, 8, 16, 18, 19]
complexity of 20 is 5: e.g. [1, 2, 4, 8, 16, 20]
complexity of 21 is 6: e.g. [1, 2, 4, 8, 16, 20, 21]
complexity of 22 is 6: e.g. [1, 2, 4, 8, 16, 20, 22]
complexity of 23 is 6: e.g. [1, 2, 4, 5, 9, 18, 23]
complexity of 24 is 5: e.g. [1, 2, 4, 8, 16, 24]
complexity of 25 is 6: e.g. [1, 2, 4, 8, 16, 24, 25]
complexity of 26 is 6: e.g. [1, 2, 4, 8, 16, 24, 26]
complexity of 27 is 6: e.g. [1, 2, 4, 8, 9, 18, 27]
complexity of 28 is 6: e.g. [1, 2, 4, 8, 16, 24, 28]
complexity of 29 is 7: e.g. [1, 2, 4, 8, 16, 24, 28, 29]
complexity of 30 is 6: e.g. [1, 2, 4, 8, 10, 20, 30]
complexity of 31 is 7: e.g. [1, 2, 4, 8, 10, 20, 30, 31]
complexity of 32 is 5: e.g. [1, 2, 4, 8, 16, 32]

关于python - python中任何给定数字的路径复杂度(最快路径)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34617451/