Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 13:05
Оценка: -1
Сегодня придумал задачу. Оформлю типа как сугубый программист

Есть массив данных
some_data d[N];


Я хочу переоформить это в K-нарное дерево.

union node
{
  some_data d;
  node* next[K];
};


Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.
Re: Листья и развилки
От: UgN  
Дата: 21.03.03 13:10
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Есть массив данных

P>
P>some_data d[N];
P>


P>Я хочу переоформить это в K-нарное дерево.


P>
P>union node
P>{
P>  some_data d;
P>  node* next[K];
P>};
P>


P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.


Или я ничего не понял, или нодов будет N, т.к. в каждом ноде -- одна some_data.

N+K-K.
Re[2]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 13:12
Оценка:
Здравствуйте, UgN, Вы писали:

P>>
P>>union node
P>>{
P>>  some_data d;
P>>  node* next[K];
P>>};
P>>


UgN>Или я ничего не понял, или нодов будет N, т.к. в каждом ноде -- одна some_data.


Да нет, оно же union либо листья, либо развилки.
Re[3]: Листья и развилки
От: UgN  
Дата: 21.03.03 13:13
Оценка:
Здравствуйте, Pushkin, Вы писали:

UgN>>Или я ничего не понял, или нодов будет N, т.к. в каждом ноде -- одна some_data.


P>Да нет, оно же union либо листья, либо развилки.


Болван!
Грохни ветку, плз, я не вынесу этого позора!
Re[4]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 13:20
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>Грохни ветку, плз, я не вынесу этого позора!


Как мне недавно объяснили, "ууупс" — нормальный технический термин
Мне пожалуй стоило выделить слово union в исходнике, но так тоже неплохо вышло
Re: Листья и развилки
От: Кодт Россия  
Дата: 21.03.03 13:33
Оценка:
Здравствуйте, Pushkin, Вы писали:

<>

P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.


Очевидно, что в дереве должно быть достаточно мест для размещения данных.
То есть, будет N узлов

Или есть какие-то особые ограничения на структуру дерева?
— сбалансированное
— узел либо лист, либо полностью заполнен
Перекуём баги на фичи!
Re[2]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 13:39
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Очевидно, что в дереве должно быть достаточно мест для размещения данных.

К>То есть, будет N узлов

Минимум

К>Или есть какие-то особые ограничения на структуру дерева?

К>- сбалансированное
К>- узел либо лист, либо полностью заполнен

См. веткой выше — в узле либо развилка, либо лист (union )
Вопрос по сути в том, сколько нужно минимально развилок, чтобы отындексировать N листьев.
Re[2]: Листья и развилки
От: Кодт Россия  
Дата: 21.03.03 13:56
Оценка:
К>- узел либо лист, либо полностью заполнен

В этом случае у нас есть 3 вида узлов:
— лист с данными
— лист без данных (болванка)
— узел с K листьями

Очевидно, что при N = ...
N=1 -- T=1 (корень-лист)
N=2..K+1 -- T=1+K (корень + K листьев). Это неизбежно, что образуются болванки.

Теперь, чтобы добавить еще 1..K данных, мы создадим ровно K листьев. При этом неважно, какой лист мы превратим в узел.
И так далее:

N = 1 + K*m ---> T = 1+K*m = N

N = 1 + K*m + n (n=1..K-1) --> T = 1 + K*m + K = N + (K-n) = N + (K — (N-1)%K)

Объединяя формулы в одну,

T = N + (K-1 — (N+K-2)%K)
Перекуём баги на фичи!
Re: Листья и развилки
От: MichaelP  
Дата: 21.03.03 13:57
Оценка: 18 (1)
Здравствуйте, Pushkin, Вы писали:

P>Сегодня придумал задачу. Оформлю типа как сугубый программист


P>Есть массив данных

P>
P>some_data d[N];
P>


P>Я хочу переоформить это в K-нарное дерево.


P>
P>union node
P>{
P>  some_data d;
P>  node* next[K];
P>};
P>


P>Задача: написать выражение, содержащее N, K и знаки математических операций, которое будучи прокомпилированным на языке Си, даст минимально необходимое число объектов типа node.


Модификация известного решения для K=2.

Предположим, что существует некая спортивная игра, в которой могут учавствовать до K участников, причем побеждает только один. Тогда любое K-нарное дерево взаимно однозначно соответсвует расписанию турнира проводимого по олимпийской системе, если в турнире учавствуют N участников. В каждой игре у нас выбывает максимум K-1 участник. Следовательно оценка снизу, с учетом того, что в финале остается один победитель:
ceil((double)(N-1)/(K-1))

Теперь докажем, что она достижима. Для этого докажем, что можно организовать турнир, в котором всех играх, кроме последней учавствует K участников.
В каждом туре организуем игры так:
Набираем максимальное возможное число "полных" игр. Оставшихся участников автоматически переводим в следующий тур. И так далее до финала.
Re[3]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 14:05
Оценка:
Здравствуйте, Кодт, Вы писали:

К>N=2..K+1 -- T=1+K (корень + K листьев). Это неизбежно, что образуются болванки.


Почему? Что мешает иметь next[i]==NULL для всех i>i0 ?
Re[2]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 14:10
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Модификация известного решения для K=2.

MP>Предположим, что существует некая спортивная игра

Не выдавай! Я маскируюсь под программера

MP>ceil((double)(N-1)/(K-1))


Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ.
Да и некошерно как-то к плавающей арифметике переходить, когда все числа целые
Re: Листья и развилки
От: UgN  
Дата: 21.03.03 14:18
Оценка:
Здравствуйте, Pushkin, Вы писали:

( N / K + N + (( N % K ) ? 0 : 1 ) ) + 1

Так?
Хоть результаты такие же?
Re[3]: Листья и развилки
От: MichaelP  
Дата: 21.03.03 14:21
Оценка: 10 (1)
Здравствуйте, Pushkin, Вы писали:

MP>>ceil((double)(N-1)/(K-1))


P>Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ.

Или я вопрос не понял — тогда поясни где я не прав, или ты ответ — готов дать пояснения.

P>Да и некошерно как-то к плавающей арифметике переходить, когда все числа целые

Я так написал, чтобы формула была попрозначнее. Могу написать так:
(N+K-3)/(K-1)
Re[2]: Листья и развилки
От: UgN  
Дата: 21.03.03 14:25
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, Pushkin, Вы писали:


UgN>( N / K + N + (( N % K ) ? 0 : 1 ) ) + 1


или, что то же самое:

( N / K + N + ( 2 — ( N % K + N — 1 ) / N ) );
Re[4]: Листья и развилки
От: UgN  
Дата: 21.03.03 14:26
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>
MP>(N+K-3)/(K-1)
MP>


N = 6
K = 4

Результат 7/3 = 2;


Это как?
Re[4]: Листья и развилки
От: Pushkin Россия www.linkbit.com
Дата: 21.03.03 14:27
Оценка: 12 (1)
Здравствуйте, MichaelP, Вы писали:

P>>Ну всё замечательно, вот токо на поставленный вопрос это не есть верный ответ.

MP>Или я вопрос не понял — тогда поясни где я не прав, или ты ответ — готов дать пояснения.
MP>Я так написал, чтобы формула была попрозначнее. Могу написать так:
MP>
MP>(N+K-3)/(K-1)
MP>


Ну хорошо, хорошо, засчитывается.
Я просто имел в виду, что ты N забыл добавить — надо же где-то сами данные хранить!
Итого

N+(N+K-3)/(K-1)


Или, если кому милее, так

(N*K+K-3)/(K-1)
Re[3]: Объяснение
От: UgN  
Дата: 21.03.03 14:33
Оценка:
Здравствуйте, UgN, Вы писали:

Думаю, что почти как у Кодта. ( Правда, у него не все понял -- не люблю математику )

Есть листья с данными (N штук) и сколько-то узлов-коммутаторов (очевидно N / K), чтобы слинковать дерево.

Каждый раз, когда кол-во данных кратно K,
приходится добавлять узел-коммутатор

+ (( N % K ) ? 0 : 1 )

И не забудем про первый узел лист

+ 1
---------------------------------

==

( N / K + N + (( N % K ) ? 0 : 1 ) ) + 1

или, что то же самое:

( N / K + N + ( 2 — ( N % K + N — 1 ) / N ) );
Re[5]: Листья и развилки
От: MichaelP  
Дата: 21.03.03 14:36
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Ну хорошо, хорошо, засчитывается.

P>Я просто имел в виду, что ты N забыл добавить — надо же где-то сами данные хранить!

В пятницу вечером и не то бывает ! Как стал о дереве думать, так и пошли узлы и листья... Совсем забыл, что ты "node" общий объект назвал .
Re[5]: Листья и развилки
От: MichaelP  
Дата: 21.03.03 14:46
Оценка: +1
Здравствуйте, UgN, Вы писали:

UgN>N = 6

UgN>K = 4

UgN>Результат 7/3 = 2;


UgN>Это как?


А вот так:
_____|____ 
___|___ | | 
| | | | | | 
1 2 3 4 5 6
Re[6]: Листья и развилки
От: UgN  
Дата: 21.03.03 14:47
Оценка:
Здравствуйте, MichaelP, Вы писали:

UgN>>N = 6

UgN>>K = 4

UgN>>Результат 7/3 = 2;


UgN>>Это как?


MP>А вот так:

MP>
MP>_____|____ 
MP>___|___ | | 
MP>| | | | | | 
MP>1 2 3 4 5 6
MP>


Фигвам -- жилище индейское!

sizeof( some_data ) неопределен и вполне может быть даже больше, чем К * sizeof( node* )

А это значит, что нельзя в одном union хранить и данные и указатели!
Или — или.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.