Информатика, номера задач

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

СЕМЕСТР 2

Гр. РТ1101-03 Лектор Мацкевич А.Г.

Номера задач из задачника: Абрамов.«Задачи по программированию»

Таб. 1

№	Модули, сортировка(1)	Строки Pascal	Текст. файлы	Типиз. файлы	Строки PChar	Графика, окна, диалоги(2)
1	628а,628б	251,814в	501а	506а,б	814в	1
2	628а,628в	252,820-3	502а	506в,г	820-3	2
3	628а,633	253а,б,820-2	502б	506д,е	820-2	3
4	628а,636	254,820-1	503	507а,б	820-1	4
5	628а,642	255,819	504а	507в,г	819	5
6	628б,628в	256,817	504б	507ж	817	6
7	628б,633	257а,б,816	504в	508а	816	7
8	628б,636	257г,д,815	504г	508б	815	8
9	628б,642	258,818	518	509а	818	9
10	642,628а	259,814а,б	519а	510	814	10
11	636,628а	260а,б,813	519б	511а	813	11
12	633,628а	261,812д,е	520	512	812	12
13	628в,628а	262,812в,г	521	513а	812	13
14	628б,628а	263,811	522	514а	811	14
15	628б,628в	264,810	523а	515	810	15
16	628б,633	265,809	523б	516	809	16
17	628б,636	266,808в,г	524	517а,б	808	17
18	628б,642	267,808а,б	525	517д,е	808	18
19	628а,628б	268,807	526	517ж	807	19
20	628а,628в	269а,б,806	527	517в,г	806	20
21	628а,633	269в,г,805	528	514б	805	21
22	628а,636	269д,е,804	529а	513б	804	22
23	628а,642	270а,б,803	530а	511б	803	23
24	628б,628в	270в,г,802	530б	509б	802	24
25	628б,633	270д,812а,б	530в	507д,е	812	25

(1) Модули, сортировка

Написать подпрограммы, реализующие методы сортировки из таб.1 . Организовать модуль ( unit ) с этими подпрограммами. Написать программу для сортировки массива из 50-100 элементов этими методами. Сравнить методы сортировки по количеству перестановок и количеству сравнений. Сделать выводы.

Алгоритмы сортировки массива.

( Номера соответствуют задачам из «Задачи по программированию ». С.А. Абрамов. 1988 г.)

№628а. (Сортировка выбором)

Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д.

№628б. (Сортировка обменами, метод пузырька)

Последовательным просмотром чисел а₁, …, а_n найти наименьшее i такое, что а_i > a_i+1 . Поменять a_i и а_i+1 местами, возобновить просмотр с элемента a_i+1 и т.д. Тем самым наибольшее число передвигается на последнее место. Следующие просмотры начинать опять с начала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.

№628в (Сортировка простыми вставками)

Просматривать последовательность а₁, …, а_n и каждый новый элемент a_i вставлять на подходящее место в уже упорядоченную совокупность а₁, …, а_i-1. Это место определяется последовательны сравнением а_i с упорядоченными элементами а₁, …, а_i-1.

№633 (Сортировка бинарными вставками)

Алгоритм упорядочения простыми вставками (№628в) можно изменить следующим образом. Место, на которое надо вставить а_i в уже упорядоченную совокупность а₁, …, а_i-1 определяется алгоритмом деления пополам. Для этого надо взять первоначально 1 и i в качестве границ поиска места элемента. Далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигать эти границы следующим образом: сравнить a_i с a_s , где s –целая часть среднего арифметического границ. Если a_s < a_i , то заменить прежнюю нижнюю границу на s+1, а верхнюю оставить без изменения, иначе оставить без изменения нижнюю границу, а верхнюю заменить на s. Когда границы совпадут, став равными некоторому числу t, выполнение алгоритма закончиться с результатом t.

№636 (Алгоритм фон Неймана, сортировка слияниями)

Алгоритм фон Неймана упорядочивания массива a₁, a₂, …,a_n по не убыванию основан на многократных слияниях уже упорядоченных групп элементов массива. Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждом. Слияниям соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента ( кроме, может быть, последней группы, которой не нашлось парной). Далее упорядоченные группы укрупняются тем же способом и т.д. Здесь приходится оперировать не только с массивом a₁, a₂,…,a_n, но и с вспомогательным массивом b₁,b₂,…,b_n.

№642 ( Сортировка обменами 2)

Последовательным просмотром чисел a₁,a₂,…,a_n найти наименьшее i такое, что a_i>a_i+1. Поменять a_i и a_i+1 местами возобновить просмотр с начала массива. Когда не удается найти такое i, массив будет упорядочен.

(2) Задание будет уточнено позже.