今天，在某Python群里，看到有一个问题，看似简单，其实挺难的。题目如下：

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。
最开始，小易在一个初始位置x_0。
对于小易所处的当前位置x，它只能通过神秘的力量移动到4x+3或者8x+7。
因为使用神秘力量要耗费太多的体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置（比如：位置0，位置1,000,000,007，位置2,000,000,014等）。
小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

分析

设小易当前位置为x_n，使用神秘力量移动以后的位置为x_(n+1)

两个步长函数

首先对这两个步长函数作一下变形：

1.jpg

由此可得

2.jpg

在看下面的分析之前，需要理解一个知识，这里简单举例说明

第一种走法：
4x+3，8x+7，4x+3
第二种走法：
4x+3，4x+3，8x+7
是完全一样的，

这里我想说明的是，从初始位置开始，小易到达的最终位置只跟4x+3的次数和8x+7的次数有关系，与先走哪个没有关系

假设小易到达目标位置

所需的4x+3的次数为m次，此时到达的位置为x_m

3.jpg

所需的8x+7的次数为n次，此时的位置为目标位置x_(m+n)

4.jpg

将上述两个式子写成一个

5.jpg

由此可知，4x+3所需次数m，8x+7所需次数n，初始位置x_0，最终位置x_(m+n)满足如下关系

6.jpg

m 为4x+3的次数， n 为8x+7的次数， x_0 为初始位置，x_(m+n)为最终的目标位置

而且由题目中的条件，小易应该用最少的次数，因此综合上述分析，本题实际为如下的最优化问题

7.jpg

由上述的分析，可知

8.jpg

(x_(m + n) + 1) / (x_0 + 1) = 2的某个指数幂

的时候，小易才可以从初始位置，到达目标位置，否则永远不可能到达。因此这也是题目中设置一个给定次数100000，判定程序结束的条件。

至此，从数学的角度本题已经分析完了，剩下的就是 撸代码。

import random
from math import log
import re
x0 = random.randint(1, 1000000006)
x0 = 125000000
k = 1
target = 1000000007

def get_m_n(sum, k):
    m_n = []
    m_max = sum // 2
    n_max = sum // 3
    min_c = m_max + n_max
    for n in range(n_max + 1):
        m = (sum - 3 * n) // 2
        if 2 * m + 3 * n == sum:
            if m + n <= min_c:
                m_n.append((m, n))
                min_c = m + n
    # print(m_n)
    print(f'初始位置为：{x0}，目标位置为：{k}倍距离，{k * target}')
    print(f'最少次数为：{min_c}')
    for i, j in m_n:
        print(f'4x+3走{i}次，8x+7走{j}次')
        
while 1:
    t = k * target
    sum = log((t + 1) / (x0 + 1), 2)
    # print(sum)
    if sum >= 2.0 and re.findall('\d+\.0$', str(sum)):
        get_m_n(int(sum), k)
        break
    elif k == 100000:
        print('没有找到')
        break
    k += 1