algorithm - 按递增顺序打印 2^i * 5^j 形式的数字

Question

如何按递增顺序打印 2^i * 5^j 形式的数字。

For eg:
1, 2, 4, 5, 8, 10, 16, 20

Answer 1

这实际上是一个非常有趣的问题，特别是如果您不希望这是 N^2 或 NlogN 的复杂性。

我会做的是:

• 定义一个包含 2 个值(i 和 j)和公式结果的数据结构。
• 定义一个包含此数据结构的集合(例如 std::vector)
• 用值 (0,0) 初始化集合(本例中结果为 1)
• 现在循环执行以下操作:
  • 查看集合，取值最小的实例
  • 将其从集合中移除
  • 打印出来
  • 根据您刚刚处理的实例创建 2 个新实例
    • 在第一个实例中自增i
    • 在第二个实例中自增j
  • 将两个实例添加到集合中(如果它们不在集合中)
• 循环直到你受够了

可以通过选择正确的数据结构和集合轻松调整性能。例如。在 C++ 中，您可以使用 std::map，其中键是公式的结果，值是对 (i,j)。取最小值就是取 map 中的第一个实例 (*map.begin())。

我很快写了下面的应用程序来说明它(它有效!但不包含进一步的评论，抱歉):

#include <math.h>
#include <map>
#include <iostream>

typedef __int64 Integer;

typedef std::pair<Integer,Integer> MyPair;
typedef std::map<Integer,MyPair> MyMap;

Integer result(const MyPair &myPair)
{
return pow((double)2,(double)myPair.first) * pow((double)5,(double)myPair.second);
}

int main()
{
MyMap myMap;
MyPair firstValue(0,0);

myMap[result(firstValue)] = firstValue;

while (true)
   {
   auto it=myMap.begin();
   if (it->first < 0) break;        // overflow

   MyPair myPair = it->second;
   std::cout << it->first << "= 2^" << myPair.first << "*5^" << myPair.second << std::endl;

   myMap.erase(it);

   MyPair pair1 = myPair;
   ++pair1.first;
   myMap[result(pair1)] = pair1;

   MyPair pair2 = myPair;
   ++pair2.second;
   myMap[result(pair2)] = pair2;
   }
}