algorithm - 找到数字之和为 10 的第 K 个最小的数

问题描述

寻找替代算法

以下是我制作的，但在编码网站上被在线法官标记为不正确。

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

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

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

}

所以我需要效率更高的替代算法。提前致谢

标签： algorithmrecursionwhile-loopsumdigits

解决方案

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

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

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

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

附加说明

在代码中，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;
}

algorithm - 找到数字之和为 10 的第 K 个最小的数

问题描述

解决方案

推荐阅读