从编程竞赛的问题......数字求和

本文介绍了从编程竞赛的问题......数字求和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我需要帮助，从这个早期的竞争解决问题N：

I need help solving problem N from this earlier competition:

由于3个正整数A，B和C，发现有多少正整数少大于或等于A，当EX pressed在基地B，有位该笔款项为C。

输入将包括一系列线，各含三个整数， A，B和C，2≤乙≤100，1≤A，C≤ 10亿。数字A，B和C 列于基座10和分离由一个或多个空格。输入是由线包含三个终止零。

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.

输出将是数字的数，对于每个输入线路（它必须被给予在基数为10）。

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

示例输出

有关的规则：

从键盘读取所有输入，即使用标准输入， System.in ， CIN 或同等学历。将输入从文件重定向到形成输入到您所提交。

Read all input from the keyboard, i.e. use stdin, System.in, cin or equivalent. Input will be redirected from a file to form the input to your submission.

写入所有输出到屏幕上，即使用标准输出，的System.out ， COUT 或同等学历。不要写标准错误。不要使用，甚至包括所有的模块，可以直接操控屏幕，如 conio ， CRT 或类似的话。从你的程序输出重定向到一个文件中供以后查看。使用直接I / O是指这样的输出不能重定向，因此不能进行检查。这可能意味着一个正确的程序被拒绝！

Write all output to the screen, i.e. use stdout, System.out, cout or equivalent. Do not write to stderr. Do NOT use, or even include, any module that allows direct manipulation of the screen, such as conio, Crt or anything similar. Output from your program is redirected to a file for later checking. Use of direct I/O means that such output is not redirected and hence cannot be checked. This could mean that a correct program is rejected!

除非另有说明，在输入的所有整数将适用于一个标准的32位计算机字。上的线相邻整数将被一个或多个空格分隔。

Unless otherwise stated, all integers in the input will fit into a standard 32-bit computer word. Adjacent integers on a line will be separated by one or more spaces.

当然，这是公平地说，我应该学会更试图解决过，但我真的AP preciate，如果有人在这里告诉我如何做。

Of course, it's fair to say that I should learn more before trying to solve this, but i'd really appreciate it if someone here told me how it's done.

在此先感谢，约翰。

Other people pointed out trivial solution: iterate over all numbers from 1 to A. But this problem, actually, can be solved in nearly constant time: O(length of A), which is O(log(A)).

提供

code是基地10适应它的任意基地实在是微不足道。

要达到上述估计的时候，你需要添加记忆以递归。让我知道，如果您有任何关于这部分的问题。

Code provided is for base 10. Adapting it for arbitrary base is trivial.
To reach above estimate for time, you need to add memorization to recursion. Let me know if you have questions about that part.

现在，递归函数本身。 Java编写的，但一切都应该在C＃/ C ++，没有任何变化。这是很大的，但意见在那里我试图澄清算法，主要是因为。

Now, recursive function itself. Written in Java, but everything should work in C#/C++ without any changes. It's big, but mostly because of comments where I try to clarify algorithm.

// 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;
}

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

Now, let's write a little tester

    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);

您可以编写多个COM prehensive测试仪检查A的所有值，但整体解决方案似乎是正确的。（我试了随机A的和C的。）

You can write more comprehensive tester checking all values of A, but overall solution seems to be correct. (I tried several random A's and C's.)

不要忘了，你不能为测试解决方案A == 10亿无记忆：它会运行过久。但随着记忆，你可以测试它甚至 A == 10 ^ 1000 。

Don't forget, you can't test solution for A == 1000000000 without memorization: it'll run too long. But with memorization, you can test it even for A == 10^1000.

修改
只是为了证明一个概念，穷人的记忆。（在Java中，在其他语言哈希表的声明有所不同），但是如果你想学习的东西，它可能是更好的尝试自己做。

edit
Just to prove a concept, poor man's memorization. (in Java, in other languages hashtables are declared differently) But if you want to learn something, it might be better to try to do it yourself.

// 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;
}

这篇关于从编程竞赛的问题......数字求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

solution

从编程竞赛的问题......数字求和

问题描述

推荐答案