從數字的加法預測數字

Question

有人問我這個算法問題，和往常一樣，我沒有回答這個問題。 :)讓我們說，你有一個號碼（稱之爲）

504 

下一次，你看到它，你刪除號碼的最後一位數字。它變成（稱之爲b）

50 

下一次，你會看到它，你刪除了最後一位數字。它變成（稱之爲c）

5 

現在，添加所有三個數字（a + b + c）。它變成：

504 + 50 + 5 = 559 

好了，現在你可能已經很好地理解了問題陳述。

問題是：鑑於給您添加了三個數字a + b + c（本例中爲559），您如何返回到原始數字（本例中爲504）？所有解決方案將不勝感激。

Answer 1

假設您開始使用的數字看起來像xyz。即其最後（十進制）數字是z，其倒數第二位數字是和，其餘是x。在你的例子中，如果你從504開始，那麼x = 5，y = 0，z = 4。原始數字的值是100x + 10y + z。

最終的數字是（100x + 10y + z），（10x + y）和x的總和。這是111x + 11y + z。

請注意，我們的約束條件是0≤y≤9且0≤z≤9。即使是最大的值，我們也有11y +z≤11（9）+ 9 <111。所以我們可以反轉變換：拉出111的最大倍數，然後從剩餘的中拉出11的最大倍數，然後還剩下什麼。

def transform(n): 
    return n + (n/10) + (n/100) 

def invert(m): 
    [x, y, z] = [m/111, (m%111)/11, (m%111)%11] 
    return 100*x + 10*y + z 

assert transform(504) == 559 
assert invert(559) == 504 

（試試上面在Python外殼需要注意的是這個工程即使x是不是一個單一位數：。transform(12345)給出了13702，並且invert(13702)給12345，如預期）

---

編輯：以m*100/111爲出發點，基於Paul Hankin's answer（請注意它）的想法的另一種解決方案。您當然可以使用該值的（上限）作爲粗略的答案，並嘗試添加1和2以得到確切的答案，但您也可以預先計算粗略答案中所需的「偏移量」。

# Precomputation, to populate the "offset" dictionary 
def sane_mod(a, m): return ((a % m) + m) % m 
offset = {} 
for y in range(10): 
    for z in range(10): 
     add = 10*y + 11*z 
     offset[sane_mod(-add, 111)] = add 

# Actual function 
def invert2(m): 
    rough = m * 100 
    return (rough + offset[rough % 111])/111 
assert invert2(559) == 504 

Answer 2

a + b + c是a + a // 10 + a // 100（其中//表示舍入除法）。這介於* 111/100 - 1.89和* 111/100之間。 （1.89是因爲從// 10丟棄的最大分數是0.9，而從// 100丟棄的最大分數是0.99，並且1.89 = 0.9 + 0.99）。

所以，對於一個+ B + C，我們正在尋找一個整數，使得：

a * 111/100 - 1.89 <= a + b + c <= a * 111/100 
a - 2.0979 <= (a + b + c) * 100/111 <= a 

因此，令x =小區（（A + B + C）* 100/111），並且x，x + 1或x + 2中的一個必須是解決方案。