代码之家 › 专栏 › 技术社区 › user7127000

如何编写函数f(“123”)=123+12+23+1+2+3作为递归关系

number-theory numbers recursion math algorithm

-2

user7127000 · 技术社区 · 7 年前

我想要 f(str) 拿一根绳子 str 然后返回所有子串的和作为数字,我想写 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

3 回复 | 直到 7 年前

Paul Hankin 7 年前

你必须打破 f 分为两个功能。

N[i] 成为 i 输入的第位数字。允许 T[i] 是第一个的子字符串之和 i-1 B[i] 是第一个的后缀之和 一、 输入的字符。

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] 在末尾追加,以及单个字符串 .这些总和为 (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")

rici 7 年前

例如,考虑数字 D _i 在位置 i x _n-1 …x _i+1 D _i y _i-1 …y ₀ x , D 和 y D 并按从数字的末尾,我们将看到以下内容:

       D
      xD
     xxD
       â¦
   xxâ¦xD
      Dy
     xDy
    xxDy
      â¦
  xxâ¦xDy
     Dyy
    xDyy
   xxDyy
     â¦
 xxâ¦xDyy

换句话说,D出现在从0到的每个位置 一、 从0到0的每个前缀长度一次 n-i-1 n-i D*(n-i) 乘以10的幂和 10 ⁰ 到 10 ⁱ (10 ⁱ⁺¹ −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)

10*n == n + 9*n == (mod 9) n mod 9 + 0
digitSum(n) mod 9 == n mod 9 10 ^k == 1 mod n 对于任何 k .)
(10*n - digitSum(n)) mod 9 == (n - n) mod 9 == 0

Poosh 7 年前

看看这个模式:

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) ,可以递归编写函数,如下所示: f(str) = f(str.substring(0, str.length - 1)) + g(str) 什么时候 str.length > 1 ,以及具有 str.length == 1 只返回 (参数 substring 中字符的起始索引以及生成的子字符串的长度。)

对于求解示例(“12395”),递归方程 f(str)=f(strs.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)