查找生成给定数字所需的最小位数。

Question

我们必须找到生成给定数字所需的最小位数，例如: 14 => 95 (9 +5= 14)是两位数，这是14的最小位数。

int moves(int n) {

    int m = 0;            // Minimum count

    while (n-9 >= 0) {    // To place maximum number of 9's
        n -= 9;
        m++;
    }

    if (n == 0) {         // If only nines made up the number
        return m;
    }

    else {
        m++;
        return m;
    }
}

我得到了一个TLE (超过运行时的时间限制)由一个在线法官。我怎样才能改进它，或者有没有更好的方法？

Answer 1

您的代码首先查看9是否符合该数字的次数。这可以更容易做到：

int m = n/9;

这就足够了，因为我们执行整数除法，其中的余数被丢弃。请注意，如果n是float或另一种浮动类型，则这将无法工作。

剩下的问题是它是否可以被9整除。如果没有，我们还有一个数字。这可以由模运算符来完成(为了便于理解而使其冗长)：

bool divisible_by_nine = (n % 9 == 0);

假设您可能不知道模运算符，它返回整数除法的余数，47 %9= 2，因为47 /9=5余数2。

没有它，你就会

int remainder = n - 9*m;
bool divisible = (remainder == 0);

合并：

int required_digits(int number)
{
   bool divisible = (number % 9 == 0);
   return number/9 + (divisible ? 0 : 1);
}

或者在一行中，取决于您希望它的详细程度：

int required_digits(int number)
{
   return number/9 + (number % 9 == 0 ? 0 : 1);
}

由于没有任何循环，这是在Θ(1)中，因此应该在所需的时间限制内工作。

(从技术上讲，处理器可能在某种程度上和内部一样处理这个部门，但它在这方面非常有效。要做到绝对正确，我必须加上“假设除法是一个固定时间操作”)。

Answer 2

你的解决方案很好。你可以试试更短的：

return (n%9==0)? n/9 : n/9 +1 ;

较短，但不易阅读.

或者妥协：

if (n%9==0) // n can be divided by 9
   return n/9;
else
   return n/9+1;

Answer 3

解释

我们知道，每个数字a都可以表示为(a_n * 10 ^ n) + ... + (a_2 * 10 ^ 2) + (a_1 * 10) + (a_0)，其中a_k是数字。

和10^n = 11...11 * 9 + 1 (n位数1)。

这意味着数字10^n可以表示为11.11+1位的和。

现在我们可以将a写成(a_n * 11..11 * 9 + a_n) + ...

分组后9(帮助，我不知道这个英语术语。)) (a_n * 11..11 + a_n-1 * 11..11 + ... a_1) * 9 + (a_n + a_n-1 + ... + a_1 + a_0)，我将把它写成b_9 * 9 + b_1。

这意味着数字a可以表示为b_9数字9+ b_1所需的数字之和(顺便说一句，这是递归的)

重述：

让我们调用函数f

• If -10 <位数< 10，结果为1.

需要两个计数器，c2.和

• 在数字上迭代

对每一位c1的

• ，乘以i数字11.11，并将结果添加到i中

c2向

• 添加i第四位数字

c_1 + f(c_2)

• 结果是

在实践中，以非递归的方式实现这一点。