algorithm - 来自编程竞赛的问题......数字和

Question

我需要帮助解决 problem N from this earlier competition :

问题 N:数字和

Given 3 positive integers A, B and C, find how many positive integers less than or equal to A, when expressed in base B, have digits which sum to C.

Input will consist of a series of lines, each containing three integers, A, B and C, 2 ≤ B ≤ 100, 1 ≤ A, C ≤ 1,000,000,000. The numbers A, B and C are given in base 10 and are separated by one or more blanks. The input is terminated by a line containing three zeros.

Output will be the number of numbers, for each input line (it must be given in base 10).

示例输入

100 10 9
100 10 1
750000 2 2
1000000000 10 40
100000000 100 200
0 0 0

示例输出

10
3
189
45433800
666303

相关规则:

1. 从键盘读取所有输入，即使用 stdin、System.in、cin 或等价物。输入将从文件重定向以形成提交的输入。

2. 将所有输出写入屏幕，即使用 stdout、System.out、cout 或等效项。不要写入 stderr。不要使用，甚至不要包含任何允许直接操作屏幕的模块，例如 conio、Crt 或任何类似的模块。程序的输出被重定向到一个文件以供以后检查。使用直接 I/O 意味着这样的输出不会被重定向，因此无法被检查。这可能意味着正确的程序被拒绝了!

3. 除非另有说明，否则输入中的所有整数都适合标准的 32 位计算机字。一行中相邻的整数将由一个或多个空格分隔。

当然，公平地说，在尝试解决此问题之前我应该​​了解更多信息，但如果有人告诉我这是如何完成的，我将不胜感激。

提前致谢，约翰。

Answer 1

其他人指出了简单的解决方案:遍历从 1 到 A 的所有数字。但实际上，这个问题可以在几乎恒定的时间内解决:O(length of A)，即 O(log(A))。

1. 提供的代码以 10 为基数。将其改编为任意基数是微不足道的。
2. 要达到上述估计时间，您需要添加 memorization递归。如果您对此部分有任何疑问，请告诉我。

现在，递归函数本身。用 Java 编写，但一切都应该在 C#/C++ 中运行，无需任何更改。它很大，但主要是因为我试图澄清算法的评论。

// returns amount of numbers strictly less than 'num' with sum of digits 'sum'
// pay attention to word 'strictly'
int count(int num, int sum) {
    // no numbers with negative sum of digits
    if (sum < 0) {
        return 0;
    }

    int result = 0;

    // imagine, 'num' == 1234
    // let's check numbers 1233, 1232, 1231, 1230 manually
    while (num % 10 > 0) {
        --num;

        // check if current number is good
        if (sumOfDigits(num) == sum) {
            // one more result
            ++result;
        }
    }

    if (num == 0) {
        // zero reached, no more numbers to check
        return result;
    }

    num /= 10;

    // Using example above (1234), now we're left with numbers
    // strictly less than 1230 to check (1..1229)
    // It means, any number less than 123 with arbitrary digit appended to the right
    // E.g., if this digit in the right (last digit) is 3,
    // then sum of the other digits must be "sum - 3"
    // and we need to add to result 'count(123, sum - 3)'

    // let's iterate over all possible values of last digit
    for (int digit = 0; digit < 10; ++digit) {
        result += count(num, sum - digit);
    }

    return result;
}

辅助函数

// returns sum of digits, plain and simple
int sumOfDigits(int x) {
    int result = 0;
    while (x > 0) {
        result += x % 10;
        x /= 10;
    }
    return result;
}

现在，让我们写一个小测试器

    int A = 12345;
    int C = 13;

    // recursive solution
    System.out.println(count(A + 1, C));

    // brute-force solution 
    int total = 0;
    for (int i = 1; i <= A; ++i) {
        if (sumOfDigits(i) == C) {
            ++total;
        }
    }
    System.out.println(total);

您可以编写更全面的测试程序来检查 A 的所有值，但总体解决方案似乎是正确的。 (我尝试了几个随机的 A 和 C。)

请记住，如果不内存，您就无法测试 A == 1000000000 的解决方案:它会运行太久。但是通过内存，您甚至可以对 A == 10^1000 进行测试。

编辑
只是为了证明一个概念，穷人的内存力。 (在 Java 中，哈希表在其他语言中的声明方式不同)但是如果您想学习一些东西，最好自己动手做。

// hold values here
private Map<String, Integer> mem;

int count(int num, int sum) {
    // no numbers with negative sum of digits
    if (sum < 0) {
        return 0;
    }

    String key = num + " " + sum;
    if (mem.containsKey(key)) {
        return mem.get(key);
    }

    // ... 
    // continue as above...
    // ...

    mem.put(key, result);
    return result;
}