今天，在某Python群里宅倒，看到有一個問題，看似簡單屯耸，其實挺難的拐迁。題目如下：
小易總是感覺饑餓，所以作為章魚的小易經(jīng)常出去尋找貝殼吃疗绣。
最開始线召，小易在一個初始位置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)
兩個步長函數(shù)
首先對這兩個步長函數(shù)作一下變形：
由此可得
在看下面的分析之前，需要理解一個知識躏吊，這里簡單舉例說明
第一種走法：
4x+3氛改，8x+7，4x+3
第二種走法：
4x+3比伏，4x+3胜卤，8x+7
是完全一樣的，
這里我想說明的是赁项，從初始位置開始葛躏，小易到達的最終位置只跟4x+3的次數(shù)和8x+7的次數(shù)有關系，與先走哪個沒有關系
假設小易到達目標位置
所需的4x+3的次數(shù)為m次肤舞，此時到達的位置為x_m
所需的8x+7的次數(shù)為n次紫新，此時的位置為目標位置x_(m+n)
將上述兩個式子寫成一個
由此可知，4x+3所需次數(shù)m李剖，8x+7所需次數(shù)n芒率，初始位置x_0，最終位置x_(m+n)滿足如下關系
m 為4x+3的次數(shù)篙顺， n 為8x+7的次數(shù)偶芍， x_0 為初始位置，x_(m+n)為最終的目標位置
而且由題目中的條件德玫，小易應該用最少的次數(shù)匪蟀，因此綜合上述分析，本題實際為如下的最優(yōu)化問題
由上述的分析宰僧，可知
只有當該值為一個 整數(shù)材彪，即
(x_(m + n) + 1) / (x_0 + 1) = 2的某個指數(shù)冪
的時候，小易才可以從初始位置琴儿，到達目標位置段化，否則永遠不可能到達。因此這也是題目中設置一個給定次數(shù)100000造成，判定程序結束的條件显熏。
至此，從數(shù)學的角度本題已經(jīng)分析完了晒屎，剩下的就是 擼代碼喘蟆。
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'最少次數(shù)為：{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
