当前位置：文江博客话题详情

数组：数学序列

发布于 2024-08-25 23:50:56 字数 573 浏览 6 评论 0原文

整数数组 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 来解决这个问题的想法。谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

心的憧憬 2024-09-01 23:50:56

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

http://codepad.org/LkTJEILz

回复收藏 0 原文

瞄了个咪的 2024-09-01 23:50:56

这是 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]

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

Here is a simple solution in python. It only uses iteration, recursion is unnecessary and inefficient even for a quick and dirty solution.

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. I know we're not really supposed to give homework answers, but it appears the OP is in an intro to C++ class so probably doesn't know python yet, hopefully it just looks like pseudo code. Also the code is missing many simple optimizations which would probably make it too slow for a solution as is.

回复收藏 0 原文

回眸一遍 2024-09-01 23:50:56

这是相当递归的。

问题的核心是：

找到大于 K 的最小数 N，并且 digitalsum(N) = J。

如果 digitalsum(K) == J 则测试 N = K + 9 是否满足条件。
如果数字和(K) <那么 J 可能仅在个位数上与 K 不同（如果可以在不超过 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 需要第四种情况，我原本认为不需要。

还有更多反例吗？