Цель работы: Закрепить навыки программирования на языке Паскаль алгоритмов обработки массивов. Изучить методы сортировок: простого обмена, простой выборки, простой вставки.
Контрольные вопросы:
1. Какие виды сортировок бывает?
2. В каком разделе программы надо написать описание данных?
3. Как определяется общее число элементов массива?
4. Что такое индекс? Как осуществляется сотрировка?
Задачи:
1. Дан вектор 
. Упорядочить компоненты вектора так, чтобы сначала размещались все отрицательные компоненты, а затем положительные.
2. Найти среднее арифметическое элементов массива 
, предшествующих первому отрицательному элементу 
. Все элементы массива сортируйте по убыванию.
3. В массиве 
вычислить сумму отрицательных, произведение положительных и количество нулевых элементов. Отрицательные элементы массива сортируйте по убыванию.
4. Ввести массив 
. Подсчитать количество всех чисел, расположенных в промежутке [-1,1] и сумму всех остальных. Все элементы в данном отрезке сортируйте по возрастанию.
5. Дан массив 
. Создать и сортировать по возростанию новый массив 
элементы которого вычисляются следующим образом: 
.
6. Имеется функция, заданная таблицей 
на отрезке [ 
]. Для произвольного аргумента 
, вычислить соответствующее значение 
, воспользовавшись формулой линейной интерполяции 
, где 
. Все элементы массива сортируйте по убыванию.
7. Дан массив 
. В элемент 
, содержащий наименьшее значение, записать среднее арифметическое значение элементов массива.
8. В массиве 
подсчитать количество нулевых элементов k и вычислить k!.
9. Дан массив 
. Все элементы, стоящие после 
, имеющего наибольшее значение, заменить нулями. Полученный массив сортируйте по возрастанию.
10. Дан массив 
. Вычислить сумму 
. Все элементы массива сортируйте по убыванию.
11. Дан массив 
. Найти произведение всех элементов, значения которых меньше 50, и сложить его с произведением элементов больших 100.
12. Даны два массива 
и 
. На место массива X записать массив Y, а на место массива Y – массив X. Все элементы двух массивов сортируйте по возрастанию.
13. Написать программу, которая проверяет, представляют ли элементы введенного с клавиатуры массива неубывающую последовательность.
14. Написать программу, которая определяет количество студентов в группе, чей рост превышает средний.
15. Даны целые числа 
. Если в данной последовательности ни одно четное число не расположено после нечетного, то получить все отрицательные члены последовательности, иначе – все положительные.
16. Даны действительные числа . Оставить без изменения последовательность , если она упорядочена по не убыванию или не возрастанию; в противном случае удалить из последовательности те члены, порядковые номера которых кратны четырем, сохранив прежним порядок остальных членов.
17. Даны действительные числа . Выяснить, имеются ли среди чисел совпадающие, и если есть, то определить их количество и порядковые номера.
18. Даны вектора и 
. Получить вектор с, компонентами которого являются 
. Найти минимальный и максимальный элемент вектора c и их порядковые номера.
19. Даны целые числа , среди которых могут быть повторяющиеся. Выяснить, сколько чисел входит в последовательность по одному разу.
20. Даны целые числа 
. Найти три натуральных числа i, j, k, каждое из которых не превосходить десяти, такие что 
. Если таких чисел нет, то сообщить об этом.
Литературы:
Основная литература:
8. Абрамов В.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. - М.: Наука, 1988. - 320 с.
9. Абрамов С.А., Зима Е.В. Начала программирования на языке Паскаль. - М.: Наука, 1987. - 112 с.
10. Вирт Н. Алгоритмы и структуры данных./Пер. с англ. М.: Мир, 1989. - 360 с.
11. Грогоно П. Программирование на языке Паскаль. - М.: Мир, 1982. - 382 с.
12. Дантеманн Дж., Мишел Дж., Тейлор Д. Программирование в среде Delphi: Пер. с англ. - Киев: НИПФ “ДиаСофтЛтд.”, 1995. - 608 с.
13. Епанешников, Фолкнер Д.Р. Delphi: Пер.с англ.- М.: БИНОМ, 1995. - 464 с.
14. Орлик С.В. Секреты Delphi на примерах: - М.: БИНОМ. - 316 с.
Дополнительная литература:
6. Перминов О.Н. Программирование на языке Паскаль. - М.: Радио и связь, 1988. - 224 с.
7. Пильшиков В.Н. Сборник упражнений по языку Паскаль: Учеб. пособие для вузов. - М.: Наука, 1989. - 160 с.
8. Прайс Д. Программирование на языке Паскаль: Практ. руководство. - М.: Мир, 1987. - 232 с.
9. Рубенкинг Н. Турбо Паскаль для Windows: В 2 т.; Пер. с англ. - М.: Мир, 1993. - 536 с.
10. Фаронов В.В. Турбо Паскаль. В 3-х книгах. Книга 1. Основы Турбо Паскаля. - М.: Учеб.-инж.центр МВТУ-ФЕСТО ДИДАКТИК, 1992. - 304 с.
11. Фаронов В.В. Паскаль и Windows. - М.: Учеб.-инж.центр МВТУ-ФЕСТО ДИДАКТИК, 1994. - 539 с.
Методические указания:
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
· количество шагов алгоритма, необходимых для упорядочения;
· количество сравнений элементов;
· количество перестановок, выполняемых при сортировке.
Мы рассмотрим только три простейшие схемы сортировки.
По-видимому, самым простым методом сортировки является так называемый метод " пузырька ". Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
· если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
· при встрече с более "тяжелым" элементом, последний становится " эталоном " для сравнения, и все следующие сравниваются с ним.
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j -го прохода не проверяются элементы, стоящие на позициях выше j.
Второй метод называется метод вставок, т.к. на j-ом этапе мы "вставляем" j-ый элемент M[j] в нужную позицию среди элементов M[1],M[2],..., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Чтобы сделать процесс перемещения элемента M[j], более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0], чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.
Если барьер не использовать, то перед вставкой M[j], в позицию i-1 надо проверить, не будет ли i=1. Если нет, тогда сравнить M[j] (который в этот момент будет находиться в позиции i) с элементом M[i-1].
Решение задачи: