Рекурсивный метод расчета веса, который человек поддерживает в человеческой пирамиде

Question

Я бился головой о стену последние пару дней, пытаясь выяснить, как правильно настроить этот рекурсивный метод. Я нашел еще один пост о переполнении стека, который указал мне правильное направление, но не могу понять, как его sh завершить.

В человеческой пирамиде вес распределяется между разными людьми неравномерно в пирамиде. Например, у человека А нет веса. Если мы предположим, что каждый человек в нашей пирамиде весит 200 фунтов, тогда человек B и человек C несут половину веса человека A (100 фунтов каждый). Человек E непосредственно поддерживает половину веса человека B (100 фунтов) и половину веса человека E (100 фунтов), поэтому он поддерживает не менее 200 фунтов. Вдобавок она несет половину этого человека B и C несет, поэтому дополнительные 100 фунтов.

Полное описание программы здесь.

Это то, что у меня так far:

public int weightOn(int row, int column) {
    // Base cases
    if (row <= 0) {
        return 0;
    } else if (column < 0 || column > row) {
        return 0;
    }

    return (200 + (weightOn(row - 1, column - 1) + weightOn(row - 1, column))) / 2;
}

Программа работает для первых 2 рядов пирамиды и всех сторонних людей, таких как: weightOn (0, 0) = 0, weightOn (1, 0) = 100, weightOn (2, 0) = 150, но когда я запускаю weightOn (2, 1), я получаю 200, когда должно быть 300, или weightOn (3, 1) возвращает 275, когда должно быть 425.

Answer 1

A -> B C -> EFG -> ... и т. Д. Каждый уровень имеет переносимый вес (n), несет половину этого числа (n / 2) + то, что этот уровень уже нес, поэтому каждый элемент несет вес ((n / 2) + то, что уже перенесено / 2), [например, на втором уровне у нас есть B и C с общим количеством 400, они несут 400 + 0/2 = 200, поэтому каждый элемент несет 200/2 = 100] [еще один пример для EFG: n = 200 * 3, и этот уровень несет в сумме 600, поэтому, если мы воспользуемся нашей формулой, мы обнаружим, что вес равен 450, поэтому каждый элемент имеет вес 150 ]

Answer 2

То же, что и ваша идея, но с некоторыми изменениями c ..

public static int weightOn(int row, int column) {
    // Base cases
    if (column < 0 || column > row)
        return 0;

    if (row == 0)
        return 200;

    int w1 = weightOn(row - 1, column - 1);
    int w2 = weightOn(row - 1, column);
    System.out.println((row - 1) + " " + (column - 1) + " " + w1);
    System.out.println((row - 1) + " " + (column) + " " + w2);

    return 200 + (w1 + w2) / 2;
}

Теперь вы можете вызвать такую ​​функцию, чтобы получить ответ

public static void main(String[] args) throws IOException {
    System.out.println(weightOn(4, 2) - 200);
}

Я только что сделал basi c testing ..

Но идея в том, что когда вызывается метод a, вам нужно вернуть его вес + часть веса, который он получает от своего родителя (parentwt) / 2; В любой момент вес текущего удерживаемого узла равен parentwt / 2; Итак, я вычел 200 в операторе sysout.

Answer 3

Я бы использовал другой подход. Просто определите класс, который представляет узел на вашей диаграмме. Каждый из этого узла может иметь (или не иметь в зависимости от того, кто этот узел представляет) ссылку на другие узлы (минимум 0, максимум 2, как в бинарном графе). Итак, теперь определить вашу функцию weightOn довольно просто. Вес узла равен

public int weightOn() {
    return 200 + leftNodeParent.weightOn()/2 + rightNodeParent.weightOn()/2 ;
}

В основном вы получите рекурсивный вызов метода weightOn ().

EDIT: это должно сработать

public static void main(String []args){
    Node a = new Node(null, null);
    Node b = new Node(null, a);
    Node c = new Node(a, null);
    System.out.println(c.weightOn());


 }

public class Node {
    Node leftParent;
    Node rightParent;
    public Node(Node left, Node right){
        this.leftParent = left;
        this.rightParent = right;
    }
    public int weightOn() {
        int leftWeight = leftParent != null ? leftParent.weightOn()/2 : 0;
        int rightWeight = rightParent != null ? rightParent.weightOn()/2 : 0;
        return (200 + leftWeight + rightWeight) ;
    }
}