Сегодня придумал задачу. Оформлю типа как сугубый программист
Есть массив данных
some_data d[N];
Я хочу переоформить это в K-нарное дерево.
union node
{
some_data d;
node* next[K];
};
Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.
P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.
Или я ничего не понял, или нодов будет N, т.к. в каждом ноде -- одна some_data.
Здравствуйте, Pushkin, Вы писали:
UgN>>Или я ничего не понял, или нодов будет N, т.к. в каждом ноде -- одна some_data.
P>Да нет, оно же union — либо листья, либо развилки.
Болван!
Грохни ветку, плз, я не вынесу этого позора!
<>
P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.
Очевидно, что в дереве должно быть достаточно мест для размещения данных.
То есть, будет N узлов
Или есть какие-то особые ограничения на структуру дерева?
— сбалансированное
— узел либо лист, либо полностью заполнен
P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.
Модификация известного решения для K=2.
Предположим, что существует некая спортивная игра, в которой могут учавствовать до K участников, причем побеждает только один. Тогда любое K-нарное дерево взаимно однозначно соответсвует расписанию турнира проводимого по олимпийской системе, если в турнире учавствуют N участников. В каждой игре у нас выбывает максимум K-1 участник. Следовательно оценка снизу, с учетом того, что в финале остается один победитель:
ceil((double)(N-1)/(K-1))
Теперь докажем, что она достижима. Для этого докажем, что можно организовать турнир, в котором всех играх, кроме последней учавствует K участников.
В каждом туре организуем игры так:
Набираем максимальное возможное число "полных" игр. Оставшихся участников автоматически переводим в следующий тур. И так далее до финала.
Здравствуйте, MichaelP, Вы писали:
MP>Модификация известного решения для K=2. MP>Предположим, что существует некая спортивная игра
Не выдавай! Я маскируюсь под программера
MP>ceil((double)(N-1)/(K-1))
Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ.
Да и некошерно как-то к плавающей арифметике переходить, когда все числа целые
Здравствуйте, Pushkin, Вы писали:
MP>>ceil((double)(N-1)/(K-1))
P>Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ.
Или я вопрос не понял — тогда поясни где я не прав, или ты ответ — готов дать пояснения.
P>Да и некошерно как-то к плавающей арифметике переходить, когда все числа целые
Я так написал, чтобы формула была попрозначнее. Могу написать так:
Здравствуйте, MichaelP, Вы писали:
P>>Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ. MP>Или я вопрос не понял — тогда поясни где я не прав, или ты ответ — готов дать пояснения. MP>Я так написал, чтобы формула была попрозначнее. Могу написать так: MP>
MP>(N+K-3)/(K-1)
MP>
Ну хорошо, хорошо, засчитывается.
Я просто имел в виду, что ты N забыл добавить — надо же где-то сами данные хранить!
Итого
Здравствуйте, Pushkin, Вы писали:
P>Ну хорошо, хорошо, засчитывается. P>Я просто имел в виду, что ты N забыл добавить — надо же где-то сами данные хранить!
В пятницу вечером и не то бывает ! Как стал о дереве думать, так и пошли узлы и листья... Совсем забыл, что ты "node" общий объект назвал .
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, Pushkin, Вы писали:
UgN> P>>
P>>N+(N+K-3)/(K-1)
P>>
P>>Или, если кому милее, так
P>>
P>>(N*K+K-3)/(K-1)
P>>
UgN>А как это выводится? UgN>В частности откуда -3?
1) ceil (X/Y) для целых X и Y переписывается всегда как (X+Y-1)/Y (это думаю все знают, но можно проверит на примерах)
2) в целых числах прекрасно работает обычное справило сложения дробей X/Y+Z = (X+Z*Y)/Y
Поэтому взяв исходную формулу имеем
N + ceil(1.0*(N-1)/(K-1)) =
N + ((N-1)+(K-1)-1)/(K-1) =
N + (N+K-3)/(K-1) =
(N*(K-1)+N+K-3)/(K-1) = (N*K+K-3)/(K-1)
Прости за такое количество математики
Что касается вывода основной формулы, то вот моё изложение, може оно будет понятней:
Каждое разветвление заменяет K узлов на 1, т.е. убивает K-1 узлов
Было N узлов, остался один верхний — надо убить N-1.
Причём гарантированно, поэтому круглим вверх.
Итого (N-1)/(K-1) с округлением вверх.