Лабораторная работа № 2. Комбинаторика
Цель работы:
Получение практических навыков решения комбинаторных задач.
Программа работы:
1. Изучить теорию.
2. Разработать программу формирования перестановок, сочетаний, размещений.
3. Выполнить вычислительные эксперименты.
Используемые программно-технические средства:
1. Персональный компьютер типа IBM PC.
2. Turbo Pascal 7.0.
Краткая теория:
Комбинаторикой называют раздел дискретной математики, в котором рассматриваются вопросы, связанные с формированием и подсчетом комбинаций из элементов перестановок, сочетаний, размещений.
Перестановкой из
Количество перестановок определяется по формуле
Сочетанием из
Количество сочетаний без повторений определяется по формуле:
Размещением без повторений из
Количество размещений без повторений определяется по формуле:
Число размещений связано с числом перестановок и сочетаний соотношением:
Математическая постановка задачи:
Составить программу формирования перестановок, сочетаний, размещений с выводом результатов на экран дисплея.
Описание программы:
Данная программа, написанная на языке Паскаль, начинается с раздела переменных, полный список которых представлен в таблице 1. В основе алгоритма программы лежат три процедуры, каждая из которых отвечает за закрепленную за ней часть программы (см. таблицу 2). Выбор требуемой операции происходит путем использования оператора case.
Работа программы начинается с вывода сообщения о необходимости выбрать операцию для выполнения. Далее требуется ввести из скольки и по сколько элементов будет осуществляться данная операция. Результат выполнения операции выводится на экран.
Таблица 1 - Список идентификаторов переменных
Идентификатор | Тип | Применение |
massiwi1 | massiwi1:massiwi; | Для хранения промежуточных результатов |
massiwi2 | massiwi2:massiwi; | Для хранения промежуточных результатов |
iz_skolki | integer | Из скольки элементов |
po_skolko | integer | По сколько элементов |
i, j, | integer | Для организации циклов |
Nomer | integer | Хранит номер выбранной операции |
y | integer | Вспомогательная переменная |
Таблица 2 - Список процедур
Имя процедуры | Формальные параметры | Вызов процедуры | Применение |
sochetanye | m, y - целые числа; | sochetanye(m,y:integer); | Операция сочетания |
perestanovka | m, y - целые числа; s - массив; | perestanovka(m,y:integer; s:mas); | Операция перестановки |
razmesheniye | m, y - целые числа; | razmesheniye(m,y:integer; s:mas); | Операция размещения |
Постановка отдельного примера:
Рассмотрим все возможные перестановки из 7-ми элементов, сочетания из 6 по 3 элемента и размещения из 7 по 3 элемента.
Вывод
В результате всей проделанной работы мы получили практические навыки решения комбинаторных задач, также нами была разработана программа на языке Паскаль, реализующая формирование перестановок, сочетаний и размещений с выводом результатов на экран дисплея.
Приложение
Листинг программы
uses crt;
label kombinatorika;
type
massiwi=array [1..20] of integer;
var
massiwi1:massiwi;
massiwi2:massiwi;
iz_skolki, po_skolko:integer;
i,j:integer;
nomer:integer;
y:integer;
procedure perestanovka(m,y:integer; s:massiwi);
var
j,i:integer;
s1:massiwi;
begin
for i:=1 to m do begin
massiwi1[y]:=s[i];
j:=1;
for y:=1 to m do begin
if s[y]<>s[i] then begin
s1[j]:=s[y];
j:=j+1;
end;
end;
if y=iz_skolki then begin
for j:=1 to iz_skolki do write(massiwi1[j]);
writeln;
end else
perestanovka(m-1,y+1,s1);
end;
end;
procedure sochetanye(m,y:integer);
var
j,i:integer;
begin
for i:=1 to m do begin
massiwi1[y]:=i;
if y=po_skolko then begin
for j:=1 to po_skolko do write(massiwi1[j]);
writeln;
end else
sochetanye(m,y+1);
end;
end;
procedure razmesheniye(m,y:integer; s:massiwi);
var
j,i:integer;
begin
for i:=1 to m do begin
massiwi1[y]:=i;
if y=po_skolko then begin
for j:=1 to po_skolko do write(massiwi1[j]);
writeln;
perestanovka(po_skolko,1,massiwi2);
end else begin
sochetanye(m,y+1);
perestanovka(po_skolko,1,massiwi2);
end;
end;
end;
Begin
kombinatorika:clrscr;
for i:=1 to 8 do
writeln;
writeln(' Wi dolgni wibrat neobhodimuy operaciyu:');
writeln('-->> 1. Razmeshenie;');
writeln('-->> 2. Perestanovka; ');
writeln('-->> 3. Sochetanie; ');
writeln('-->> 4. Vihod.');
writeln;
write('-->> Wi wibrali:');
readln(nomer);
case nomer of
1: begin
clrscr;
write('Sochetanye iz=');
readln(iz_skolki);
write(' po=');
readln(po_skolko);
writeln;
writeln('Sochetanye:');
sochetanye(iz_skolki,1);
readln;
goto kombinatorika;
end;
2: begin
clrscr;
write('Perestanovka iz=');
readln(iz_skolki);
for i:=1 to iz_skolki do massiwi2[i]:=i;
writeln;
writeln('Perestanovka:');
perestanovka(iz_skolki,1,massiwi2);
readln;
goto kombinatorika;
end;
3:begin
clrscr;
write('Razmeshenie iz=');
readln(iz_skolki);
write(' po=');
readln(po_skolko);
for i:=1 to iz_skolki do massiwi2[i]:=i;
writeln;
writeln('Razmeshenie:');
razmesheniye(iz_skolki,1,massiwi2);
readln;
goto kombinatorika;
end;
4: end;
end.