(.
Полная версия: Кол-во правлиьных двоичных деревьев для N элем
Есть ли какая-нибудь формула по которой можно посчитать максимальное количество правильных двоичных деревьев для n элементов, а то я уже неделю бьюсь, так никакой законамерности и не увидел (.
(.
Надо посмотреть книги по теории графов. Думаю, для деревьев формула существует(хотя для произвольных графов это число можно лмшь оценить с некоторой точностью).
Нудно именно для двоичных деревьев. А автора книги не подскажешь?
Ээ-э... Сразу могу вспомнить только двух авторов : Харари, Кристофидес... У нас вообще в читалки книг по графам полно. Но в какой именно есть, точно не знаю
Вот формула: n^(n-2). Доказано Кэли, потом найдено более удобное доказательство. Правда, всё равно длинноватое. Привести?
Тоесть формула - число элементов в степени - (число елементов - 2)? Если да, то что-то она не совем работает
Для 5 элементов получается 125 перестановок. Если брать без 1ого элемента - 4 в степени 2 - 16 вариантов. А я всего 8 насчитал.
Цитата(Гость_Wizard @ 26.10.04 5:07)
4 в степени 2 - 16 вариантов. А я всего 8 насчитал.
Гм, а я насчитал 12 :o
Да нет, все-таки мы оба где-то ошибаемся. Формула точная n^(n-2) помеченных деревьев с n вершинами для любого n>=2.
А для непомеченных деревьев(т. е. для классов изоморфизма) общей формулы, всё-таки, скорее всего не существуют. Очевидно, для n=4, например, таких различных деревьев всего 2...
Хм 12 ну никак не получается. елсли взять числа 5 4 3 2 1 то для последних 3 будет 6 перестановок далее осьавшиеся 2 - 5 3 4 2 1 и 5 3 4 1 2.
Блин! Стоп!
Я конкретно стормозил. Даю формулу для произвольных деревьев, а надо для двоичных.
Не знаю, что и сказать...
Я конкретно стормозил. Даю формулу для произвольных деревьев, а надо для двоичных.
Не знаю, что и сказать...
Это же форум по програмированию! Так давайте програмировать!
Чтоб найти к-во возможных деревьев из n элементов, нужно знать к-во возможных деревьев с n-1, n-2 ... и 1 элементами.
К-во деревьев с 1 элементом - 1;
К-во деревьев с 0 елементами тоже 1
теперь мы просто для каждого последующего числа элементов перебираем к-во элементов в левой и правой ветви, чтоб их сумма была нужной. Для каждого такого варианта, к-во возможных вариантов растановки будет произведением к-ва возможных вариантов растоновок в каждой его ветви. Поэтому нужно всего лишь сумировать все эти произведения, и мы получим к-во возможных деревьев для следующего числа элементов.
Теперь можно просто провести описанную выше процедуру необходимое число раз, и мы получим нужное число. :yes:
вот простая программа на Delphi, демонстрирующая данный алгоритм (чтоь она работала на обычном TP, нужно всего лишь уменьшить константу maxsize до примерно 6000(в зависимости от настроек компилятора, чтоб все влезло в один сегмент 65кб))
Т.к. результатом выполнения при x>17 резултатом будут очень большие числа
, здесь используются числа с плавающей точкой в которых можно хранить результаты до x=8202 включительно, но с нек. (но очень маленькой) потерей точности вычисления.
ваши мысли/замечания/предложения? :p1:
Чтоб найти к-во возможных деревьев из n элементов, нужно знать к-во возможных деревьев с n-1, n-2 ... и 1 элементами.
К-во деревьев с 1 элементом - 1;
К-во деревьев с 0 елементами тоже 1
теперь мы просто для каждого последующего числа элементов перебираем к-во элементов в левой и правой ветви, чтоб их сумма была нужной. Для каждого такого варианта, к-во возможных вариантов растановки будет произведением к-ва возможных вариантов растоновок в каждой его ветви. Поэтому нужно всего лишь сумировать все эти произведения, и мы получим к-во возможных деревьев для следующего числа элементов.
Теперь можно просто провести описанную выше процедуру необходимое число раз, и мы получим нужное число. :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.
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 резултатом будут очень большие числа
, здесь используются числа с плавающей точкой в которых можно хранить результаты до x=8202 включительно, но с нек. (но очень маленькой) потерей точности вычисления.ваши мысли/замечания/предложения? :p1:
Здорово!
Если под ПРАВИЛЬНЫМИ двоичными деревьями имелись в виду именно все помеченные двоичные деревья с виксированной корневой вершиной, то это именно то, что нужно.
Мне, в принципе, тоже приходила мысль написать программку, но подсчитывающую кочичество различных непомеченных деревьев, а это будет сложнее.
Если под ПРАВИЛЬНЫМИ двоичными деревьями имелись в виду именно все помеченные двоичные деревья с виксированной корневой вершиной, то это именно то, что нужно.
Мне, в принципе, тоже приходила мысль написать программку, но подсчитывающую кочичество различных непомеченных деревьев, а это будет сложнее.
Что-то я наверно задачу неправильно объяснил... Нужно перебрать все варианты заполнения двоичных, правильнозаполненых деревьев, то есть
допустим у нас есть 5 вершин, значит у нас есть неповторяющиеся числа числа (для простоты возьмем 1,2,3,4,5) Деревья заполняются с 0ого уровня и ниже с лева направо (в смысле вершины распределяются на последующих уровнях слева напрво) и причем все предки больше потомков. Для приведенных 5 чисел варинатов заполнения будет 8. Так как вершину будет занимать всегда число 5. 4ка сможет перемещаться только по 1 ому уровню для оставшихся трех элементов перестановок будет (3)!=6 так как они могут занимать места друг друга не противореча условию. То есть 5,4,(3,2,1)! и оставшиеся две перестановки 5,3,4,(2,1)! и того 8 перестановок.
то есть если пронумеровать графы:
(1)
/ \
(2) (3)
/ \
(4) (5)
То самой 1ой перестановкой (когда мы просто распеделим элементы по порядку) будет:
(5) (5) (5)
/ \ / \ / \
(4) (3) и последние 2 - (3) (4) (3) (4)
/ \ / \ / \
(2) (1) (2)(1) (1) (2)
допустим у нас есть 5 вершин, значит у нас есть неповторяющиеся числа числа (для простоты возьмем 1,2,3,4,5) Деревья заполняются с 0ого уровня и ниже с лева направо (в смысле вершины распределяются на последующих уровнях слева напрво) и причем все предки больше потомков. Для приведенных 5 чисел варинатов заполнения будет 8. Так как вершину будет занимать всегда число 5. 4ка сможет перемещаться только по 1 ому уровню для оставшихся трех элементов перестановок будет (3)!=6 так как они могут занимать места друг друга не противореча условию. То есть 5,4,(3,2,1)! и оставшиеся две перестановки 5,3,4,(2,1)! и того 8 перестановок.
то есть если пронумеровать графы:
(1)
/ \
(2) (3)
/ \
(4) (5)
То самой 1ой перестановкой (когда мы просто распеделим элементы по порядку) будет:
(5) (5) (5)
/ \ / \ / \
(4) (3) и последние 2 - (3) (4) (3) (4)
/ \ / \ / \
(2) (1) (2)(1) (1) (2)
Мде форматирование текста не сохранилось ((
((
Цитата
(1)
/ \
(2) (3)
/ \
(4) (5)
То самой 1ой перестановкой (когда мы просто распеделим элементы по порядку) будет:
(5) (5) (5)
/ \ / \ / \
(4) (3) и последние 2 - (3) (4) (3) (4)
/ \ / \ / \
(2) (1) (2) (1) (1) (2)
/ \
(2) (3)
/ \
(4) (5)
То самой 1ой перестановкой (когда мы просто распеделим элементы по порядку) будет:
(5) (5) (5)
/ \ / \ / \
(4) (3) и последние 2 - (3) (4) (3) (4)
/ \ / \ / \
(2) (1) (2) (1) (1) (2)
А тут что сложного? как я понимаю, тут n позиций, на которых надо расставить n чисел - чистая комбинаторика, открываем справочник и смотрим 
Либо ты помогаешь, либо не даешь подобных глупых советов! administrator
А в чем глупость? Знаете, если будут полностью конкретные и самодостаточные вопросы, то и ответы всегда будут в тему, если я что неправильно понял, то покажите в каком месте и подумаем еще раз.
Либо ты помогаешь, либо не даешь подобных глупых советов! administrator
А в чем глупость? Знаете, если будут полностью конкретные и самодостаточные вопросы, то и ответы всегда будут в тему, если я что неправильно понял, то покажите в каком месте и подумаем еще раз.
Решение таки найдено .
Вообщем сначала создаем всевозможные перестановки для (n-1) элементов, а потом выбираем из них те которые подходят под требование правильного дерева.
.Вообщем сначала создаем всевозможные перестановки для (n-1) элементов, а потом выбираем из них те которые подходят под требование правильного дерева.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.