Рефетека.ру / Информатика и програм-ие

Лабораторная работа: Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)

Лабораторная работа № 2. Комбинаторика


Цель работы:

Получение практических навыков решения комбинаторных задач.

Программа работы:

1. Изучить теорию.

2. Разработать программу формирования перестановок, сочетаний, размещений.

3. Выполнить вычислительные эксперименты.

Используемые программно-технические средства:

1. Персональный компьютер типа IBM PC.

2. Turbo Pascal 7.0.

Краткая теория:

Комбинаторикой называют раздел дискретной математики, в котором рассматриваются вопросы, связанные с формированием и подсчетом комбинаций из элементов перестановок, сочетаний, размещений.

Перестановкой из Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.) элементов называют комбинации отличающиеся порядком расположения элементов.

Количество перестановок определяется по формуле


Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)


Сочетанием из Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.) элементов по Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.) элементам называются комбинации отличающиеся хотя бы одним элементом.

Количество сочетаний без повторений определяется по формуле:


Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)

Размещением без повторений из Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.) элементов по Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.) называют комбинации, отличающиеся либо элементами, либо порядком расположения элементов.

Количество размещений без повторений определяется по формуле:


Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)


Число размещений связано с числом перестановок и сочетаний соотношением:


Разработка программы формирования перестановок, сочетаний, размещений (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.

Похожие работы:

  1. Разработка программ в среде программирования ...
  2. • Разработка программы Helpopr
  3. • Обучающая программа Графика программированию в графическом ...
  4. • Язык Paskal. Основные элементы языка. Структура программы
  5. • Вычисление интегралов методом Монте-Карло
  6. • Численные методы решения типовых математических задач
  7. • Анализ алгоритмов нечисленной обработки данных
  8. • Обработка данных о студентах
  9. • Вычисление вероятности игры в КРЭКС(кости)
  10. • Разработка программы на четырех языках ...
  11. • Периферийное устройство ПЭВМ, Характеристика этапов ...
  12. • Среда разработки Турбо Паскаль 7.0. Базы данных
  13. • Автоматизированное рабочее место учителя
  14. • Решение задачи о кратчайшем маршруте
  15. • Разработка информационно-справочной системы ...
  16. • Разработка программы на языке Borland Object Pascal ...
  17. • Курсовая работа программирование на Pascal
  18. • Прикладное программное обеспечение. Оновные понятия ...
  19. • Расчет напряженности поля радиотелецентров
Рефетека ру refoteka@gmail.com