![]() |
![]() ![]() |
![]() |
Altair |
![]()
Сообщение
#1
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Код 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. -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
![]()
Сообщение
#2
|
Гость ![]() |
При решении задач на практике часто приходится выбирать из некоторого множества объектов какие-либо подмножества, обладающие заданными свойствами, размещать элементы в определенном порядке и т.д. Такие задачи называются комбинаторными. Классическими задачами комбинаторики являются задачи о перестановках, выборках, сочетаниях.
Перестановки Перестановки описывают, сколькими способами можно расставить N различных предметов на N различных позиций. Число перестановок принято обозначать Pn. N различных элементов можно расставить на N различных мест N! способами. Следовательно, Pn = N! = 1*2*… *(N-1)*N. Также важной задачей является не только подсчет количества перестановок, но и их генерация, при этом больший интерес представляет генерация перестановок в определенном порядке, например, лексикографическом (отсортированном по возрастанию). Рассмотрим задачу генерации всех перестановок N-элементного множества в лексикографическом порядке. В качестве примера рассмотрим перестановку для N=3 Цитата 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Алгоритм генерации следующей перестановки таков: начиная с конца перестановки находим такой элемент a[i]: a[i-1]<a[i]; затем в конце перестановки находим элемент a[j] больший чем a[i-1]; далее меняем местами элементы перестановки a[i-1] и a[j]; и оставшуюся конечную часть перестановки упорядочиваем в порядке возрастания. { программа генерации перестановок N элементного Для получения всех n! перестановок необходимо, чтобы начальная перестановка образовывала возрастающую последовательность (то есть была первой в лексикографическом порядке). Следует прокомментировать следующие два момента: почему условием окончания работы программы является выполнение равенства j=0 и почему для упорядочивания хвоста перестановки используется простой цикл без всяких сравнений.
Сочетания Задачи о сочетаниях решают вопрос о том, сколькими способами можно выбрать M элементов из заданного N элементного множества и генерации всех возможных выборок. Число выборок вычисляется следующей формулой С=n!/(m!(n - m)!). Рассмотрим задачу о генерации сочетаний в лексикографическом порядке. Для примера рассмотрим начальные данные N=6 и M=4. Тогда число сочетаний равно 15. Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1, … , n. Цитата 1234 1256 2345 1235 1345 2346 1236 1346 2356 1245 1356 2456 1246 1456 3456 Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что a[i] <> n-k+i. Далее увеличиваем этот элемент на 1, а оставшуюся часть сочетания заполняем числами натурального ряда большими измененного элемента в порядке их следования. program sochets; Рекурсивный алгоритм генерации сочетаний (с повторениями): const Подмножества Для генерации всех подмножеств N-элементного множества: введем массив b[1..n] такой, что если b[i]=1 то i-й элемент входит в подмножество и если b[i]=0, то иначе. Тогда пустому подмножеству будет соответствовать набор из 0, а n-элементному подмножеству набор из 1. Поэтому здесь явно заметна связь с двоичным представление чисел в интервале 0 … 2N–1. Будем находить двоичное представление числа и формировать характеристические вектора подмножеств. Изначально положим b[i]=0 для всех I, что соответствует пустому подмножеству. Введем массив a[1..n] соответствующий двоичному представлению числа. Будем моделировать операцию сложения этого числа с 1. Для этого просмотрим число справа налево, заменяя единичные биты на нулевые до тех пор, пока не найдем нулевой бит, который заменим на 1. program subsets; |
samec |
![]()
Сообщение
#3
|
![]() Бывалый ![]() ![]() ![]() Группа: Пользователи Сообщений: 180 Пол: Мужской Реальное имя: Юра Репутация: ![]() ![]() ![]() |
Генерация разбиений 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, движется назад).
|
![]() ![]() |
![]() |
Текстовая версия | 21.08.2024 14:55 |