Мне нужна подсказка, чтобы начать эту загадку программирования

Ответ 1

Это ваше дерево

           (0)
     -------------      
     |           | 
    (2)         (1)
 ---------    -------   
 |       |    |     |
[3p]     ..   ..   (3)
                  ------
                  |     |
                 ...    ..

Ваша логика должна создавать это дерево в памяти с каждым node, содержащим следующую структуру данных.

BalanceIdx: Integer;    //The balance index number if any. -1 indicates none
InitialPounds: Integer; //Initial weight in the node 
AddedPounds: Integer;   //The weight you added when processing. Default is 0
TotalWeight: Integer;   //**Total weight of a node including all its children. This is also our indication that a particular branch is already traversed. Default is -1

Мы говорим о рекурсивной функции, которая в основном знает, что она имеет только два пути или никакой путь, чтобы следовать, когда в любом node дерева. Каждая рекурсия считается сидящей на пластине баланса.

Вот логика.

• Начните с корня и пройдите, пока не найдете node, у которого нет пути для перехода.

• Обновите его TotalWeight с помощью InitialPounds.

• Теперь посмотрите, есть ли у node другого брата TotalWeight. Если НЕТ, установите там корень своей рекурсивной функции и выполните.

• Если ДА, вычислите разницу и обновите AddedPounds того, где вы сидите. Теперь перейдите к родительскому объекту и обновите его TotalWeight. (не забудьте добавить 10p для баланса (ов)). Затем перейдите к великому родителю и повторите 3.

После того, как рекурсивная функция завершит перемещение всего дерева, у вас есть AddedPounds, записанный в каждом node. Используйте другую рекурсивную функцию для построения вывода.

Этот ответ предназначен для стартера, о котором вы просили.

Ответ 2

SPOILER ALERT: включено полное решение (кроме чтения ввода)

Этот вопрос довольно старый и выглядел забавным, поэтому я просто пошел и решил его (на C, а не на PHP, как это отмечено), после нескольких намеков открытия. Я использовал подробные имена переменных и прокомментировал, поэтому он должен работать как псевдокод. Я собирался написать C-подобный псевдокод, но никогда не ударил ничего, что стоило подвести итог.

Основным осложнением этой проблемы является то, что вы не можете использовать деревья двоичные, поскольку на одном балансе может быть несколько других балансов на одной или обеих своих чашках. Вероятно, самый простой способ здесь - это ссылки на списки узлов, где каждый node имеет дочерние и правые дочерние элементы, а также указатель брата и сестры. Чтобы получить все остатки, сидящие на левой кастрюле баланса, перейдите по связанному списку указателей на сестры, начиная с левого дочернего элемента node для баланса, на который вы смотрите.

Поскольку формат ввода присваивает номера всем остаткам, проще всего использовать эти индексы в массиве структур. Если вы можете предположить, что имеется баланс менее 2 ^ 31, вы можете сэкономить память, используя 32-битные int вместо 64-битных указателей. (Отрицательные индексы являются дозорными для пустых, как NULL-указатель в реализациях дерева/списка на основе указателей)

struct balance {
    // weights sitting directly on the pans of this balance
    float weight_left, weight_right;  // or unsigned int; the question only said the balance-count was an int.  I assumed the balance-IDs were int, too

    // optionally: float adjustment;  // For recording our changes.  negative or positive for adding to left or right balance.

    // references to other balances: negative means empty-list, otherwise index into an array.
    int next;           // linked-list of sibling balances on the same pan of a parent
    int left, right;    // list-heads for balances on the left and right pan
};

Когда они говорят, что вы должны добавить вес к "самому низкому" балансу, я предполагаю, что они означают, что корень внизу. Это не дерево подвесных весов, отстраненных от чего-то.

Вам разрешено добавлять весы в балансы, которые уже имеют балансы. Таким образом, нет никаких осложнений по поводу добавления веса в пустые кастрюли у листьев дерева. (Это потребовало бы разделения веса таким образом, чтобы каждый поддерево сбалансировано индивидуально).

Итак, это выглядит довольно просто для рекурсивного решения.

• Поддерево может быть сбалансировано самостоятельно, без какой-либо информации о каких-либо других балансах.
• Не имеет значения, какая комбинация весов и других весов составляет нагрузку на левую и правую кастрюли. Вам просто нужны эти два итога. Баланс, добавляя вес непосредственно к более легкой кастрюле.
• Сбалансируйте баланс после балансировки всех его поддеревьев. Вы можете суммировать веса поддеревьев, балансируя их.

Итак, алгоритм:

static const float BALANCE_WEIGHT = 10.0f;

// return total weight of the balance and everything on it, including the 10.0f that this balance weighs
// modify the .weight_left or .weight_right of every node that needs it, in the subtrees of this node
float balance(struct balance storage[], int current)
{
    float lweight = 0, rweight = 0;

    // C++ can make this more readable:
    // struct balance &cur = storage[current];

    // loop over all the left and then right children, totalling them up
    // depth-first search, since we recurse/descend before doing anything else with the current
    for (int i = storage[current].left ; i >= 0 ; i = storage[i].next )
        lweight += balance(storage, i);

    for (int i = storage[current].right; i >= 0 ; i = storage[i].next )
        rweight += balance(storage, i);


    lweight += storage[current].weight_left;
    rweight += storage[current].weight_right;

    float correction = fabsf(rweight - lweight);

    // modify the data structure in-place with the correction.
    // TODO: print, or add to some other data structure to record the changes
    if (lweight < rweight) {
        storage[current].weight_left += correction;
    } else {
        storage[current].weight_right += correction;
    }

    return BALANCE_WEIGHT + rweight + lweight + correction;
}

Чтобы записать, какие изменения вы внесли, либо используйте дополнительное поле в структуре данных, либо уничтожайте исходные данные, когда вы возвращаетесь с первой балансировки глубины (поскольку она больше не нужна). например магазин .weight_left = correction; .weight_right = 0;, если левый лишний вес добавлен, в противном случае сделайте обратное.

Эта реализация будет использовать меньшее пространство стека, если бы существовал глобальный массив, а не каждый рекурсивный вызов, чтобы передать указатель storage. Это дополнительное значение, которое должно быть сохранено/восстановлено в регистре-вызове ABI и непосредственно занимает дополнительное пространство в стеке-вызове ABI, таком как 32-битный x86.

Все вычисления, связанные с текущими node weight_left и weight_right, происходят в конце, вместо того, чтобы читать их в начале и затем перечитывать их для + = read-modify-write. Компилятор не смог выполнить эту оптимизацию, поскольку он не может знать, что структура данных не имеет циклов, в результате чего balance(subtree) изменит один из этих весов.

По какой-то причине x86 gcc 5.2 -O3 компилирует это в действительно огромный код. Это более разумно с -O2. clang работает с -O3, но пропускает некоторые оптимизации.

Ответ 3

Этот ответ также даст рабочий код, на этот раз в PHP.

Некоторые важные наблюдения:

• Несмотря на то, что данный пример никогда не ставит более одного баланса по обе стороны от любого из балансов, нескольким остаткам разрешено сидеть на одной стороне баланса;
• Нет гарантии, что есть только один баланс корня, в комнате может быть несколько отдельных стоек;
• Формат ввода позволяет одному балансу покоиться на нескольких других балансах или многократно отдыхать на одной стороне баланса или даже опираться на себя. Предполагается, что такой и другой циклический ввод будет считаться недействительным;
• Условие "выбрать способ, который добавляет дополнительный вес на самые низкие балансы", равносильно тому, что "вам разрешено добавлять вес только с одной стороны каждого баланса, ни один из них"

Определены четыре функции:

• parseInput принимает входную строку, возвращает массив объектов, представляющих данные логическим способом;
• addWeights принимает индекс (ID) баланса и вычисляет, на какой стороне его вес должен быть добавлен, и сохраняет этот вес в новом свойстве. В расчет используется рекурсия для расчета веса всех остатков, расположенных по обе стороны этого баланса, после того как они были сбалансированы с добавленными весами. Он выдает ошибку, если обнаружены циклы, а также предотвращает бесконечную рекурсию;
• баланс посещает все остатки, и если они еще не сбалансированы, выполняется вызов вышеприведенных addWeights. Это будет охватывать несколько конфигураций корневого баланса;
• outputString принимает завершенную структуру и возвращает строку в ожидаемом формате вывода.

Структура данных представляет собой массив пар объектов. Данные примера будут преобразованы в следующее: с добавлением добавленного свойства во время вычислений:

[
  [
    { 'weight' => 0, 'balances' => [1], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' => [2], 'addedWeight' => 14 }
  ], [
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' => 10 },
    { 'weight' => 0, 'balances' => [3], 'addedWeight' =>  0 }
  ], [
    { 'weight' => 3, 'balances' =>  [], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  3 }
  ], [
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  0 },
    { 'weight' => 0, 'balances' =>  [], 'addedWeight' =>  0 }
  ]
]

Комментарии в коде должны объяснять наиболее важные части:

function parseInput($input) {
    $lines = preg_split('/(\r\n|\n)/', $input, null, PREG_SPLIT_NO_EMPTY);
    $count = (int) array_shift($lines); // we don't need this item
    $balances = array();
    $side = array();
    foreach($lines as $line) {
        // get the numbers from one line in an array of numbers
        $args = array_map('intval', explode(' ', $line));
        $obj = new stdClass();
        // first number represents the weight
        $obj->weight = array_shift($args);
        // all other numbers represent IDs of balances
        $obj->balances = $args;
        // collect this as a side, next iteration will fill other side
        $side[] = $obj;
        if (count($side) == 2) {
            // after each two lines, add the two objects to main array
            $balances[] = $side;
            $side = array();
        }
    }
    return $balances;
}

function addWeights(&$balances, $id) {
    if ($id == -1) {
        // There is no balance here: return 0 weight
        return 0;
    }
    // Check that structure is not cyclic:
    if (isset($balances[$id][0]->addedWeight)) {
        throw new Exception("Invalid balance structure: #$id re-encountered");;
    }
    $total = 10; // weight of balance itself
    $added = 0;
    foreach($balances[$id] as &$side) {
        // get the direct weight put in the balance: 
        $weight = $side->weight;
        // add to it the total weight of any balances on this side,
        // by using recursion
        foreach($side->balances as $balanceId) {
            $weight += addWeights($balances, $balanceId);
        }
        // calculate difference in left/right total weight
        $added = $weight - $added;
        $total += $weight;
        // create new property with result
        $side->addedWeight = 0;
    }
    // set either left or right added weight:
    $balances[$id][$added > 0 ? 0 : 1]->addedWeight = abs($added);
    $total += abs($added);
    return $total;
}

function balance(&$balances) {
    // If the only root balance was at index 0, we could just 
    // call addWeights($balances, 0), but it might be elsewhere
    // and there might even be multiple roots:
    foreach($balances as $index => $balance) {
        if (!isset($balance[0]->addedWeight)) {
            addWeights($balances, $index);
        }
    }
}

function outputString(&$balances) {
    $output = '';
    foreach($balances as $index => $balance) {
        $output .= "$index: {$balance[0]->addedWeight} {$balance[1]->addedWeight}\n";
    }
    return $output;
}

Вот как он используется:

// test data
$input =
"4
0 1
0 2
0
0 3
3
0
0
0";
// 1. transform input into structure
$balances = parseInput($input);
// 2. main algorithm
balance($balances);
// 3. output the result in desired format
echo outputString($balances);

Выход:

0: 0 14
1: 10 0
2: 0 3
3: 0 0

Ответ 4

Обзор

Задача требует, чтобы древовидная структура представляла балансы, которые покоятся на балансах. Чтобы решить эту проблему, вы должны иметь возможность: -

• Найдите все остатки. Это требует некоторой формы рекурсивной функции, где вы можете посетить левых и правых детей.

• Подсчет весов. Из данного баланса найдите вес с левой стороны и с правой стороны.

• Добавление весов. Учитывая, что в вопросе говорится, что сначала нужно добавить весы к самым низким остаткам, то вы повторно просматриваете деревья для баланса, у которого нет детей, или у детей, которые уже были сбалансированы.