Название: Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)
Вид работы: лабораторная работа
Рубрика: Информатика и программирование
Размер файла: 20.64 Kb
Скачать файл: referat.me-139661.docx
Краткое описание работы: Сущность понятия "комбинаторика". Программа формирования перестановок, сочетаний, размещений с выводом результатов на экран дисплея. Алгоритм программы, написанной на языке Паскаль. Список идентификаторов переменных программы. Список процедур программы.
Разработка программы формирования перестановок, сочетаний, размещений (Turbo Pascal 7.0.)
Лабораторная работа № 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.
Похожие работы
-
Генерация комбинаторных объектов
Методика решения задачи по выбору подмножества, состоящего из нескольких компонент. Характеристики, порядок записи и листинг программ по генерации множества всех подмножеств из N элементов и генерации последовательности чисел в лексикографическом порядке.
-
Лабараторная работа №4
Цель работы: изучение правил записи констант, переменных, выражений, операторов присваивания, раздела определения констант, раздела описания переменных и общей структуры программы на языке Turbo-Pascal.
-
Создание графических объектов с помощью псевдографики
Основы работы на языке высокого уровня Turbo Pascal. Основное оборудование и программное обеспечение. Операторы, необходимы для работы в графической среде Turbo Pascal. Запуск графического режима. Текст программы в графической среде Turbo Pascal.
-
Работа с типами данных записи
Создание программы для обработки структуры данных. Возможность ввода и записи данных на персональном компьютере. Прикладное программирование на языке Turbo Pascal. Свободное редактирование записанных данных с помощью программы, написанной на Turbo Pascal.
-
Язык Paskal. Основные элементы языка. Структура программы
Ознакомление со структурой языка программирования Turbo-Pascal 7.0, его алфавитом, выражениями и простейшими конструкциями (метками, идентификаторами). Способы описания арифметических, вещественных, логических и символьных операций в программной среде.
-
Организация ввода-вывода. Обработка массивов. Структурированные данные
Ознакомление с основными понятиями и организацией ввода-вывода, обработкой массивов. Описание одномерных и двумерных массивов. Описание строк и операции с ними. Комбинированный тип данных - записи. Характеристика записей, использующих вариантную часть.
-
Обработка текстовых файлов
Разработка программы обработки числовых последовательностей с кодом на языке Pascal. Функции ввода пользователем с клавиатуры последовательности целых чисел. Алгоритмы разработанных процедур и функций. Инструкция пользователя, листинг программы.
-
Защищенность выборки символов
Анализ вероятности входа в систему злоумышленником с одной и трех попыток. Вероятности входа в систему при фиксированной и случайной длине выборки. Исследование и расчет защищенности (надёжности) метода при подглядываниях. Оптимизация длины выборки.
-
Прикладное программное обеспечение. Оновные понятия комбинаторики
Классификация прикладных программ. Назначение и основные функциональные возможности текстовых редакторов, табличных процессов, систем управления базами данных, графических редакторов. Комбинаторика, как отрасль математики. Основные ее соотношения.
-
Алгоритм формирования ключей в процессе функционирования DES
Процесс и основные этапы реализации алгоритма формирования ключей в процессе функционирования DES с помощью языка программирования C++. Особенности работы программного алгоритма и его пошаговая реализация. Листинг получившейся программы, пример ее работы.