![]() |
1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
![]() |
Гость_Wizard |
![]()
Сообщение
#1
|
Гость ![]() |
Есть ли какая-нибудь формула по которой можно посчитать максимальное количество правильных двоичных деревьев для n элементов, а то я уже неделю бьюсь, так никакой законамерности и не увидел
![]() |
![]() ![]() |
Digitalator |
![]()
Сообщение
#2
|
Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 247 Пол: Мужской Репутация: ![]() ![]() ![]() |
Это же форум по програмированию! Так давайте програмировать!
![]() Чтоб найти к-во возможных деревьев из 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. Т.к. результатом выполнения при x>17 резултатом будут очень большие числа ![]() ваши мысли/замечания/предложения? :p1: -------------------- |
![]() ![]() |
![]() |
Текстовая версия | 26.07.2025 2:24 |