На уроке информатики сегодня обсуждалась тема "Двоичные деревья". Пока шли уроки, Петя нарисовал в тетради лес из нескольких различных полных двоичных деревьев. Вечером он подсчитал количество узлов у всех этих деревьев. Их оказалось 2947.

Какое наименьшее количество деревьев мог нарисовать Петя?

В каждом дереве 2^n узлов. Поскольку надо найти наименьшее количество деревьев, надо разбить число 2947 на слагаемые, которые представляют собой степени двойки, причем каждое новое отделяемое слагаемое должно быть максимальной степенью двойки, "влезающей" в остаток. Количество слагаемых будет являться ответом.

2947 = 2048 + 899 = 2048 + 512 + 387 = 2048 + 512 + 256 + 131 = 2048 + 512 + 256 + 128 + 3 = 2048 + 512 + 256 + 128 + 2 + 1

Ответ: 6.

Иными словами, переводим число 2947 в двоичную систему и считаем количество единиц в записи числа.