Мне поручено закодировать решение следующей проблемы:
Учитывая целое число X и целое число Y, где X - конечная сумма, а Y - количество раз, которое мне разрешено удваивать мой текущий сумма в моей цепочке добавления чисел. Мы начинаем с 1 и добавляем к нашей сумме либо
1) добавляя 1 к нашей текущей сумме, либо
2) удваивая нашу текущую сумму.
Функция должна возвращать наименьшее количество раз, которое мы добавляем к нашей сумме, чтобы достичь X.
Например,
, если X = 10 и Y = 2, самый короткий способ прибавить к 10 будет:
1,2,4,5,10 = 4 шага сложения с 2 шагами удвоения (из 2-> 4 и 5-> 10, 1-> 2 не считается как удвоение)
Я ломал голову над решением, и я рассматриваю возможность реализации подхода бинарного дерева к этой проблеме. Головным узлом будет 2, поскольку мы всегда добавляем от 1 до 2. Левый узел добавляет 1, а правый узел удваивается. Это будет выглядеть примерно так:
2
3 4
4 6 5 8
5 8 7 12 6 10 9 16
И как только оно достигнет 10, оно прекратится и ответ будет num_of_traversals + 1. Конечно, он должен был бы проверить, что число раз, когда он выбрал правильный узел, было меньше или равно K. Если больше K, то он продолжает проходить до следующего вхождения 10.
Я никогда ранее кодировался с двоичными деревьями, поэтому я не уверен, как бы я go реализовал этот псевдокод. Я заинтересован в некоторой помощи для начала работы с этой проблемой. Спасибо!
Редактировать: Я решил эту проблему с помощью недвоичного дерева. Но мне все еще очень любопытно, как можно было бы сделать это с помощью бинарного дерева или если это даже желательно.