Презентация, доклад по теме Комбинаторика в Pascal

longint;
begin
write('n='); r
eadln (n);
if n<0 then write('error!')
else
begin
f:=1;
for i:=1 to n do
f:=f*i;
writeln (n,'!=',f);
end;
readln;
end.

Вычисление факториала через использование рекурсии

program z1r;
var n: integer;

function fact(a: integer): longint;
begin
if a=0 then fact:=1
else
fact:=a*fact(a-1);
end;

begin
write('n='); readln (n);
if n<0 then write('error!')
else
writeln (n,'!=',fact(n));
readln;
end.

6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

program z1;
var n, i: integer;
f : double;
begin
{write('n='); readln (n);}
for n:=0 to 25 do
if n<0 then write('error!')
else
begin
f:=1;
for i:=1 to n do
f:=f*i;
writeln (n,'!=',f:0:0);
end;
readln;
end.

6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

program z1;
var
n, i: integer;
f : extended;
begin
{write('n='); readln (n);}
for n:=0 to 25 do
if n<0 then write('error!')
else
begin
f:=1;
for i:=1 to n do
f:=f*i;
writeln (n,'!=',f:0:0);
end;
readln;
end.

6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040 {INTEGER}
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600 {LONGINT}
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000 {DOUBLE, COMP}
21! = 51090942171709440000 {EXTENDED}
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000

ПРОБЛЕМА:
Вычисление факториалов «больших» чисел
Например: 100!

= 12·10002 + 345·10001 + 678·10000

система счисления с основанием 1000!

A = 12345678

= 33;
var A: array[0..N] of longint;

Основной алгоритм:

[A]:= 1
нц для k от 2 до 100
[A]:= [A] * k
кц

длинное число

основание 1000000

2)

A[0]

r := перенос в A[1]

s:= A[0]*k;
A[0]:= s mod d;
r:= s div d;

s:= A[1]*k + r

3) Умножение «длинного» числа на k:

r;
A[i]:= s mod d;
r:= s div d
end;

for k:=2 to 100 do
begin
...
end;

все следующие разряды, добавляя лидирующие нули до 6 цифр

i:= N;
while A[i] = 0 do
i:= i - 1;

write( A[i] );

12345

012345

x div 100000

x mod 100000

M:= 100000;
while M > 0 do begin
write(x div M);
x:= x mod M;
M:= M div 10
end
end;

d = 1000000;
var A: array[0..N] of longint;
i,k: byte;
r,s: longint;
procedure Write6(x: longint);
var M: longint;
begin
M:= 100000;
while M > 0 do begin
write(x div M);
x:= x mod M;
M:= M div 10
end
end;

begin
a[0]:=1;
for k:=2 to 100 do
begin
r:= 0;
for i:= 0 to N do begin
s:= A[i]*k + r;
A[i]:= s mod d;
r:= s div d
end;
end;
i:= N;
while A[i] = 0 do
i:= i - 1;
write( A[i] );
for k:=i-1 downto 0 do
Write6(A[k]);
readln;
end.

включает в себя:
Пустое множество: ∅
Одноэлементные множества: {A}, {B}, {C}, {D}
Двухэлементные множества: {A,B}, {A,C}, {A,D} {B,C}, {B,D}, {C,D}
Трехэлементные множества: {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}
Четырехэлементное множество: {A,B,C,D}

Множество всех подмножеств множества из N элементов содержит 2N элементов.

Идея алгоритма:
Заведем вектор B, состоящий из 4-ёх чисел, каждое из которых может принимать значение 0 или 1.
Будем считать, что значение 1 указывает на то, что соответствующий по номеру компонент исходного множества включается в множество, а значение 0 указывает на то, что элемент не включается.

подмножества:
4321
DCBA
0000 Пустое множество
0001 A
0010 B
0011 AB
0100 C
0101 AC
0110 BC
0111 ABC
1000 D
1001 AD
1010 BD
1011 ABD
1100 CD
1101 ACD
1110 BCD
1111 ABCD

и выводит на экран множество всех подмножеств обозначая элементы соответствующими по порядку латинскими буквами.

program z3_mnoj;
const alphabet: string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var b : array [1..100] of byte;
N, i : byte;
begin
readln(N);
for i:=1 to N+1 do b[i]:=0;
writeln ('empty set');
while b[N+1]=0 do begin
i:=1;
while b[i]=1 do begin b[i]:=0; inc(i); end;
b[i]:=1;
for i:=1 to n do if b[i]=1 then write(alphabet[i]);
writeln;
end;
readln;
end.

Обнуление массива B из N+1 элемента

0000
1000
0100
1100
0010
1010
0110
1110
…
1111

BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA

Лексикографический порядок

Алгоритм построения следующей перестановки

Пример:
Перестановки из 9 компонент, обозначенных цифрами от 1 до 9

1-ая перестановка: 1 2 3 4 5 6 7 8 9

2
Какая перестановка следующая?
(Строим ее в лексикографическом порядке: возрастания величины числа, составленного из этих цифр)
Ответ: 1 9 5 8 6 2 3 4 7
Как он получается?
1) Просматриваем исходный массив от конца к началу, что бы найти первое число, которое МЕНЬШЕ предыдущего:
4
(7>6>3>2, а 4<7)
2) Среди просмотренных чисел справа от найденной (4) ищем последнее число которое больше 4:
6
(7>4, 6>4, 3<4, 2<4)
3) Меняем эти 2 числа (4 и 6) местами: 1 9 5 8 6 7 4 3 2
4) Числа (справа от 6), которые составляют убывающую последовательность (7 4 3 2) , попарно меняем местами так, что бы они составили возрастающую последовательность (2 3 4 7):
1 9 5 8 6 2 3 4 7
Это следующая перестановка.

Последняя перестановка:
9 8 7 6 5 4 3 2 1

первыми буквами латинского алфавита.

program z4_perest;
const
alphabet: string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var b : array [1..100] of byte ;
N,i,j,k : byte;
flag: boolean;
procedure swapB(i,k:byte);
var x : byte;
begin
x:=B[i]; B[i]:=B[k]; B[k]:=x;
end;
procedure writeB;
begin
for i:=1 to N do write(alphabet[b[i]]);
writeln;
end;

begin readln(N);
for i:=1 to N do b[i]:=i;
writeB;
flag:=true;
while flag do begin
i:=N;
while (i>0) and (B[i]>=B[i+1]) do i:=i-1;
if i=0 then flag:=false
else begin
for j:=i+1 to N do
if (B[j]>B[i]) then k:=j;
swapB(i,k);
for j:=i+1 to (i+ ((N+1-i) div 2))
do swapB(j,N+i+1-j);
writeB;
end;
end;
end.

этих 5 элементов по 3 (для букв и цифр от 1 до 5):
ABC 123
ABD 124
ABE 125
ACD 134
ACE 135
ADE 145
BCD 234
BCE 235
BDE 245
CDE 345

Лексикографический порядок

Алгоритм генерации последовательности
Выберем наименьшие M из N чисел и выпишем их в порядке возрастания - 1 2 3 - это начальное сочетание.
Наибольшие M из N чисел (3 4 5), выписанные в порядке возрастания, последнее сочетание.

которой не стоит последнее из возможных значений
4) Увеличиваем его на 1
5) Все последующие элементы сочетания получаем увеличением на 1 предыдущего элемента сочетания.

Например пусть текущее сочетание: 1 3 5
(Анализ начинаем с последней позиции)
5 - это последнее возможное значение, переходим к предыдущей позиции.
3 - это не последнее возможное значение для этой позиции (каковым является 4 в данном случае). Потому мы его увеличиваем на 1 - получаем 4.
Число в следующей позиции получаем прибавлением 1 к этой 4-ке - и получаем 5.
Таким образом следующее значение: 1 4 5

и выводит в лексикографическом порядке все сочетания из N первых латинских букв по M.

program z5_sochet;
uses crt;
const
alphabet:
string[26] =
'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
b : array [1..100] of byte;
N, M, i, j, k : byte;
flag: boolean;
procedure WriteB;
begin
for i:=1 to M do write(alphabet[b[i]]);
writeln;
end;

begin readln(N,M);
for i:=1 to M do b[i]:=i;
writeB;
flag:=true;
while flag do
begin
i:=M;
while (i>0) and (b[i]=N-m+i) do dec(i);
if i=0 then flag:=false
else begin
inc(B[i]);
for j:=i+1 to M do B[j]:=B[j-1]+1;
writeB;
end;
end;
readln;
end.

можно воспользоваться композицией алгоритмов, изложенных выше.
⇒
Генерировать все сочетания из N по M
Для каждого сочетания генерировать все перестановки из M элементов.
Пример 4.
Генерируем все размещения из 5 элементов по 3, сами элементы обозначим латинскими буквами A, B, C, D, E.
Решение:
ABC ACB BAC BCA CAB CBA
ABD ...
ABE ...
ACD ...
ACE ...
ADE ...
BCD ...
BCE ...
BDE ...
CDE CED DCE DEC ECD EDC

Все возможные перестановки из 3 букв 1-го элемента строки

1-ые элементы строк представляют все возможные сочетания из 5 букв по 3

byte;
var
b : barray;
N,M,i,j,k : byte;
z : longint; flag : boolean;
procedure WriteB (B:barray);
begin
inc(Z);
write (Z:3,' : ');
for i:=1 to M do write(alphabet[b[i]]);
writeln;
end;
procedure SwapB(var B:barray;i,k:byte);
var x : byte;
begin
x:=B[i]; B[i]:=B[k]; B[k]:=x;
end;

procedure PermuteAll(B:barray; N:byte);
var i,k,j : byte;
begin
writeB(B);
while (true) do begin
i:=N;
while (i>0) and (B[i]>=B[i+1]) do i:=i-1;
if i=0 then exit;
for j:=i+1 to N do if (B[j]>B[i]) then K:=j;
swapB(B,i,k);
for j:=i+1 to (i+ ((N+1-i) div 2)) do swapB(B,j,N+i+1-j);
writeB(B);
end;
end;
begin readln(N,M);
for i:=1 to M do b[i]:=i; PermuteAll(B,M);
flag:=true;
while (flag) do begin
i:=M;
while (i>0) and (b[i]=N-m+i) do dec(i);
if i=0 then flag:=false
else begin
inc(B[i]);
for j:=i+1 to M do B[j]:=B[j-1]+1; PermuteAll(B,M);
end;
end;
readln; end.

Оператор exit предназначен для досрочного завершения процедуры или функции

Задача 6.
Написать программу, которая вводит с клавиатуры числа N, M и генерирует все возможные размещения из N букв по M.

по описанному выше алгоритму все сочетания из N по M. Для каждого построенного в векторе B сочетания вызывается процедура PermuteAll, которой в качестве параметров передаются текущее сочетание B и количество элементов в нем M. Процедура PermuteAll генерирует для полученного сочетания все возможные перестановки.
2. Массив B передается в процедуру PermuteAll по значению (при объявлении процедуры при параметре B нет ключевого слова VAR) и потому изменения массива B в процедуре PermuteAll не влияют на содержимое массива B в главной программе.
3. В то же время для того, что бы процедура SwapB могла обменивать значения в B и возвращать измененный массив в вызывающую ее процедуру PermuteAll, массив B добавлен в параметры процедуры SwapB с передачей по адресу - используя ключевое слово VAR.
4. Для передачи массива в качестве параметра заведен специальный тип BARRAY.
5. Для подсчета всех сгенерированных размещений используется переменная Z в процедуре WriteB.

Таблица чисел p(i,j) таких, что
p(i,j) = p(i-1,j-1) + p(i-1,j)
p(i,0) = 1
p(0,j) = 0 при j>0
Или иногда часть этой таблицы не выше главной диагонали

j:= 1 to N do p[j, 1]:= 1;
for i:= 3 to N do
for j:= 2 to i-1 do p[i, j]:= p[i-1, j-1]+p[i-1, j];
for i:= 1 to N do begin
for j:= 1 to N-i do Write(' ':3);
for j:= 1 to i-1 do Write(p[i, j]:6);
writeln;
end;
readln;
end.

Цикл предназначен для вывода в «треугольном» виде