java - 简单的算法，但内存不足

问题正有理数序列定义如下：一个用正有理数标记的无限完全二叉树是定义人：根的标签是1/1标签p/q的左子项是p/（p+q）标签p/q的右子项是（p+q）/q树梢如下图所示：序列是通过执行水平顺序（宽度优先）来定义的。树的遍历（用浅虚线表示）。以便：f（1）=1/1，f（2）=1/2，f（3）=2/1，f（4）=1/3，f（5）=3/2，f（6）=2/3，…编写一个程序，找出f（n）为p/q的n的值输入p和q。输入输入的第一行包含一个整数P（1≤P≤1000），其中是后面的数据集数。每个数据集应该是同样独立地处理。每个数据集由单行输入。它包含数据集编号k空格，分子，p，正斜杠（/）和分母，q，所需分数的。输出对于每个数据集都有一行输出。它包含数据集编号，k，后跟一个空格根据n的值，其中f（n）是p/q。输入将被选择为n将适合32位整数。Source to question我的方法我创建了堆并计划对其进行迭代，直到找到有问题的元素，但是我的内存不足，所以我很确定我应该在不创建堆的情况下完成它？代码public ARationalSequenceTwo() { Kattio io = new Kattio(System.in, System.out); StringBuilder sb = new StringBuilder(10000); int iter = io.getInt(); // create heap int parent; Node[] heap = new Node[Integer.MAX_VALUE]; int counter = 1; heap[0] = new Node(1, 1); while (counter < Integer.MAX_VALUE) { parent = (counter - 1) / 2; // left node heap[counter++] = new Node(heap[parent].numerator, heap[parent].numerator + heap[parent].denominator); // right node heap[counter++] = new Node(heap[parent].numerator + heap[parent].denominator, heap[parent].denominator); } // find Node int dataSet; String word; int numerator; int denominator; for (int i = 0; i < iter; i++) { dataSet = io.getInt(); word = io.getWord(); numerator = Integer.parseInt(word.split("/")[0]); denominator = Integer.parseInt(word.split("/")[1]); for (int j = 0; j < Integer.MAX_VALUE; j++) { Node node = heap[j]; if (node.numerator == numerator && node.denominator == denominator) { sb.append(dataSet).append(" ").append(j).append("\n"); } } } System.out.println(sb); io.close();} 最佳答案 让我们考虑节点n=a/b。如果n是其父节点的左子节点，那么n=p/（p+q），其中父节点是p/q，即。p = a,b = p + qp = a,q = b - a如果n是其父项的右子项，则n=（p+q）/q：a = p + qb = qp = a - b =q = b那么，以3/5为例，它是左孩子还是右孩子如果是左子，那么它的父代是3/（5-3）=3/2对于正确的孩子，我们会有（3-5）/5=-2/5因为这不是肯定的，显然n是一个留守儿童。所以，概括一下：给定一个有理数n，我们可以找到根的路径如下：ArrayList lefts=新的ArrayList（第页）；while (nNum != nDen) { if (nNum < nDen) { //it's a left child nDen = nDen - nNum; lefts.add(true); } else { nNum = nNum - nDen; lefts.add(false); }}现在数组中已经有了路径，我们如何在最终结果中转换它？让我们观察一下如果给定的值是1/1，那么数组是空的，我们应该返回1每次我们从n级转到n+1级时，都会在结果中加上2^n例如，从级别0到级别1，我们添加1（根）从级别1到级别2，我们将级别1的所有两个节点（即2）相加，以此类推。剩下的是最后一个部分，它将节点添加到最后一个节点的左边，这个节点对应于输入rational，再加上一个。左边有几个节点？如果尝试将每个向左的弧标记为0，将每个向右的弧标记为1，则会注意到路径以二进制形式拼写上一级的节点数。例如，3/5是3/2的左子代数组将填充false、true、false二进制，010。最终结果是2^0+2^1+2^2+010+1=1+2+4+2+1=10最后，注意和（2^i）是2^（i+1）-1。因此，我们终于可以为第二部分编写代码：int s = (1 << lefts.size()) - 1) // 2^(i+1) - 1int k = 0for (int i = lefts.size() - 1; i >= 0; i---) { if (lefts.get(i)) { k += 1 << i; }}return s + k + 1;接收输入num和den的完整程序：import java.util.ArrayList;public class Z { public static int func(int num, int den) { ArrayList<Boolean> lefts = new ArrayList<>(); while (num != den) { if (num < den) { //it's a left child den = den - num; lefts.add(true); } else { num = num - den; lefts.add(false); } } int s = (1 << lefts.size()) - 1; // 2^(i+1) - 1 int k = 0; for (int i = lefts.size() - 1; i >= 0; i--) { if (!lefts.get(i)) { k += 1 << i; } } return s + k + 1; } public static void main(String[] args) { System.out.println(func(Integer.parseInt(args[0]), Integer.parseInt(args[1]))); }}关于java - 简单的算法，但内存不足，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41007977/