f（ "123"）= 123 + 12 + 23 + 1 + 2 + 3を反復関係として書くには

Question

誰かが私にこれを理解させてもらえるかどうかは疑問だ。

私はf(str)は数字の文字列strを取り、数値として、すべてのサブストリングの合計を返すようにしたい、と私は私がメモ化でこれを解決しようとすることができるように、自身の機能としてf書きたいです。

私はあなたがダウンして二つの機能にfを破る必要があり

 Solve("1") = 1 
     Solve("2") = 2 
     Solve("12") = 12 + 1 + 2 
     Solve("29") = 29 + 2 + 9 
     Solve("129") = 129 + 12 + 29 + 1 + 2 + 9 
     Solve("293") = 293 + 29 + 93 + 2 + 9 + 3 
     Solve("1293") = 1293 + 129 + 293 + 12 + 29 + 93 + 1 + 2 + 9 + 3 
     Solve("2395") = 2395 + 239 + 395 + 23 + 39 + 95 + 2 + 3 + 9 + 5 
     Solve("12395") = 12395 + 1239 + 2395 + 123 + 239 + 395 + 12 + 23 + 39 + 95 + 1 + 2 + 3 + 9 + 5 

Answer 1

を見詰めるように、それは私に飛び出していません。

N[i]を入力のiとします。 T[i]を、入力の最初のi-1文字の部分文字列の合計とします。 B[i]を入力の最初のi文字の接尾辞の合計とします。

入力が「12395」の場合、B[3] = 9+39+239+1239およびT[3] = 123+12+23+1+2+3です。

再発の関係は以下のとおりです。

T[0] = B[0] = 0 
T[i+1] = T[i] + B[i] 
B[i+1] = B[i]*10 + (i+1)*N[i] 

最後の行には、いくつかの説明が必要：最初i+2文字の接尾辞としてだけでなく、最後に追加さN[i]との最初のi+1文字の接尾辞です1文字の文字列N[i]。これらの合計は(B[i]*10+N[i]*i) + N[i]で、これはB[i]*10+N[i]*(i+1)と同じです。

f(N) = T[len(N)] + B[len(N)]。

これは、あなたが動的プログラムであると考えることができ、短い、線形時間、反復解法を与える：

このパターンを見てみると

def solve(n): 
    rt, rb = 0, 0 
    for i in xrange(len(n)): 
     rt, rb = rt+rb, rb*10+(i+1)*int(n[i]) 
    return rt+rb 

print solve("12395") 

Answer 2

：新しい用語を取得するには

Solve("1") = f("1") = 1 
Solve("12") = f("12") = 1 + 2 + 12 = f("1") + 2 + 12 
Solve("123") = f("123") = 1 + 2 + 12 + 3 + 23 + 123 = f("12") + 3 + 23 + 123 
Solve("1239") = f("1239") = 1 + 2 + 12 + 3 + 23 + 123 + 9 + 39 + 239 + 1239 = f("123") + 9 + 39 + 239 + 1239 
Solve("12395") = f("12395") = 1 + 2 + 12 + 3 + 23 + 123 + 9 + 39 + 239 + 1239 + 5 + 95 + 395 + 2395 + 12395 = f("1239") + 5 + 95 + 395 + 2395 + 12395 

nの長さがstrの場合は、0から始まるインデックス範囲の文字からなる部分文字列をstr：(n-1,n-1), (n-2,n-1), (n-3,n-1), ... (n-n, n-1)に含めます。

サブ文字列のインデックス範囲から形成された整数の合計を取得する関数を記述できます。その関数をg(str)と呼び出すと、str.length > 1の場合はf(str) = f(str.substring(0, str.length - 1)) + g(str)と、再帰的に書くことができます。str.length == 1の場合は、strの整数値が返されます。 （substringのパラメータはstrの文字の開始インデックスと、得られたサブストリングの長さである。）（「12395」）を解決例えば

、再帰方程式f(str) = f(str.substring(0, str.length - 1)) + g(str)収率：

f("12395") = 
f("1239") + g("12395") = 
(f("123") + g("1239")) + g("12395") = 
((f("12") + g("123")) + g("1239")) + g("12395") = 
(((f("1") + g("12")) + g("123")) + g("1239")) + g("12395") = 
1 + (2 + 12) + (3 + 23 + 123) + (9 + 39 + 239 + 1239) + (5 + 95 + 395 + 2395 + 12395) 

Answer 3

この問題を見る1つの方法は、各桁の最終的な合計への寄与を考慮することです。

たとえば、数字xn-1…xi+1Diyi-1…y0の末尾にあるiの数字Diを考えてみましょう。 （xとDとyを使用して数字の位置について話すことができました）Dを含むすべての部分文字列を見て数字の末尾からDの位置で並べ替えると、次のとおりです。

 D 
     xD 
    xxD 
     … 
    xx…xD 
     Dy 
    xDy 
    xxDy 
     … 
    xx…xDy 
    Dyy 
    xDyy 
    xxDyy 
    … 
xx…xDyy 

などです。すなわち

、Dは（含む）0からn-i-1各プレフィックス長のために一度0からiに全ての位置に表示され、各桁位置でn-i時間の合計。これは合計に対するその総寄与が100から10iの10の累乗の合計であるD*(n-i)であることを意味します。 （偶然にも、その合計が正確に(10i+1−1)⁄9です。）ポール・ハンキンによって提案された反復の少し簡単なバージョンにつながる

：別の方法で合計を再配置することにより

def solve(n): 
    ones = 0 
    accum = 0 
    for m in range(len(n),0,-1): 
     ones = 10 * ones + 1 
     accum += m * ones * int(n[m-1]) 
    return accum 

、あなたが来ることができます

：この単純な再帰を持つまで、あなたが本当に再帰的なソリューションたい場合は、以下の理由

# Find the sum of the digits in a number represented as a string 
digitSum = lambda n: sum(map(int, n)) 

# Recursive solution by summing suffixes: 
solve2 = lambda n: solve2(n[1:]) + (10 * int(n) - digitSum(n))/9 if n else 0 

それは、10*n-digitSum(n)は9で割り切れる常に、明白ではない場合

digitSum(n) mod 9 == n mod 9

1. 10*n == n + 9*n == (mod 9) n mod 9 + 0。 （kの場合は10k == 1 mod nなので）

2. したがって(10*n - digitSum(n)) mod 9 == (n - n) mod 9 == 0です。