Комбинаторика |
Комбинаторика |
Altair |
15.01.2005 15:03
Сообщение
#1
|
Ищущий истину Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Код Function Accomodations(N,K:Longint):Longint; var i,Result:longint; begin Result:=1; For i:=n downto (n-k+1) do result:=result*i; Accomodations:=result end; Function Transpositions(N:longint):Longint; begin Transpositions:=Accomodations(N,N) end; Function Combination(N,K:Longint):Longint; var numerator,denominator,i:longint; begin numerator:=1; denominator:=1; for i:=N downto (N-K+1) do numerator:=numerator*i; for i:=1 to K do denominator:=denominator*i; Combination:=numerator div denominator end; procedure BinomialTheorum(N:longint); var K,T,SA,SB:Longint; begin writeln; for K:=0 to n do begin SA:=n-k; SB:=k; T:=Combination(N,K); If T>1 then write(T); If SA=1 then write('A'); If SA>1 then write('A^',SA); If SB=1 then write('B'); If SB>1 then write('B^',SB); If k<>n then write(' + '); end; writeln end; begin BinomialTheorum(3); writeln(Combination(14,7)); writeln(Accomodations(14,5)); writeln(Transpositions(3)); end. Function Accomodations(N,K:Longint):Longint; Вычисление размещений из N по К. (число размещений из N по K есть число К-элементных упорядоченных подмножеств множества, содержащего N элементов.) Function Transpositions(N:longint):Longint; Вычисление числа перестановок. (A из n по n) Function Combination(N,K:Longint):Longint; Вычисление сочетаний из N по K. (k элементные подмножества множества, содержащего N элементов.) procedure BinomialTheorum(N:longint); Выводит на экран разложение (a+b)^n. по формуле Ньютона. Входной паарметр - N. -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
samec |
12.12.2008 8:56
Сообщение
#2
|
Бывалый Группа: Пользователи Сообщений: 180 Пол: Мужской Реальное имя: Юра Репутация: 1 |
Генерация разбиений n-элементного множества на k блоков.
Разбиение множества (1,…,n) мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Например (для множества из 4 элементов, разбиение на три подмножества): ( 1 2 ) ( 3 ) ( 4 ) ( 1 4 ) ( 2 ) ( 3 ) ( 1 ) ( 2 4 ) ( 3 ) ( 1 ) ( 2 ) ( 3 4 ) ( 1 ) ( 2 3 ) ( 4 ) ( 1 3 ) ( 2 ) ( 4 ) (в каждом блоке элементы упорядочены по возрастанию) Этот наименьшей элемент блока мы будем называть номером блока. Надо заметить, что номера соседних блоков совсем не обязательно являются соседними натуральными числами, например для блоков: ( 1 2 ) ( 3 ) ( 4 ), номера каждого блока будут: 1, 3 и 4. В этом алгоритме мы будем использовать переменные Prev[i], Next[i], 1<=i<=n, содержащие соответственно номер предыдущего и номер следующего блока, для блока с номером i. (Next[i]=0, если блок с номером i является последним блоком разбиения) Например для разбиения ( 1 2 ) ( 3 ) ( 4 ) эти переменные будут выглядеть следующим образом: Prev[0,1,3], Next[3,4,0]. Для каждого элемента I, 1<=i<=n, номер блока, содержащего элемент i, будет храниться в переменной Blok[i], например для разбиения ( 1 2 ) ( 3 ) ( 4 ) – Blok[1,1,2,3], а для разбиения ( 1 3 ) ( 2 ) ( 4 ) – Blok[1,2,1,3]. Направление, в котором «движется» элемент I, будет находиться в переменной Forw[i] (Forw[i]==1, если I, движется вперед, Forw[i]==0, если I, движется назад).
|
Текстовая версия | 27.05.2024 5:08 |