На тему: Алгоритмы машинной математики

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Государственный университет – учебно-научно-производственный комплекс»

 

УНИИ ИТ

 

 

Кафедра ЭВТИБ

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ
КОНТРОЛЬНОЙ РАБОТЫ

по дисциплине Основы алгоритмизации и программирования

На тему: Алгоритмы машинной математики

для студентов 3 курса очно-заочного отделения специальности:

211000.62 «Конструирование и технология электронных средств»

 

 

Составитель: ассистент _______________ Усачева О. И.

 

 

г. Орел, 2013 г.

ВВЕДЕНИЕ

Контрольная работа — это самостоятельная работа студента по дисциплине «Основы алгоритмизации и программирования».

Цель написания контрольной работы:

·  закрепить теоретические и практические знания по предмету;

·  научиться применять, полученные знания при решении практических вопросов;

·  научиться самостоятельно находить информационную базу на основе знакомства с библиографическим фондом библиотеки и читального зала ВУЗа, с помощью электронной справки и других источников информации.

ПОРЯДОК И СРОКИ СДАЧИ КОНТРОЛЬНОЙ РАБОТЫ НА РЕГИСТРАЦИЮ, ПРОВЕРКУ И ДОРАБОТКУ

Сроки выполнения и защиты контрольной работы определяются преподавателем в соответствии с учебным планом и программой курса дисциплины. Контрольная работа представляется на проверку не менее чем за две недели до зачета или экзамена. Проверка контрольной работы происходит в течение двух недель со дня передачи работы на проверку. В тех случаях, если работа не отвечает требованиям (по содержанию или по оформлению), она возвращается студенту на доработку. Замечания, заверенные своей подписью, преподаватель оставляет на первом или последнем листе работы. Студент имеет право выслушать замечания в устной форме при личной беседе с преподавателем для разъяснения необходимости доработки контрольной работы. Доработка осуществляется в трёхдневный срок со времени проверки контрольной работы.

Не засчитываются работы, оказавшиеся идентичными по своему содержанию, причем обе работы аннулируются, а их авторам выдаются новые темы. Не могут быть засчитаны работы, полностью скопированные с образцов компьютерных обучающих программ, из сети «Интернет» и т. п.

В случаях сомнений преподавателя в подлинном авторстве, он вправе потребовать от студента черновой или электронный вариант работы.

Зачёт (незачёт) контрольной работы может проводиться после завершения цикла проверок и доработок, или после проведения собеседования по контрольной работе по усмотрению преподавателя.

При проведении собеседования студент должен иметь при себе электронную версию контрольной работы.

Студенты не получившие зачёт по контрольной работе не допускаются к итоговой аттестации — зачёту, экзамену.

СТРУКТУРА КОНТРОЛЬНОЙ РАБОТЫ

Структура контрольной работы должна быть следующей:

·  титульный лист (Приложение 1);

· задание;

·  практическая часть;

В разделе задание студент помещает свой вариант задания контрольной работы.

В практической части должны быть представлены математическое описание задачи объясняющие ход её решения, блок-схема алгоритма с пояснениями и листинг программы.

ОФОРМЛЕНИЕ КОНТРОЛЬНОЙ РАБОТЫ

Оптимальный объем курсовой работы не должен превышать 10-15 страниц печатного текста формата А4.

Контрольная работа оформляется при помощи Microsoft Word.

Каждая страница основного текста и приложений должна иметь поле: левое – 20 мм, верхнее, правое и нижнее — 10 мм.

Требования к тексту курсовой работы:

шрифт — Times New Roman;

размер шрифта — 12 пт;

межстрочный интервал — полуторный.

Нумерация страниц проставляется в середине нижней части листа последовательно, начиная с 2-й страницы (задание), то есть после титульного листа.

Текст практической части работы должен соответствовать следующим требованиям: каждый расчет, таблица и график должен иметь свое название, единицы измерения и номер.

Контрольная работа скрепляется степлером или помещается в папку.

Контрольная работа считается завершенной в том случае, если она соответствует предъявленным требованиям по структуре, содержанию, языку и стилю изложения материала, правильно оформлена, отпечатана, проверена на предмет орфографических ошибок, сброшюрована, подписана автором.

 

ТЕМА И ЗАДАНИЯ ПО КОНТРОЛЬНОЙ РАБОТЕ

 

Тема контрольной работы — Алгоритмы машинной математики.

 

Варианты заданий

Номера вариантов указаны в Приложении 2.

 

СОДЕРЖАНИЕ И ПОРЯДОК ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

 

Порядок выполнения каждого пункта задания контрольной работы должен быть подробно описан и проиллюстрирован в виде рисунков, представленных в практической части.

Контрольная работа должна содержать следующие разделы.

1. Словесное или математическое описание задачи, объясняющее ход её решения.

2. Блок-схему алгоритма. При составлении блок-схемы алгоритма необходимо придерживаться рекомендаций по вычерчиванию графических символов, приведённых в разделе «Краткие теоретические сведения» настоящих методических указаний. Блок-схема обязательно должна содержать не менее 60 % пояснений действий описываемых алгоритмом. Блок-схема выполняется в электронном виде. Для этого используются графические средства MS Word, MS Paint и других известных программ.

По требованию преподавателя содержимое контрольной работы и программа должны быть представлены в электронном виде.

 

ПОНЯТИЕ АЛГОРИТМА

Процесс решения задачи представляет собой совокупность определённых действий над данными. Данными называют все величины, участвующие в решении задачи. Данные, известные перед решением, являются начальными, исходными данными. Результат решения задачи — это конечные, выходные данные. А данные, получаемые в результате обработки исходных данных и являющиеся вспомогательными данными на этапе получения выходных данных, называются промежуточными данными.

Решить задачу — значит получить результат. Для каждой точно сформулированной задачи всегда известно, что считать результатом.

Последовательность чётких однозначных указаний (действий), применение которых к определённым исходным данным, обеспечивает получение требуемого результата, называется алгоритмом.

Понятие алгоритма является одним из базовых понятий в программировании. Строгого определения алгоритма не существует. Остановимся на содержательном определении.

Алгоритмом называется конечный набор точных и понятных предписаний (правил, инструкций, команд), позволяющих механически решать конкретную задачу из определенного класса однотипных задач.

 

ÿ Создание алгоритма доступно исключительно живым существам!

 

Алгоритм создаётся в расчёте на определённого исполнителя. Исполнителей алгоритма называют формальными исполнителями. В качестве исполнителя может выступать не только человек, но и техническое устройство — автомат, робот, ЭВМ. В первую очередь к формальным исполнителям относятся автоматические устройства, в том числе и компьютер.

Для того чтобы исполнитель мог выполнить алгоритм, необходимо, чтобы он мог выполнить каждый шаг алгоритма. Совокупность команд, которые могут быть выполнены исполнителем, называют системой команд исполнителя. Для правильного построения алгоритма и программы необходимо знать систему команд исполнителя.

ÿ Создание алгоритма — процесс творческий!

СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ

Алгоритмы могут описываться различными способами, отличающимися друг от друга наглядностью, компактностью, степенью формализации. Наибольшее распространение получили способы описательный, графический и в виде программы для ЭВМ.

Описательный способ записи алгоритма ориентирован на исполнителя-человека. Записывается на естественном, в частности математическом, языке. Этот способ характеризуется высокой степенью понятности для исполнителя.

Графический – компактная форма записи в виде специальных графических символов (блоков) с указанием связей между ними. Каждый блок предписывает выполнение определённых действий. Совокупность блоков образует схему алгоритма (блок-схему). Графический способ записи алгоритма получил наибольшее распространение. Он характеризуется большой наглядностью и ориентирован на исполнителя-человека.

Алгоритм в виде программы – конечный продукт разработки алгоритма в виде программы, записанной на языке программирования.

Если задача решается с помощью ЭВМ, алгоритм решения задачи должен быть записан в понятной для машины форме, т. е. в виде программы.

ГРАФИЧЕСКИЕ СИМВОЛЫ

Некоторые часто используемые графические символы приведены в табл.1.

При разработке алгоритма каждое действие обозначают соответствующим блоком, а последовательность выполнения — линиями со стрелками на конце. Для простоты чтения схемы желательно, чтобы линия входила в блок сверху, а выходила снизу.

Для изображения линий потока существуют следующие правила.

1. Линии должны быть параллельны линиям внешней рамки схемы алгоритма (границам листа)

2. Направление линии сверху вниз или слева направо принимается за основное и стрелками не обозначается, а в остальных случаях направление линии обозначается стрелками.

3. Изменение направления линии производится под углом 90⁰.

Если схема алгоритма состоит из нескольких частей, расположенных на одной странице или не умещается на одном листе, то линия потока одной части заканчивается символом “Соединитель”, а линия потока следующей части схемы начинается с того же символа. Внутри символов “Соединитель” ставятся одинаковые порядковые номера, соответствующие разорванной линии потока.

Название блока	Обозначение	Назначение блока	Пример использования	Операторы QBasic соответствующие графическому символу
Пуск, остановка		Начало или конец программы		REM <текст> CLS
Процесс		Обработка данных (выполне­ние операций, в результате которых изменяются значе­ния, форма представления или расположение данных).		Операторы присваивания в формате   <имя переменной>=<выражение>
Решение		Выбор направления выполне­ния алгоритма в зависимости от истинности или ложности некоторых условий.		IF <Логическое условие> THEN <Действие 1> ELSE <Действие 2>
Данные		Ввод или вывод информации.		Оператор ввода: INPUT <текст>; <имя переменной>   Оператор вывода: PRINT <текст>;<имя переменной>
Подготовка		Организация счётного цикла (начало цикла). Применяется в том случае, когда известно число повторений цикла.		Оператор «начало цикла»: FOR I=Xн TO Xк  step h <Тело цикла> NEXT I
Предопреде­лённый процесс	а	Вызов процедур (использова­ние ранее созданных и от­дельно описанных алгорит­мов)		CALL (<имя процедуры и её параметры>)
Соединитель		Маркировка разрывов линий.
Межстраничный соединитель
Комментарий		Пояснения к действиям		REM <текст> или ‘ (знак апострофа) <текст>
Линии потока		Указание последовательности связей между символами

 

 

 

ПРИМЕРЫ СОСТАВЛЕНИЯ АЛГОРИТМОВ

Пример.

Математическая формулировка задачи.

Определить площадь треугольника по формуле Герона

где a, b, c — длины сторон треугольника;

— полупериметр треугольника.

Описательный алгоритм решения задачи.

1. Ввод с клавиатуры исходных данных a, b, c.

2. Вычисление p по формуле .

3. Вычисление s по формуле .

4. Вывод результата s на экран монитора.

Графический алгоритм решения задачи.

Блок-схема алгоритма представлена на рисунке 1. На семе блоки расположены в той последовательности, в которой они должны выполняться Любая перестановка блоков приведёт к невозможности решения задачи.

 

 

Рис. 4. Блок-схема алгоритма вычисления площади треугольника по формуле Герона.

 

 

Пример.

Математическая формулировка задачи.

Вычислить значение функции .

Для удовлетворения свойств массовости и результативности алгоритма необходимо, чтобы при любых исходных данных (значениях x и y) был получен результат или сообщение о том, что задача не может быть решена при заданных значениях исходных данных. Действительно, если x или y равны, то задача не может быть решена, так как деление на ноль невозможно. Поэтому в алгоритме необходимо предусмотреть вывод информации для случая, когда вычисление z невозможно. Такой вычислительный процесс можно описать следующим выражением:

вычислить , если ;

вывести сообщение , если .

Описательный алгоритм решения задачи.

1. Ввод с клавиатуры исходных данных x, y.

2. Проверка условия . Если условие выполняется, то вывести сообщение, что , в противном случае вычислить .

3. Вывести результат вычисления z на экран.

Графический алгоритм решения задачи.

Блок-схема алгоритма представлена на рис. 10.

 

 

Рисунок 5 – Блок-схема алгоритма решения задачи из примера 1.

 

Пример.

Математическая формулировка задачи.

Вычислить значения функции  при x изменяющимся от 0,1 до 1 с шагом 0,1.

Для удовлетворения свойств массовости обозначим начальную точку диапазона (0,1) за x₀, конечную точку (1) — за x_k, а шаг изменения значения x — за h.

Описательный алгоритм решения задачи.

1. Ввод с клавиатуры исходных данных: начальное значение для x — x₀; конечное значение — x_k; шаг изменения x — h.

2. Присвоить x начальное значение x= x₀.

3. Вычислить z по формуле .

4. Вывести на экран рзультат вычисления z.

5. Изменить x путём прибавления к нему шага изменения параметра .

6. Проверить условие окончания вычислений z (выхода из цикла) . Если условие выполняется, то перейти к пункту 3 данного описания для вычисления нового значения z; если же условие не выполняется, то заканчиваем вычисления (выход из цикла).

Графический алгоритм решения задачи.

Алгоритм может быть представлен в двух вариантах.

Вариант 1.

Блок-схема алгоритма представлена на рисунке 6.

 

 

Рисунок 6 – Блок-схема алгоритма вычисления значений функции z(x) на заданном интервале.

Вариант 2.

Воспользуемся тем, что нам известно число повторений цикла, которое определяется как . Следовательно можно использовать блок «начало цикла», который выполняет все функции, необходимые для организации цикла. В этом случае блок-схема алгоритма (рис. 7) становится более компактной и наглядной.

 

 

 

Рисунок 7 – Блок-схема алгоритма вычисления значений функции z(x) на заданном интервале с использованием блока «начало цикла».

 

 

Понятие сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

"Внешней" сортировкой принято называть сортировку последовательных файлов, располагающихся во внешней памяти и слишком больших, чтобы можно было целиком переместить их в основную память и применить один из рассмотренных в предыдущем разделе методов внутренней сортировки.

Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.

 

Сортировка методом Шелла

Метод состоит в том, что упорядочиваемая таблица разделяется на группы элементов, каждая из которых упорядочивается методом вставки. В процессе упорядочения размеры таких
групп увеличиваются до тех пор, пока все элементы таблицы не войдут в упорядоченную группу. Выбор очередной упорядочиваемой группы и ее расположение внутри таблицы производятся так, чтобы можно было использовать предшествующую упорядоченность. Группой таблицы называют последовательность элементов, номера которых образуют арифметическую прогрессию с разностью d (d называют шагом группы). В начале процесса упорядочения выбирается первый шаг группы d, который зависит от размера таблицы.

d=[n/2]

Массив: 23, 8, 5, 65, 47, 34, 1, 6, 13, 52

Шаг 1: d=5 (сортируются элементы, расстояние между которыми пять)

                     23, 8, 5, 65, 47, 34, 1, 6, 13, 52 –массив не меняется

                     23, 8, 5, 65, 47, 34, 1, 6, 13, 52

                     23, 1, 5, 65, 47, 34, 8, 6, 13, 52

                     23, 1, 5, 65, 47, 34, 8, 6, 13, 52– массив не меняется

                     23, 1, 5, 65, 47, 34, 8, 6, 13, 52

                     23, 1, 5, 13, 47, 34, 8, 6, 65, 52

                     23, 1, 5, 13, 47, 34, 8, 6, 65, 52 – массив не меняется

Шаг 2: d=3 (сортируются элементы, расстояние между которыми три)

                     23, 1, 5, 13, 47, 34, 8, 6, 65, 52

                     13, 1, 5, 23, 47, 34, 8, 6, 65, 52

                     13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется

                     13, 1, 5, 23, 47, 34, 8, 6, 65, 52– массив не меняется

                     13, 1, 5, 23, 47, 34, 8, 6, 65, 52

                     13, 1, 5, 8, 47, 34, 23, 6, 65, 52

                     13, 1, 5, 8, 47, 34, 23, 6, 65, 52

                     13, 1, 5, 8, 6, 34, 23, 47, 65, 52

                     13, 1, 5, 8, 6, 34, 23, 47, 65, 52– массив не меняется

                     13, 1, 5, 8, 6, 34, 23, 47, 65, 52 – массив не меняется

                         

Шаг 3: d=2 (сортируются элементы, расстояние между которыми два)

                     13, 1, 5, 8, 6, 34, 23, 47, 65, 52

                     5, 1, 13, 8, 6, 34, 23, 47, 65, 52

                     5, 1, 13, 8, 6, 34, 23, 47, 65, 52– массив не меняется

                   5, 1, 13, 8, 6, 34, 23, 47, 65, 52

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52 – массив не меняется

Шаг 4: d=1 (сортируются элементы, расстояние между которыми один)

                     5, 1, 6, 8, 13, 34, 23, 47, 65, 52

                     1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 34, 23, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 34, 23, 47, 65, 52

                     1, 5, 6, 8, 13, 23, 34, 47, 65, 52

                     1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 23, 34, 47, 65, 52– массив не меняется

                     1, 5, 6, 8, 13, 23, 34, 47, 65, 52

                     1, 5, 6, 8, 13, 23, 34, 47, 52, 65

 

Шейкерная сортировка.

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6

     23, 8, 5, 65, 47, 1, 34, 6

     23, 8, 5, 65, 1, 47, 34, 6

     23, 8, 5, 1, 65, 47, 34, 6

     23, 8, 1, 5, 65, 47, 34, 6

     23, 1, 8, 5, 65, 47, 34, 6

       1, 23, 8, 5, 65, 47, 34, 6

Шаг 2: 1, 23, 8, 5, 65, 47, 34, 6

     1, 23, 5, 8, 65, 47, 34, 6

     1, 5, 23, 8, 65, 47, 34, 6

Шаг 3: 1, 5, 23, 8, 65, 47, 34, 6

     1, 5, 23, 8, 65, 47, 6, 34

     1, 5, 23, 8, 65, 6, 47, 34

     1, 5, 23, 8, 6, 65, 47, 34

     1, 5, 23, 6, 8, 65, 47, 34

     1, 5, 6, 23, 8, 65, 47, 34

Шаг 4: 1, 5, 6, 23, 8, 65, 47, 34

     1, 5, 6, 8, 23, 65, 47, 34

Шаг 5: 1, 5, 6, 8, 23, 65, 47, 34

     1, 5, 6, 8, 23, 65, 34, 47

     1, 5, 6, 8, 23, 34, 65, 47

Шаг 6: 1, 5, 6, 8, 23, 34, 65, 47

     1, 5, 6, 8, 23, 34, 47, 65

Сортировка выбором.

При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j+1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение.

 

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: 23, 8, 5, 65, 47, 34, 1, 6

     1, 8, 5, 65, 47, 34, 23, 6

Шаг 2: 1, 8, 5, 65, 47, 34, 23, 6

     1, 5, 8, 65, 47, 34, 23, 6

Шаг 3: 1, 5, 8, 65, 47, 34, 23, 6

     1, 5, 6, 65, 47, 34, 23, 8

Шаг 4: 1, 5, 6, 65, 47, 34, 23, 8

     1, 5, 6, 8, 47, 34, 23, 65

Шаг 5: 1, 5, 6, 8, 47, 34, 23, 65

     1, 5, 6, 8, 23, 34, 47, 65

 

Сортировка разделением.

 

1. В исходном неотсортированном массиве выбрать некоторый элемент x = a(k) (барьерный элемент).

2. Переставить элементы массива таким образом, чтобы слева от x оказались элементы массива, меньшие или равные x, а справа ­ элементы массива, большие чем х.

3. Для дальнейшей сортировки необходимо применить п. 1, 2 для каждой из этих частей. И так до тех пор. Пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.

 

Массив: 23, 8, 5, 65, 47, 34, 1, 6

1. Выбираем средний элемент: 23, 8, 5, 65, 47, 34, 1, 6

2. Сортируем вправо от среднего элемента числа больше выбранного, а влево меньше:

23, 8, 5, 65, 47, 34, 1, 6

23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений

23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений

23, 8, 5, 65, 47, 34, 1, 6 – массив без изменений

23, 8, 5, 65, 47, 34, 1, 6 – меняем местами 6 и 65, т.к. 6<34 и 65>34: 23, 8, 5, 6, 47, 34, 1, 65

23, 8, 5, 6, 47, 34, 1, 65– меняем местами 1 и 47, т.к. 1<34 и 47>34: 23, 8, 5, 6, 1, 34, 47, 65

Правая часть упорядочена, теперь выбираем среднее значение для левой части исключая число 34:

23, 8, 5, 6, 1, 34, 47, 65

23, 8, 5, 6, 1, 34, 47, 65 – меняем местами 1 и 23, т.к. 1<5 и 23>5: 1, 8, 5, 6, 23, 34, 47, 65

1, 8, 5, 6, 23, 34, 47, 65 – меняем местами 8 и 5, т.к. 8>5: 1, 5, 8, 6, 23, 34, 47, 65

1, 5, 8, 6, 23, 34, 47, 65 – меняем местами 8 и 6, т.к. 8>6: 1, 5, 6, 8, 23, 34, 47, 65

Пирамидальная сортировка.

Массив: 44, 55, 12, 42, 94, 18, 6, 67

 

обменяли 55 и 12, забыли про 55

просеяли 12 сквозь 44, 42

обменяли местами 44 и 12, забыли про 44

просеяли 12 сквозь 42

обменяли местами 42 и 6, забыли про 42

получили 6, 12, 18.

Сортировка со слиянием.

Два массива: 5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 1

5, 8, 23, 65                    1, 6, 34, 47

Записываем меньшее значение: 5

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 6

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 8

5, 8, 23, 65               1, 6, 34, 47

Записываем меньшее значение: 23

5, 8, 23 ,65                1, 6, 34, 47

Записываем меньшее значение: 34

5, 8, 23 ,65                1, 6, 34, 47

Записываем меньшее значение: 47

Осталось число 65.

Естественное слияние.

Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)

2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше

3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора

4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность.

Массив: 24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40

Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:

(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)

(24) + (08, 13, 17) = (08, 13, 17, 24)

(06, 19, 20) + (11) = (06, 11, 19, 20)

(07, 55) + (33) = (07, 33, 55)

(22) + (18) = (18, 22)

Новый набор чисел:

08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40

Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):

(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)

(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)

(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)

Новый набор:

06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40

Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:

(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)

(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)

Новый набор и его две серии:

(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)

Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:

02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55

ПРИЛОЖЕНИЕ 1

МИНИСТЕРСТВО ПО ОБРАЗОВАНИЮ РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Государственный университет – учебно-научно-производственный комплекс»

 

 

Кафедра ЭВТИБ

 

Контрольная работа

 

по дисциплине «Основы алгоритмизации и программирования»

 

на тему:

 

_____________________________________________

 

 

Выполнил(а) студент(ка)

__________________формы обучения

специальности ___________________

___________курса, _________группы,

вариент: __________________________

______________ _________________

(подпись)

(ФИО)

 

Руководитель работы

______________________ _______________ ________________

(ученая степень, звание, должность)

(подпись)

(ФИО)

 

 

200_ – 200_ уч. г.

ПРИЛОЖЕНИЕ 2

Вариант 1

1. Даны длины сторон треугольника A, B, C. Найти площадь треугольника S.

2. Можно ли на прямоугольном участке застройки размером а и b метров разместить два дома размером в плане р на q и r на s метров? Дома можно располагать только параллельно сторонам участка.

3. Выполнить сортировку с простым включением: 12, 32, 45, 66, 17, 5, 89, 22, 41

4. Выполнить сортировку методом Шелла: 12, 32, 45, 66, 17, 5, 89, 22, 41, 1

5. Выполнить сортировку «методом пузырька»: 12, 32, 45, 66, 92, 17, 5, 89, 22, 41, 1, 100

6. Выполнить сортировку выбором: 12, 32, 45, 66, 92, 17, 5, 89, 22, 41, 1, 100

7. Выполнить сортировку разделением: 12, 32, 45, 66, 92, 17, 5, 89, 22, 41, 1, 100

8. Выполнить сортировку с помощью двоичного дерева: 12, 32, 45, 66, 92, 17, 5, 89, 22, 41, 1, 100

9. Выполнить сортировку со слиянием: 12, 32, 45, 66, 92 5, 17, 22, 41, 89  14, 24, 35, 40, 79

10. Выполнить прямое слияние: 12, 45, 15, 89, 32, 5, 66, 17,

Вариант 2

1. Вычислить площадь трапеции с основаниями а, b и высотой h.

2. Составить алгоритм вычисления функции y(x), при произвольных значениях x:

если ;

    если ;

если .

3. Выполнить сортировку с простым включением: 11, 102, 33, 15, 99, 55, 2, 48, 13

4. Выполнить сортировку методом Шелла: 11, 102, 33, 15, 99, 55, 2, 48, 13, 24

5. Выполнить сортировку «методом пузырька»: 11, 102, 33, 15, 99, 55, 2, 48, 13, 24, 85, 4

6. Выполнить сортировку выбором: 11, 102, 33, 15, 99, 55, 2, 48, 13, 24, 85, 4

7. Выполнить сортировку разделением: 11, 102, 33, 15, 99, 55, 2, 48, 13, 24, 85, 4

8. Выполнить сортировку с помощью двоичного дерева: 11, 102, 33, 15, 99, 55, 2, 48, 13, 24, 85, 4, 75, 63

9. Выполнить сортировку со слиянием: 11, 15, 33, 99, 102  2, 13, 24, 48, 55 4, 63, 75, 85, 100

10. Выполнить прямое слияние: 11, 102, 33, 15, 99, 55, 2, 48

Вариант 3

1. Найти площадь поверхности куба со стороной а.

2. Составить алгоритм нахождения действительных и комплексных корней квадратного уравнения.

3. Выполнить сортировку с простым включением: 13, 39, 10, 112, 85, 32, 55, 11, 71

4. Выполнить сортировку методом Шелла: 13, 39, 10, 112, 85, 32, 55, 11, 71, 14, 59, 44

5. Выполнить сортировку «методом пузырька»: 13, 39, 10, 112, 85, 32, 55, 11, 71, 105

6. Выполнить сортировку выбором: 13, 39, 10, 112, 85, 32, 55, 11, 71, 14, 59, 44

7. Выполнить сортировку разделением: 13, 39, 10, 112, 85, 32, 55, 11, 71, 105

8. Выполнить сортировку с помощью двоичного дерева: 13, 39, 10, 112, 85, 32, 55, 11, 71, 14, 59, 44, 12

9. Выполнить сортировку со слиянием: 10, 13, 39, 85, 112 11, 14, 32, 55, 71 11, 22, 37, 77, 80

10. Выполнить прямое слияние: 13, 39, 10, 112, 85, 32, 55, 11

Вариант 4

1. Даны координаты вершин треугольника А(х₁, у₁), В(х₂, у₂), С(х₃, у₃). Найти его площадь.

2. Даны два числа а, b; выбрать большее из них.

3. Выполнить сортировку с простым включением: 14, 5, 21, 54, 2, 52, 105, 27, 33

4. Выполнить сортировку методом Шелла: 14, 5, 21, 54, 2, 52, 105, 27, 33, 66

5. Выполнить сортировку «методом пузырька»: 14, 5, 21, 54, 2, 52, 105, 27, 33, 66, 6, 44

6. Выполнить сортировку выбором: 14, 5, 21, 54, 2, 52, 105, 27, 33, 66, 6, 44, 102, 17

7. Выполнить сортировку разделением: 14, 5, 21, 54, 2, 52, 105, 27, 33, 66, 6, 44, 102, 17

8. Выполнить сортировку с помощью двоичного дерева: 14, 5, 21, 54, 2, 52, 105, 27, 33, 66, 6, 44, 102, 17, 61

9. Выполнить сортировку со слиянием: 2, 5, 14, 21, 54 27, 33, 52, 66, 105 6, 17, 44, 61, 102

10. Выполнить прямое слияние: 27, 5, 21, 54, 2, 52, 105, 14

Вариант 5

1. Даны координаты вершин треугольника А(х₁, у₁), В(х₂, у₂), С(х₃, у₃). Найти сумму медиан треугольника АВС.

2. Найти наибольшее значение среди трех величин: А, В, С.

3. Выполнить сортировку с простым включением: 150, 102, 130, 114, 205, 116, 100, 145, 122

4 Выполнить сортировку методом Шелла: 150, 102, 130, 114, 205, 116, 100, 145, 122, 18

5. Выполнить сортировку «методом пузырька»: 150, 102, 130, 114, 205, 116, 100, 145, 122, 18, 302, 144

6. Выполнить сортировку выбором: 150, 102, 130, 114, 205, 116, 100, 145, 122, 18, 302, 144, 201

7. Выполнить сортировку разделением: 150, 102, 130, 114, 205, 116, 100, 145, 122, 18, 302, 144, 201, 120

8. Выполнить сортировку с помощью двоичного дерева: 150, 102, 130, 114, 205, 116, 100, 145, 122, 18, 302, 144, 201, 120, 111

9. Выполнить сортировку со слиянием: 102, 114, 130, 150, 205 18, 100, 116, 122, 145       111, 120, 144, 201, 302

10. Выполнить прямое слияние: 22, 41, 59, 101, 85, 36, 92, 48

Вариант 6

1. Даны координаты вершин треугольника А(х₁, у₁), В(х₂, у₂), С(х₃, у₃). Найти внутренние углы треугольника АВС (в градусах).

2. Рассчитать Y.

3. Выполнить сортировку с простым включением: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19

4. Выполнить сортировку методом Шелла: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19, 71, 10

5. Выполнить сортировку «методом пузырька»: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19, 71, 10, 1

6. Выполнить сортировку выбором: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19, 71, 10, 1, 91

7. Выполнить сортировку разделением: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19, 71, 10, 1, 91

8. Выполнить сортировку с помощью двоичного дерева: 16, 84, 65, 94, 44, 6, 48, 59, 34, 19, 71, 10, 1, 91, 9

9. Выполнить сортировку со слиянием: 16, 44, 65, 84, 94, 6, 19, 34, 48, 59     1, 9, 10, 71, 91

10. Выполнить прямое слияние: 16, 59, 44, 94, 65, 6, 48, 84

Вариант 7

1. В квадратной комнате шириной A и высотой B есть окно и дверь с размерами C на D и M на N соответственно. Вычислите площадь стен для оклеивания их обоями. Составьте блок-схему алгоритма решения поставленной задачи.

2.Составить алгоритм для вычисления функции:

3. Выполнить сортировку с простым включением: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5

4. Выполнить сортировку методом Шелла: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5, 29, 50, 202, 20

5. Выполнить сортировку «методом пузырька»: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5, 29, 50

6. Выполнить сортировку выбором: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5, 29, 50

7. Выполнить сортировку разделением: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5, 29, 50

8. Выполнить сортировку с помощью двоичного дерева: 19, 45, 39, 122, 3, 35, 109, 49, 16, 5, 29, 50, 202, 20

9. Выполнить сортировку со слиянием: 3, 19, 39, 45, 122, 5, 16, 35, 49, 109,   20, 29, 50, 90, 202.

10. Выполнить прямое слияние: 19, 45, 39, 122, 3, 49, 109, 35

Вариант 8