java - 算法简单但内存不足

Question

Problem

A sequence of positive rational numbers is defined as follows:

An infinite full binary tree labeled by positive rational numbers is defined by:

• The label of the root is 1/1
• The left child of label p/q is p/(p+q)
• The right child of label p/q is (p+q)/q

The top of the tree is shown in the following figure:

The sequence is defined by doing a level order (breadth first) traversal of the tree (indicated by the light dashed line). So that:

F(1)=1/1,F(2)=1/2,F(3)=2/1,F(4)=1/3,F(5)=3/2,F(6)=2/3,…

Write a program which finds the value of n for which F(n) is p/q for inputs p and q.

Input

The first line of input contains a single integer P, (1≤P≤1000), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input. It contains the data set number, K, a single space, the numerator, p, a forward slash (/) and the denominator, q, of the desired fraction.

Output

For each data set there is a single line of output. It contains the data set number, K, followed by a single space which is then followed by the value of n for which F(n) is p/q. Inputs will be chosen so n will fit in a 32-bit integer.

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();
}

Answer 1

让我们考虑节点 n = a/b。如果 n 是其父节点的左子节点，则 n = p/(p+q)，其中父节点为 p/q。 IE。

p = a, 
b = p + q 

p = a, 
q = b - a

如果 n 是其父节点的右 child ，则 n = (p+q)/q:

a = p + q
b = q

p = a - b =
q = b

因此，例如给定 3/5，它是左 child 还是右 child ？如果它是左 child ，那么它的 parent 将是 3/(5-3) = 3/2。对于正确的 child ，我们将有 (3-5)/5 = -2/5。由于这不是正数，显然 n 是左 child 。

因此，归纳:

给定一个有理数 n，我们可以找到到根的路径如下:

ArrayList lefts = new 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，等等。

我们只剩下最后一部分了，即将节点添加到我们拥有的最后一个节点的左侧，对应于输入有理数的节点加一。左边有几个节点？如果您尝试将每条向左的弧标记为 0，将每条向右的弧标记为 1，您会注意到该路径以二进制表示最后一层中的节点数。例如，3/5 是 3/2 的左 child 。该数组将填充为 false、true、false。在二进制中，010。最终结果是 2^0 + 2^1 + 2^2 + 010 + 1 = 1 + 2 + 4 + 2 + 1 = 10

最后，注意 sum(2^i) 是 2^(i+1) - 1。所以，我们终于可以编写第二部分的代码了:

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;

接受输入 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])));
  }
}