1

整数数组 A[i] (i > 1) 定义如下：元素 A[k] ( k > 1) 是大于 A[k-1] 的最小数，使得其数字之和等于数字 4* A[k-1] 的数字之和。

您需要编写一个程序，根据给定的第一个元素 A[1] 计算此数组中的第 N 个数。

输入：在一行标准输入中，有两个数字用一个空格分隔：A[1] (1 <= A[1] <= 100) 和 N (1 <= N <= 10000)。

输出：标准输出应该只包含一个整数 A[N] ，即定义序列的第 N 个数字。

输入：7 4

输出：79

解释：数组的元素如下：7、19、49、79……第4个元素是解。

我尝试通过编写一个单独的函数来解决这个问题，该函数对于给定的数字 A[k] 计算它的数字之和，并找到大于 A[k-1] 的最小数字，正如它在问题中所说的那样，但没有成功。第一次测试由于内存限制而失败，第二次测试由于时间限制而失败，现在我不知道如何解决这个问题。一位朋友建议递归，但我不知道如何设置。

任何可以以任何方式帮助我的人都请写信，同时提出一些关于使用递归/DP 来解决这个问题的想法。谢谢。

4

3 回答 3

1

这与递归无关，几乎与动态编程无关。您只需要找到可行的优化以使其足够快。只是一个提示，尝试理解这个解决方案：

http://codepad.org/LkTJEILz

于 2010-03-21T16:10:00.667 回答
0

这是python中的一个简单解决方案。它只使用迭代，即使对于快速而肮脏的解决方案，递归也是不必要且效率低下的。

def sumDigits(x):
    sum = 0;
    while(x>0):
        sum += x % 10
        x /= 10
    return sum

def homework(a0, N):
    a = [a0]
    while(len(a) < N):
        nextNum = a[len(a)-1] + 1
        while(sumDigits(nextNum) != sumDigits(4 * a[len(a)-1])):
            nextNum += 1
        a.append(nextNum)
    return a[N-1]

PS。我知道我们真的不应该给出家庭作业的答案，但看起来 OP 在 C++ 类的介绍中，所以可能还不知道 python，希望它看起来像伪代码。此外，代码缺少许多简单的优化，这可能会使解决方案变得太慢。

于 2010-03-21T16:54:11.933 回答
0

它是相当递归的。

问题的核心是：

找到大于 K 且具有digitsum(N) = J 的最小数N。

  • 如果digitsum(K) == J 则测试N = K + 9 是否满足条件。

  • 如果digitum(K) < J 那么可能N 与K 仅在个位上不同（如果digitsum 可以在不超过9 的情况下达到）。

  • 否则，如果 digitsum(K) <= J 新的个位数是 9，并且问题递归到“找到大于 (K/10) 且具有 digitsum(N') = J-9 的最小数字 N'，然后 N = N' *10 + 9"。

  • 如果digitsum(K) > J 那么 ???

在每种情况下 N <= 4 * K

9 -> 18 根据第一条规则

52 -> 55 根据第二条规则

99 -> 189 由第三条规则，在递归期间使用第一条规则

25 -> 100 需要第四种情况，我最初没有看到需要。

还有反例吗？

于 2010-03-21T17:34:29.913 回答