Лабораторная работа № 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.
Другие работы по теме:
Автоматизированния система обучения программированию
Актуальной проблемой совершенствования учебного процесса является разработка программного обеспечения для его проведения. Очевидным пробелом является почти полное отсутствие средств обучения основам программирования.
Перестановки
Описываются понятия r-перестановок множества, r-сочетания, перестановки с повторениями.
Автоматизований аналіз злочинності по областям
Розробка програми "Злочин", що призначена для збереження та перегляду, а також автоматичного аналізу всієї інформації про злочинність. Порядок і основні принципи формування структури даних, постановка задачі. Написання та лістинг розробленої програми.
Ошибки при выполнении программы. Опции компилятора
Умея пользоваться массивами, условными операторами и операторами цикла, вы мо-жете писать довольно серьезные программы. При выполнении этих программ неизбежно будут возникать критические ошибки, приводящие к аварийному завершению программы.
Нахождение интегралов в среде Pascal
Методика и основные этапы нахождения интеграла функции sin (x+10)+x4=0 с помощью двух подходов: метод прямоугольников и метод трапеций. Составление соответствующей программы в среде Pascal. Оценка возможностей пользователя при решении данного задания.
Лабораторная работа №6
Цель работы: Освоение правил составления программ циклической структуры с параметром. Задание № 17 . Вычислить значение функции , по указанному графику для значений аргумента
Лабораторная работа №5
Цель работы: изучение условного оператора, оператора отбора, составного оператора и правил программирования разветвляющихся алгоритмов. Задание № 17
Лабараторная работа №4
Цель работы: изучение правил записи констант, переменных, выражений, операторов присваивания, раздела определения констант, раздела описания переменных и общей структуры программы на языке Turbo-Pascal.
Вращение треугольника
Содержание Введение 2 В программу также были включены функции предоставляющие пользователю некоторый сервис и удобство при работе ( использование модулей Turbo-Vision 2.0 for Borland Pascal). 5
Создание графических объектов с помощью псевдографики
Основы работы на языке высокого уровня Turbo Pascal. Основное оборудование и программное обеспечение. Операторы, необходимы для работы в графической среде Turbo Pascal. Запуск графического режима. Текст программы в графической среде Turbo Pascal.
Работа с типами данных записи
Создание программы для обработки структуры данных. Возможность ввода и записи данных на персональном компьютере. Прикладное программирование на языке Turbo Pascal. Свободное редактирование записанных данных с помощью программы, написанной на Turbo Pascal.
Язык Paskal. Основные элементы языка. Структура программы
Ознакомление со структурой языка программирования Turbo-Pascal 7.0, его алфавитом, выражениями и простейшими конструкциями (метками, идентификаторами). Способы описания арифметических, вещественных, логических и символьных операций в программной среде.
Проектування ітераційних алгоритмів
Використання ітерацій для обчислення приблизних значень величин. Розробка ітераційних алгоритмів з перевіркою правильності введення даних. Побудова блок-схеми і програмування мовою Turbo Pascal обчислення значення функції, розкладеної в степеневий ряд.
Разработка программы на четырех языках программирования
Этапы написания программы на четырех языках программирования (Turbo Pascal 7.0, Borland C++ 3.11, Delphi 7, Builder C++ 6.0), которая выводит на экран имя и фамилию студента, используя стандартные средства графики и простейшие геометрические фигуры.
Базис стандартной и рекурсивной схемы. Верификация программы
Базис класса стандартных схем программ. Стандартная схема в линейной форме. Протокол выполнения программы рекурсивной схемы. Слабейшие предусловия операторов программы в линейной форме. Верификация программы с помощью метода индуктивных утверждений.
Написание игры "Змейка" средствами языка Turbo Pascal
Изучение текстового режима языка программирования Turbo Pascal. Написание игры "Змейка" с помощью средств, процедур и функций языка программирование Turbo Pascal. Структурное и функциональное описание разработки. Листинг и общие примеры работы программы.
Среда программирования Turbo Pascal
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Тульский государственный университет
Turbo Pascal
Рязанская государственная радиотехническая академия Кафедра Вычислительной и Прикладной математики Пояснительная записка К курсовой работе по дисциплине
Turbo Or Nitrous Essay Research Paper Turbo
Turbo Or Nitrous Essay, Research Paper Turbo or Nitrous As you are driving, you see many cars going over the speed limit. Many of the drivers are into racing and modifying their cars. In most cars there are two major modifications that can be done, they are; turbo kit, or a nitrous kit. Both increase horsepower dramatically, but one is instant and the other goes into effect after a certain rpm.
Pascals Wager Essay Research Paper
“Who is God? Where is God? Does God really exist? Should I believe in God?” These are some of the questions which are asked by millions of people each and every day who are desperately trying to find some meaning in their life. Blaise Pascal tried to help society, as well as himself, to find the best solution to these problems.
Descartes Pascal And The Rationalist Credo Essay
, Research Paper Descartes, Pascal, and the Rationalist CredoPascal asserts that we can know only by the heart, whereas Descartes would have us believe through his truths that we can know with certainty of Gods existence. The factors that go into their views on reason will be compared and accented within this essay.
Pascals Triangle Essay Research Paper The arithmetic
Pascals Triangle Essay, Research Paper The arithmetic triangle was developed in 1653 by Blaise Pascal. He named this triangle after himself and today it is known as Pascal’s Triangle. It is an arrangement of certain whole numbers in a triangular pattern.
Fd Or Fc Essay Research Paper I
Fd Or Fc? Essay, Research Paper I am deciding whether to get a 3rd generation or 2nd generation Mazda RX-7. The 3rd generation was made from 1993-1995 and is known as the RX-7 Twin turbo or FD3S. The 2nd generation that I am considering was made from 1989-1991 and is known as the RX-7 Turbo II or the FC3S. The FD has a more modern rounded look, kind of like a Dodge Viper or the Chevy Corvette C5.