找出第 K 个最小的数字，其数字的总和为 10

Question

寻找替代算法

以下是我制作但在编码网站上被 Online Judge 标记为不正确的。

在声明了int数据类型k的变量后，l收到了一个输入从控制台使用 cin()。由于问题的限制表明可能的数字 is/are 在 1 到 20000 之间，我首先使用这些条件打开了一个 for 循环。在 i 的每次迭代中（一个接一个），测试数字是否其数字相加到 10，如果是，它是否是第 k 个数字总和为 10 的数字。

为了找到数字的总和，我使用了递归函数或使用 while 循环的迭代方法。因此有两段代码。在这两种方法中，总和是通过首先使用模块化 % 运算符和除法运算符 / 查找数字来计算的。计算出总和，然后进一步测试它是否等于 10，如果是，还通过保持所有先前相似元素的计数来测试它是否是第 K 个元素。所有条件都满足后，才是我用cout()输出的值。

#include <bits/stdc++.h>

using namespace std;

//recursion to get sum of digits.

*int sum(int d)

{

 return d==0?0:d%10+sum(d/10);

}*

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

    {

     int total=sum(i);

      if(total==10)

     {

      --k;

      if(k==0)

      cout<<i<<"\n";

      }

     }

  }

   return 0;

}

第二个，我使用迭代（while循环）来推导出数字和

#include <bits/stdc++.h>

using namespace std;

int main()

{
  
  //ios_base::sync_with_stdio(false);

  //cin.tie(NULL);

   int t;

   cin>>t;

   while(t-- >0)

   {

    int k;

    cin>>k;

    for(int i=0;i<20000;i++)

{

     int sum=0,d=i;

     *while(d!=0)

       {

          sum+=d%10;

           d/=10;

       }*


     if(sum==10)

       {

         --k;

          if(k==0)

          cout<<i<<"\n";

        }
    }

 }

return 0;

}

So l need alternative algorithms of better efficiency. Thanks in advance

Answer 1

你可以用“递归”的方式解决这个问题。

如果给定数字以数字 d 开头，则后面的数字之和必须为 10-d。由于数字不超过20000，所以最多5位，第一位是0、1。

一个简单的解决方案是使用四个嵌套循环。然后你检查最后一位数字是否合法。

n= 0
for d4= 0 to 1
    for d3= 0 to min(9, d-d4)
        for d2= 0 to min(9, d-d4-d3)
            for d1= 0 to min(9, d-d4-d3-d2)
                d0= 0 d-d4-d3-d2-d1
                if 0 <= d0 and d0 <= 9:
                    n+= 1
                    if n == k stop

可以进行一些微优化。使用这种方法，我找到了 502 个不同的解决方案。

Answer 2

我误解了这些约束，但终于找到了解决方案。 1<=K<=2*10^4 约束是针对变量 K 的，数字 X 的值是一个正整数，因此我初始化了 x=1。我在无限循环内应用了一个 break 语句（以便在找到并打印数字时执行它）即 while(1).

包括的主题有：递归、迭代、if 语句、循环控制语句。

#include <bits/stdc++.h>

using namespace std;

int main()

{
  //write your code here

  //ios_base::sync_with_stdio(false);

 // cin.tie(NULL);

  int t;

  cin>>t;

  while(t>0)

  {

    int k;

    cin>>k;

    int x=1;

    while(1)

    {

     int sum=0;

     int d=x;

     while(d!=0)

     {

     sum+=d%10;

      d/=10;

     }

      if(sum==10)

      k--;

      if(k==0)

      {

      cout<<x<<"\n";

      break;

      }

      x++;

    }

    t--;

    }

     return 0;

     }

Answer 3

您的代码的主要问题是您限制搜索小于 20000 的值。

为了提高效率，我加了两个小技巧

我通过记住以前的结果来避免多次执行相同的计算
我根据位数之和的值，调整增量的值

在我的电脑上，计算最大值需要 0.15 秒（k = 20000）。

补充说明

代码中，i变量对应个候选，即我们测试数字和是否等于10的值。

num对应找到解的索引。一个解对应一个数，数位之和等于10。mem[num] = i表示i是num^th解。 k 与 OP 代码中的含义相同：我们想要找到 k^th 数字，使得数字总和 = 10。

这两行int kmax = 1; mem[1] = 19;利用了19是第一个有效解的事实。这是初始化 mem 向量的管理所必需的，它会记住所有找到的解决方案。

用于加速该过程的技巧如下：

如果当前数i的和等于10，则我们知道i和i+8之间没有其他解。例如，在 27 之后，下一个解等于 36。所以我们可以做 i += 9 而不是简单地 i++.
如果总和大于10，那么简单地增加第一个数字是找不到解的。例如，如果i = 85，我们可以直接进入90，也就是将最小位置零。这是用 i += (10 - i%10);
如果总和小于 10，例如5，那么你可以直接加5而不是1。这是用i += (10 - total);

实际上，有可能走得更远。例如，如果i = 99000，那么我们可以直接添加1000而不是10。我没有走得太远，因为获得的代码似乎已经有点过分了（0.15s而不是1s）。

#include <iostream>
#include <vector>

int sum(int d) {
    int ans = 0;
    while(d) {
        ans += d%10;
        d /= 10;
    }
    return ans;
}

int main() {
    int t;
    std::cin >> t;
    std::vector<int> mem(20001, 0);
    int kmax = 1;
    mem[1] = 19;
    while(t-- >0) {
        int i, k;
        std::cin >> k;
        int num = 1;
        if (k > kmax) {
            i = mem[kmax];
            num = kmax;
            while(true) {
                int total = sum(i);
                if(total == 10) {
                    mem[num] = i;
                    if (num == k) break;
                    num++;
                    i += 9;
                } else {
                    if (total > 10) {
                        i += (10 - i%10);
                    } else {
                        i += (10 - total);
                    }
                }
            }
            kmax = k;
        }
        std::cout << mem[k] <<"\n";
    }
    return 0;
}

Answer 4

为了完整性，这里是必需的数字动态程序。这个可以让你用二进制搜索几乎立即找到第 200,000 个（更不用说第 20,000 个）。

JavaScript代码：

function g(digits, i, sum, bound, memo){
  const key = String([i, sum, bound]);

  if (memo.hasOwnProperty(key))
    return memo[key];
    
  if (sum == 0)
    return memo[key] = 1;
    
  if (i == 0)
    return sum <= (bound ? digits[0] : 9);

  let result = 0;
  
  const k = bound ? digits[i] : 9;

  for (let d=0; d<=k && d<=sum; d++){
    const _bound = digits[i] == d ? bound : 0;
    result += g(digits, i-1, sum-d, _bound, memo);
  }
  
  return result;
}


function f(n, sum){
  const digits = [];
  
  while(n){
    digits.push(n % 10);
    n = Math.floor(n/10);
  }
  
  return g(digits, digits.length-1, sum, 1, {});
}

console.log(f(320002210, 10));

console.log(f(320002209, 10));

找出第 K 个最小的数字，其数字的总和为 10

Find the Kth smallest number whose digits have a sum of 10

algorithm

recursion

sum

digits

while-loop