IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

> Кол-во правлиьных двоичных деревьев для N элем, Кол-во правлиьных двоичных деревьев
Гость_Wizard
сообщение 20.10.2004 10:35
Сообщение #1


Гость






Есть ли какая-нибудь формула по которой можно посчитать максимальное количество правильных двоичных деревьев для n элементов, а то я уже неделю бьюсь, так никакой законамерности и не увидел sad.gif(.
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Digitalator
сообщение 28.10.2004 1:45
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 247
Пол: Мужской

Репутация: -  1  +


Это же форум по програмированию! Так давайте програмировать! smile.gif
Чтоб найти к-во возможных деревьев из n элементов, нужно знать к-во возможных деревьев с n-1, n-2 ... и 1 элементами.
К-во деревьев с 1 элементом - 1;
К-во деревьев с 0 елементами тоже 1 smile.gif
теперь мы просто для каждого последующего числа элементов перебираем к-во элементов в левой и правой ветви, чтоб их сумма была нужной. Для каждого такого варианта, к-во возможных вариантов растановки будет произведением к-ва возможных вариантов растоновок в каждой его ветви. Поэтому нужно всего лишь сумировать все эти произведения, и мы получим к-во возможных деревьев для следующего числа элементов.
Теперь можно просто провести описанную выше процедуру необходимое число раз, и мы получим нужное число. :yes:
вот простая программа на Delphi, демонстрирующая данный алгоритм (чтоь она работала на обычном TP, нужно всего лишь уменьшить константу maxsize до примерно 6000(в зависимости от настроек компилятора, чтоб все влезло в один сегмент 65кб))
Код
{$APPTYPE CONSOLE}
const maxsize = 8202;
var m:array[0..maxsize] of extended;
   index:word;
   x:word;
   i:word;
   sum:extended;
   max:word;
   c:char;
begin
max:=1;
m[0]:=1;
m[1]:=1;
sum:=0;
repeat
repeat
write ('input num :');
readln(x);
until (x>1)and(x<=maxsize);
for index:=max+1 to x do
 begin
 sum:=0;
 for i:=0 to index-1 do  sum:=sum + (m[i]*m[index-1-i]);
 m[index]:=sum;
 end;
if x>max then max:=x;
writeln(m[x]);
write('Continue? ');
readln(c)
until (c in ['n', 'N']);
end.

Т.к. результатом выполнения при x>17 резултатом будут очень большие числа rolleyes.gif , здесь используются числа с плавающей точкой в которых можно хранить результаты до x=8202 включительно, но с нек. (но очень маленькой) потерей точности вычисления.

ваши мысли/замечания/предложения? :p1:


--------------------
In byte we trust
ICQ World.ru
mail[dog]digitalator[dot]com
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Гость_Wizard   Кол-во правлиьных двоичных деревьев для N элем   20.10.2004 10:35
Atos   Надо посмотреть книги по теории графов. Думаю, для...   20.10.2004 13:28
Гость_Wizard   Нудно именно для двоичных деревьев. А автора книги...   20.10.2004 16:32
Atos   Ээ-э... Сразу могу вспомнить только двух авторов :...   23.10.2004 12:53
Atos   Вот формула: n^(n-2). Доказано Кэли, потом найдено...   25.10.2004 13:56
Гость_Wizard   Тоесть формула - число элементов в степени - (числ...   26.10.2004 8:00
Гость_Wizard   Для 5 элементов получается 125 перестановок. Если ...   26.10.2004 8:07
Atos   Гм, а я насчитал 12 :o Да нет, все-таки мы оба г...   26.10.2004 11:54
Wizard   Хм 12 ну никак не получается. елсли взять числа 5 ...   26.10.2004 17:33
Atos   Блин! Стоп! Я конкретно стормозил. Даю фо...   27.10.2004 14:49
Wizard   :)   27.10.2004 19:06
Digitalator   Это же форум по програмированию! Так давайте п...   28.10.2004 1:45
Atos   Здорово! Если под ПРАВИЛЬНЫМИ двоичными деревь...   28.10.2004 13:58
Wizard   Что-то я наверно задачу неправильно объяснил... Ну...   29.10.2004 12:25
Wizard   Мде форматирование текста не сохранилось :(((   29.10.2004 12:26
Wizard   RE: Кол-во правлиьных двоичных деревьев для N элем   29.10.2004 18:53
Digitalator   А тут что сложного? как я понимаю, тут n позиций, ...   29.10.2004 20:08
Wizard   Решение таки найдено :). Вообщем сначала создаем в...   11.11.2004 10:52


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 26.07.2025 2:24
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"