编程竞赛的一个问题......数字和

Question

我需要帮助解决早期竞争中的问题N:

问题N:数字和

给定3个正整数A,B和C,找到小于或等于A的正整数,当用基数B表示时,有数字总和为C.

输入将由一系列行组成,每行包含三个整数,A,B和C,2≤B≤100,1≤A,C≤1,000,000,000.数字A,B和C在基数10中给出,并由一个或多个空格分隔.输入由包含三个零的行终止.

输出将是每个输入行的数字数(必须在基数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到1的所有数字A.但实际上,这个问题可以在几乎恒定的时间内解决:O(length of A)这是O(log(A)).

1. 提供的代码适用于基数10.使其适用于任意基数是微不足道的.
2. 要达到上述估计时间,您需要为递归添加记忆.如果您对该部分有疑问,请与我们联系.

现在,递归函数本身.用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;
}