函数f("123")=123+12+23+1+2+3如何写成递推关系

Question

我想知道是否有人可以帮我解决这个问题。

我想f(str)取一个字符串str的数字和return所有子串的和作为数字，我想把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

您必须将 f 分解为两个函数。

设 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个字符的后缀是前i+1个字符的后缀加上N[i]，以及单字符串 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 的长度，您要包括由 str 中基于 0 的字符索引范围组成的子字符串： (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 的基本情况将只是 return [ 的整数值=13=]。（substring的参数是str中字符的起始索引和结果子串的长度。）

对于示例 Solve("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

看待这个问题的一种方法是考虑每个数字对最终总和的贡献。

例如，考虑数字 Di 位置 i（从末尾开始）的数字 xn-1…xi+1Diy i-1…y0。（我使用 x、D 和 y 只是为了能够讨论数字位置。）如果我们查看包含 D 的所有子字符串并对它们进行排序在数字末尾 D 的位置，我们将看到以下内容：

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

等等。

也就是说，对于0到n-i-1（含）的每个前缀长度，D在0到i的每个位置出现一次，或者总共n-i次每个数字的位置。这意味着它对总和的总贡献是 D*(n-i) 乘以从 100 到 [=48 的 10 的幂和=]10ⁱ。（碰巧，这个总和正好是 (10i+1−1)⁄9.)

这导致了 Paul Hankin 提出的迭代的稍微简单的版本：

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 整除，因为：

10*n == n + 9*n == (mod 9) n mod 9 + 0
digitSum(n) mod 9 == n mod 9。（因为 10k == 1 mod n 对于任何 k。）
因此(10*n - digitSum(n)) mod 9 == (n - n) mod 9 == 0.

函数f("123")=123+12+23+1+2+3如何写成递推关系

How to write a function f("123")=123+12+23+1+2+3 as a recurrence relationship

algorithm

math

recursion

numbers

number-theory