一個數最後一位是6，移動到首位是原來數的三倍，求這個數.md

一個數最後一位是6，移動到首位是原來數的三倍，求這個數

問題

題目：一個數最後一位是6，移動到首位是原來數的三倍，求這個數 要求：速度最優

大神們快來踴躍探討~~~

問題出自 segmentfault, by prolifes

回答

各路大神的回答

citaret 的回答

先贴上一版：

x = 6
xs = []
while True:
    xs.append(x // 3)
    x = x % 3 * 10 + x // 3
    if x == 6:
        print ''.join(str(x) for x in xs)
        break

输出：

2068965517241379310344827586

原理是手算，把每次得到的商的末位补到被除数的最后，然后继续除法，直到末位为6，且余数为0停止。

hsfzxjy 的回答

由於數學公式的使用請大家前往問題原出處查看 回答

我的回答

下午看到這題的時候就有了個想法, 手邊沒電腦只好等到現在...

後來看到 @citaret 的答案就發現剛好是反向的想法, 下面是我的作法:

x = 6
last_carry = 0
result = 6
radix = 10

while True:
    c1, x = divmod(x * 3, 10)
    c2, x = divmod(x + last_carry, 10)
    last_carry = c1 + c2
    
    if x==6 and last_carry==0:
        return result

    result += (x * radix)
    radix *= 10

想法就剛好是反過來, 我一步一步地乘上去

• 每次把 x 乘 3
• 把個位數加上 last_carry 就是下次的 x
• 把十位數的進位留下來當作下次的 last_carry
• 做到 x==6 且無進位的時候

用圖來思考長這樣:

0 <-- last carry
 \
1 8 = 6 X 3
 \  (0 + 8 = 8)
2 4 = 8 X 3
 \  (1 + 4 = 5) 
1 5 = 5 X 3
...

用 timeit 稍微測了一下時間(各運行 1000000 次), 共測三次:

# first
dokelung: 17.301649590954185
citaret:  18.24915363173932

# second
dokelung: 19.257807812653482
citaret:  17.994877750985324

# third
dokelung: 17.0617663115263
citaret:  18.355605391785502

時間看起來差不多, 不過我自認為代碼沒有很漂亮...