c - 如何生成最多 18 位数字，其倒数之和为整数

Question

我正在寻找一种方法来生成一系列数字，其倒数之和是整数？

例如 - 11(1/1 + 1/1 = 2 是整数)、122(1/1+1/2+1/2 是整数)、236(1/2 + 1/3 + 1/6 是整数) 同样。

此外，我想避免重复相同的数字组合或排列。例如，如果打印122，我不想打印212和221。

我想知道如何解决这个问题

Answer 1

一些帮助您入门的想法:

• 您的电话号码不能包含零。
• 您可以随时在有效号码上加上 1，该号码仍然有效。
• 您不需要生成数字。相反，生成数字列表。如果你将列表按升序排列，你将自动解决如何消除排列的问题。
• 每个真分数 1/2 到 1/9 都可以表示为公分母为 2520 的展开分数。

因此以下方法可能有效:

• 从一个空数组开始，总和为 0。
• 现在递归调用生成函数。在每次递归中，检查总和是否能被 2520 整除而没有余数。如果是，请打印该数字，并打印前面用 1 填充的所有数字，直到有 18 位数字为止。因此，对于 236，打印 236、1236、11236 等等，直到 111 111 111 111 111 236。
• 如果您的数组长度为 18，请不要进一步递归。否则，请在将 2 到 9 的每个数字添加到列表后调用您的函数，但不要使用小于列表中最后一位数字的数字来保持列表排序。
• 不要重新计算总和，而是保留一个运行总和:递归时，将相应的分子添加到总和中:2 为 1260，3 为 840，4 为 630，依此类推。

这种自下而上的方法比检查所有可能的数字要快得多。以下程序将在不到一秒的时间内打印所有 14,137 个有效数字(无序，即按生成顺序):

#include <stdlib.h>
#include <stdio.h>

#define NDIGIT 18

void rec(int set[], int n, int sum)
{
    static int num[10] = {
        0, 2520, 1260, 840, 630, 504, 420, 360, 315, 280
    };

    if (sum % 2520 == 0) {
        for (int j = 0; j < NDIGIT - n + 1; j++) {
            for (int i = 0; i < j; i++) putchar('1');
            for (int i = 0; i < n; i++) putchar(set[i] + '0');
            putchar('\n');
        }
    }

    if (n < NDIGIT) {
        int i0 = n ? set[n - 1] : 2;

        for (int i = i0; i < 10; i++) {
            set[n] = i;
            rec(set, n + 1, sum + num[i]);
        }
    }
}

int main()
{
    int set[NDIGIT];

    rec(set, 0, 0);

    return 0;
}

如果需要排序输出，请转换 set一个长整数，也许 uint64_t来自<stdint.h>并将其存储在数组中，而不是立即打印它们。然后对数组进行排序并打印数字。