求解交汇于指定数字的Digital Rivers问题（C语言实现）

问题描述 #

我是C语言及编程新手，现在要解决老师布置的Digital Rivers问题：

• Digital Rivers定义：序列中每个数的下一个数等于自身加上其各位数字之和，例如123的下一个数是123+1+2+3=129。
• 任务要求：读取输入数字N（输入范围≤500），输出所有交汇于该数字的Digital Rivers（即序列包含N的河流）。比如输入32时，需要输出所有能交汇到32的河流。
• 当前困境：已经实现了计算Digital Rivers的部分代码，但不知道如何推进。曾考虑创建数组对比所有起始于1的序列，怀疑这个思路过于复杂，寻求解题提示。

现有代码 #

#include <stdio.h>

int digitsum(int n)
{
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum = sum + digit;
        n = n / 10;
    }
    return sum;
}

int nextnum(int digitsum, int n)
{
    int sum = 0;
    sum = n + digitsum;
    printf("%d\n", sum);
    return sum;
}

int main()
{
  int n;
  printf("N--> ");
  scanf("%d", &n);

  for (int i = 0; i < 20; i++) {
    n = nextnum(digitsum(n), n);
  }

  return 0;
}

解题思路提示 #

• 反向推导代替正向遍历：不用从1开始生成所有序列找包含N的，而是从N往回找可能的前驱数，这个思路更高效。
  原理：如果y的下一个数是z，那么y = z - s，其中s是y的各位数字之和，且必须满足y + digitsum(y) == z。
• 缩小前驱查找范围：一个数的各位数字之和最大是9乘以它的位数（比如三位数最大27），所以N的前驱x的范围是max(1, N - 9*位数)到N-1，不用遍历所有数。
• 递归/迭代找所有起始点：找到N的前驱后，继续找这些前驱的前驱，直到找不到符合条件的x（x<1或超过500）。这些最终的起始点就是每条河流的起点。
• 避免重复计算：可以用一个布尔数组标记已经处理过的数，比如某个数已经被确定是某条河流的一部分，就不用再处理它的其他路径。
• 生成并输出河流：找到所有起始点后，从每个起始点开始生成序列直到N，把这些序列输出即可。

内容的提问来源于stack exchange，提问作者Totally_Lost