16

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

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

10 回答 10

2

这非常适合函数式编程风格。在 F# 中：

let min (a,b)= if(a<b)then a else b;;
type stream (current, next)=
    member this.current = current
    member this.next():stream = next();;
let rec merge(a:stream,b:stream)=
    if(a.current<b.current) then new stream(a.current, fun()->merge(a.next(),b))
    else new stream(b.current, fun()->merge(a,b.next()));;

let rec Squares(start) = new stream(start,fun()->Squares(start*2));;

let rec AllPowers(start) = new stream(start,fun()->merge(Squares(start*2),AllPowers(start*5)));;
let Results = AllPowers(1);;

与 Results 一起工作，然后成为具有当前值和下一个方法的流类型。

走过它：

  1. 我将 min 定义为完整性。
  2. 我将流类型定义为具有当前值和返回新字符串的方法，基本上是数字流的头部和尾部。
  3. 我定义了函数合并，它采用两个流的当前值中较小的一个，然后递增该流。然后它递归提供流的其余部分。本质上，给定两个有序的流，它将产生一个有序的新流。
  4. 我将正方形定义为以 2 的幂增加的流。
  5. AllPowers 采用起始值，并以 5 的幂数将所有平方产生的流合并。它与将其乘以 5 产生的流，因为这是您仅有的两个选项。您实际上只剩下一棵结果树

结果是合并越来越多的流，所以你合并以下流

1、2、4、8、16、32...

5、10、20、40、80、160...

25、50、100、200、400...

.

.

. 通过尾递归和编译器优化等，合并所有这些结果是相当有效的。

这些可以像这样打印到控制台：

let rec PrintAll(s:stream)=
    if (s.current > 0) then
        do System.Console.WriteLine(s.current)
        PrintAll(s.next());;

PrintAll(Results);

let v = System.Console.ReadLine();

类似的事情可以用任何允许递归和将函数作为值传递的语言来完成（如果你不能将函数作为变量传递，它只会稍微复杂一点）。

于 2011-09-27T16:43:34.277 回答
2

这实际上是一个非常有趣的问题，特别是如果您不希望这是 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;
   }
}
于 2011-09-27T16:30:06.557 回答
2

对于 O(N) 解决方案，您可以使用到目前为止找到的数字列表和两个索引：一个表示要乘以 2 的下一个数字，另一个表示要乘以 5 的下一个数字。然后在每次迭代中，您有两个候选值可供选择较小的一个。

在 Python 中：

 numbers = [1]
 next_2 = 0
 next_5 = 0

 for i in xrange(100):
     mult_2 = numbers[next_2]*2
     mult_5 = numbers[next_5]*5

     if mult_2 < mult_5:
        next = mult_2
        next_2 += 1
     else:
        next = mult_5
        next_5 += 1

     # The comparison here is to avoid appending duplicates
     if next > numbers[-1]:
        numbers.append(next)

 print numbers
于 2011-09-28T03:57:40.497 回答
1

我把这个问题想象成一个矩阵M，其中M(i,j) = 2^i * 5^j. 这意味着行和列都在增加。

考虑以递增的顺序在条目中画一条线，显然从 entry 开始(1,1)。当您访问条目时，行和列增加条件确保由这些单元格形成的形状将始终是整数分区（英文表示法）。跟踪此分区（行中较小条目的数量在mu = (m1, m2, m3, ...)哪里- 因此）。然后，您需要比较的唯一条目是那些可以添加到分区的条目。miim1 >= m2 >= ...

这是一个粗略的例子。假设你已经访问了所有的xs ( mu = (5,3,3,1))，那么你只需要检查@s：

x x x x x @
x x x @
x x x 
x @
@

因此，检查的数量是可添加的单元格的数量（如果您想用姿势来思考，则相当于按Bruhat 顺序上升的方式的数量）。

给定一个 partition mu，很容易确定可添加的状态是什么。0在最后一个正条目之后绘制一个无限的 s 字符串。那么你可以增加mi当1且仅当m(i-1) > mi。

回到例子，因为mu = (5,3,3,1)我们可以增加m1 (6,3,3,1)orm2 (5,4,3,1)或m4 (5,3,3,2)or m5 (5,3,3,1,1)。

问题的解决方案然后找到正确的分区序列（饱和链）。在伪代码中：

mu = [1,0,0,...,0];
while (/* some terminate condition or go on forever */) {
    minNext = 0;
    nextCell = [];
    // look through all addable cells
    for (int i=0; i<mu.length; ++i) {
        if (i==0 or mu[i-1]>mu[i]) {
            // check for new minimum value
            if (minNext == 0 or 2^i * 5^(mu[i]+1) < minNext) {
                nextCell = i;
                minNext = 2^i * 5^(mu[i]+1)
            }
        }
    }
    // print next largest entry and update mu
    print(minNext);
    mu[i]++;
}

我在 Maple 中写了这个，在 12 次迭代后停止：

1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50

并添加了输出的单元格序列并得到了这个：

1  2  3  5  7 10
4  6  8  11 
9  12

对应于这个矩阵表示：

1, 2, 4, 8, 16, 32...

5, 10, 20, 40, 80, 160...

25, 50, 100, 200, 400...
于 2011-10-10T22:47:56.723 回答
1

所以我们有两个循环，一个递增i，第二个j从零开始递增，对吧？（乘法符号在问题的标题中令人困惑）

你可以做一些非常简单的事情：

  1. 添加数组中的所有项目
  2. 对数组进行排序

或者您需要具有更多数学分析的其他解决方案？

编辑：通过利用与合并排序问题的相似性更智能的解决方案

如果我们想象无限数量的2^i和5^j作为两个独立的流/列表的集合，这个问题看起来与众所周知的合并排序问题非常相似。

所以解决步骤是：

  • 从每个流中获取两个数字一个（2 个和 5 个）
  • 相比
  • 返回最小
  • 从先前返回的最小的流中获取下一个数字

就是这样！;)

PS：归并排序的复杂度always是O(n*log(n))

于 2011-09-27T15:53:08.997 回答
0

作为一名数学家，当我看到这样的事情时，我总是首先想到的是“对数有帮助吗？”。

在这种情况下可能会。

如果我们的 A 系列在增加，那么系列 log(A) 也在增加。由于 A 的所有项都具有 2^i.5^j 的形式，因此系列 log(A) 的所有成员都具有 i.log(2) + j.log(5) 的形式

然后我们可以查看系列 log(A)/log(2)，它也在增加，其元素的形式为 i+j.(log(5)/log(2))

如果我们计算出为最后一个系列（称为 B）生成完整有序列表的 i 和 j，那么 i 和 j 也将正确生成系列 A。

这只是改变了问题的性质，但希望它变得更容易解决。在每个步骤中，您可以增加 i 和减少 j，反之亦然。

查看您可以进行的一些早期更改（我可能将其称为 i、j 的转换或只是 transorms）为我们提供了一些关于我们前进方向的线索。

显然，将 i 增加 1 将使 B 增加 1。但是，鉴于 log(5)/log(2) 约为 2.3，那么将 j 增加 1 而将 i 减少 2 只会增加 0.3 。那么问题是在每个阶段找到对于 i 和 j 的变化 B 的最小可能增加。

为了做到这一点，我只保留了一个记录，因为我增加了 i 和 j 的最有效变换（即从每个中添加和减去什么）以获得系列中最小的可能增加。然后应用任何一个有效的（即确保 i 和 j 不会变为负数）。

由于在每个阶段都可以减少 i 或减少 j，因此实际上可以单独检查两类转换。一个新的转换不必具有最好的总分才能包含在我们未来的检查中，只要比同类中的任何其他都好。

为了测试我的想法，我在 LinqPad 中编写了一个程序。需要注意的关键事项是 Dump() 方法只是将对象输出到屏幕，并且语法/结构对于真正的 c# 文件无效。如果你想运行它，转换它应该很容易。

希望任何未明确解释的内容都可以从代码中理解。

void Main()
{
    double C = Math.Log(5)/Math.Log(2);
    int i = 0;
    int j = 0;
    int maxi = i;
    int maxj = j;

    List<int> outputList = new List<int>();
    List<Transform> transforms = new List<Transform>();
    outputList.Add(1);
    while (outputList.Count<500)
    {
    Transform tr;
        if (i==maxi)
        {
            //We haven't considered i this big before. Lets see if we can find an efficient transform by getting this many i and taking away some j.
            maxi++;
            tr = new Transform(maxi, (int)(-(maxi-maxi%C)/C), maxi%C);
            AddIfWorthwhile(transforms, tr);
        }
        if (j==maxj)
        {
            //We haven't considered j this big before. Lets see if we can find an efficient transform by getting this many j and taking away some i.
            maxj++;
            tr = new Transform((int)(-(maxj*C)), maxj, (maxj*C)%1);
            AddIfWorthwhile(transforms, tr);
        }
        //We have a set of transforms. We first find ones that are valid then order them by score and take the first (smallest) one.
        Transform bestTransform = transforms.Where(x=>x.I>=-i && x.J >=-j).OrderBy(x=>x.Score).First();
        //Apply transform
        i+=bestTransform.I;
        j+=bestTransform.J;
        //output the next number in out list.
        int value = GetValue(i,j);
        //This line just gets it to stop when it overflows. I would have expected an exception but maybe LinqPad does magic with them?
        if (value<0) break;
        outputList.Add(value);
    }
    outputList.Dump();

}

public int GetValue(int i, int j)
{
    return (int)(Math.Pow(2,i)*Math.Pow(5,j));
}

public void AddIfWorthwhile(List<Transform> list, Transform tr)
{
    if (list.Where(x=>(x.Score<tr.Score && x.IncreaseI == tr.IncreaseI)).Count()==0)
    {
        list.Add(tr);
    }
}

// Define other methods and classes here
    public class Transform
    {
        public int I;
        public int J;
        public double Score;
        public bool IncreaseI
        {
            get {return I>0;}
        }

        public Transform(int i, int j, double score)
        {
            I=i;
            J=j;
            Score=score;
        }
    }

我没有费心查看它的效率，但我强烈怀疑它比其他一些解决方案更好，因为在每个阶段我需要做的就是检查我的一组转换 - 计算出其中有多少与“n”相比是不平凡的。这显然是相关的，因为你走得越远，转换的次数就越多，但是新转换的数量在更高的数字下变得非常小，所以它可能只是 O(1)。不过，这个 O 的东西总是让我感到困惑。;-)

与其他解决方案相比，它的一个优点是它允许您计算 i,j 而无需计算乘积，这使我无需计算实际数字本身就可以计算出序列是什么。

对于前 230 个数字之后的价值（当 int 空间不足时），我每次都要检查 9 个转换。并且考虑到它只有我的总数溢出，如果前一百万个结果我跑到 i=5191 和 j=354。转换次数为 23。列表中此数字的大小约为 10^1810。达到此级别的运行时间约为 5 秒。

PS如果你喜欢这个答案，请随时告诉你的朋友，因为我花了很长时间在这上面，几个+1将是很好的补偿。或者实际上只是评论告诉我你的想法。:)

于 2011-09-28T15:10:08.683 回答
0

如果你可以在 O(nlogn) 中做到这一点，这里有一个简单的解决方案：

Get an empty min-heap
Put 1 in the heap
while (you want to continue)
    Get num from heap
    print num
    put num*2 and num*5 in the heap

你有它。通过最小堆，我的意思是最小堆

于 2011-09-27T22:42:03.570 回答
0

首先，（正如其他人已经提到的）这个问题非常模糊！

不过，我将根据您的模糊方程式和您预期的结果进行测试。因此，我不确定以下内容是否适用于您正在尝试做的事情，但是它可能会让您对 java 集合有所了解！

import java.util.List;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;


public class IncreasingNumbers {

    private static List<Integer> findIncreasingNumbers(int maxIteration) {
        SortedSet<Integer> numbers = new TreeSet<Integer>();
        SortedSet<Integer> numbers2 = new TreeSet<Integer>();

        for (int i=0;i < maxIteration;i++) {
            int n1 = (int)Math.pow(2, i);
            numbers.add(n1);

            for (int j=0;j < maxIteration;j++) {
                int n2 = (int)Math.pow(5, i);
                numbers.add(n2);

                for (Integer n: numbers) {
                    int n3 = n*n1;
                    numbers2.add(n3);
                }
            }
        }

        numbers.addAll(numbers2);

        return new ArrayList<Integer>(numbers);
    }

    /**
     * Based on the following fuzzy question @ StackOverflow
     * http://stackoverflow.com/questions/7571934/printing-numbers-of-the-form-2i-5j-in-increasing-order
     * 
     * 
     * Result:
     * 1 2 4 5 8 10 16 20 25 32 40 64 80 100 125 128 200 256 400 625 1000 2000 10000 
     */
    public static void main(String[] args) {
        List<Integer> numbers = findIncreasingNumbers(5);

        for (Integer i: numbers) {
            System.out.print(i + " ");
        }
    }
}
于 2011-09-27T16:35:43.757 回答
0

我相信现在每个人都可能已经得到了答案，但只是想为这个解决方案指明方向。

这是来自http://www.careercup.com/question?id=16378662的 Ctrl C + Ctrl V 

 void print(int N)
  {
     int arr[N];
     arr[0] = 1;
     int i = 0, j = 0, k = 1;
     int numJ, numI;
     int num;
       for(int count = 1; count < N; )
        {
          numI = arr[i] * 2;
          numJ = arr[j] * 5;

            if(numI < numJ)
             {
               num = numI;
               i++;
             }

           else
            {
              num = numJ;
              j++;
            }

            if(num > arr[k-1])
            {
             arr[k] = num;
             k++;
             count++;
            }

       }

     for(int counter = 0; counter < N; counter++)
     {
      printf("%d ", arr[counter]);
     }
}
于 2013-03-20T19:23:19.710 回答
0

向我提出的问题是返回一组无限的解决方案。我考虑过使用树木，但考虑到 i 和 j 的值是无限的，我觉得在确定何时收获和修剪树木方面存在问题。我意识到可以使用筛算法。从零开始，确定每个正整数是否具有 i 和 j 的值。这通过将 answer = (2^i)*(2^j) 转而求解 i 来促进。这给了我 i = log2 (answer/ (5^j))。这是代码：

class Program
{
static void Main(string[] args)
{
    var startTime = DateTime.Now;

    int potential = 0;

    do
    {
        if (ExistsIandJ(potential))
            Console.WriteLine("{0}", potential);
            potential++;
    } while (potential < 100000);

    Console.WriteLine("Took {0} seconds", DateTime.Now.Subtract(startTime).TotalSeconds);

}

private static bool ExistsIandJ(int potential)
{
    // potential = (2^i)*(5^j)
    // 1 = (2^i)*(5^j)/potential
    // 1/(2^1) = (5^j)/potential or (2^i) = potential / (5^j)
    // i = log2 (potential / (5^j))

    for (var j = 0; Math.Pow(5,j) <= potential; j++)
    {
        var i = Math.Log(potential / Math.Pow(5, j), 2);
        if (i == Math.Truncate(i))
            return true;
    }
    return false;
}
}
于 2015-07-30T01:30:34.020 回答