如何按递增顺序打印表格2^i * 5^j的编号。

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

最佳答案

这实际上是一个非常有趣的问题,尤其是如果你不希望这是n^ 2或nLogn复杂性。
我要做的是:
定义包含2个值(i和j)和公式结果的数据结构。
定义包含此数据结构的集合(例如std::vector)
使用值(0,0)初始化集合(在本例中,结果为1)
现在在循环中执行以下操作:
在集合中查找并获取具有最小值的实例
从集合中移除
把这个打印出来
基于刚才处理的实例创建2个新实例
在第一个实例中,增量i
在第二种情况下增量j
将这两个实例添加到集合(如果它们还不在集合中)
循环直到你吃饱为止
通过选择正确的数据结构和集合,可以轻松地调整性能。
例如,在C++中,可以使用一个STD::MAP,其中密钥是公式的结果,值是对(I,J)。取最小值就是取映射中的第一个实例(*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;
   }
}

10-05 20:43
查看更多