Добрый день, такая задача возникла:
Дана геометрическая прогрессия(последовательность) с основанием 2, и первым членом 1:
1 2 4 8 16 32 64 128 ...
входные данные дается одно число, например: 74
это число состоит из членов последовательности, 2 + 8 + 64
и нужно найти из каких членов состоит входное число.
Хотел бы узнать если какие то формулы или хорошие алгоритмы? или жадный перебор всевозможных вариантов?
членов последовательности может быть до 30, думаю слишком затратно будет перебор делать..
Просто берешь максимально возможный вариант, вычитаешь из N, и опять ищешь максимально возможный вариант. (Должно работать).
Можно перевести в двоичную систему счисления и посмотреть на каких позициях 1 стоят
Так, на этом моменте подробней пожалуйста.
что именно в двоичную переводить? и почему там еденицы должны получиться?
Я что-то подобное читал про алгоритм записи прав доступа в линусе.
74 в двоичной системе — 1 0 0 1 0 1 0 . Если нумеровать разряды справа налево, начиная с нуля, то единичка в каком-то разряде означает, что 2^Разряд присутствует в нужной вам сумме. Допустим, тут единички в разрядах 6, 3 и 1 — а это 64 + 8 + 2.