Оптимальное решение вопроса дерева процессов

Question

Дерево процессов гипотетической цепочки процессов представлено в виде древовидной структуры. Каждый процесс порождает количество процессов, равное количеству его процессов, т.е. процесс 3 имеет 3 дочерних элемента. Процессы названы в порядке уровней, root равным 1, его дочерние / дочерние элементы названы от 2 и так далее. Каков номер процесса родительского процесса данного процесса?

     1
      \
       2
      / \
     3   4
     |   |
 +-+-+   +-+--+-+
 | | |   | |  | | 
 5 6 7   8 9 10 11

Итак, для 6 родительский процесс будет 3.

Я написал функцию в O (n), которая просто соберите дерево до n и найдите его родителя, но я считаю, что есть более эффективный способ решения этой проблемы.

Answer 1

• Хорошо, это разрешимо с помощью небольшой математической формулы.

• Если вы внимательно наблюдаете, для любого данного узла его наибольшее дочернее значение равно parent_node * (parent_node + 1) / 2 + 1.

• Итак, допустим, вы хотите найти родителя процесса 9.

• Нам нужно будет решить уравнение parent_node * (parent_node + 1) / 2 = 9. Здесь parent_node - неизвестное значение.

• Таким образом, мы можем преобразовать уравнение как parent_node ² + parent_node - 18 = 0, Теперь мы можем найти корни с помощью квадратичной c формулы .

• Мы находим, что положительное значение root равно 3.772, принимая только целочисленное значение, это 3.

• Теперь есть 2 scenar ios:
  • Если текущее значение узла (здесь 9) больше parent_node * (parent_node + 1) / 2 + 1, то ответом будет положительное значение root формулы + 1, поэтому оно равно 3 + 1 = 4.
  • Если текущее значение узла (здесь 9) не выше , чем parent_node * (parent_node + 1) / 2 + 1, то ответом является положительное целое число root само значение.

Answer 2

public class OptimalSolution {

    public static void main(String[] args) {

        int targetNumber = 8;//number represent which one parent required.
        int start_number=1;
        int curentlevel = 0 ,intialNum = 0;
        boolean flag =true;
        for (int i = 0; i < targetNumber; i++) {
            while (intialNum >= 0) {
                if(start_number==targetNumber) {
                    System.out.println(start_number+"==="+curentlevel);
                    flag=false;
                    break;
                }
                start_number++;
                intialNum--;
            }
            if(flag==false)
                break;
            curentlevel ++;
            intialNum =i;
        }
    } 
}