Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа № 7
Цель работы. Получение практических навыков при работе со сложными типами данных – векторами
Массив – это совокупность конечного числа данных одного типа. Простейшим примером массива может служить линейная таблица. Значения, образующие линейную таблицу, являются элементами массива, а их порядковые номера в таблице называются индексами. Можно сказать, что одномерный массив соответствует понятию вектора. Индекс определяет положение элемента массива относительно его начала.
Общая форма описания переменной:
var<имя>:array |<тип-индексов>| of<тип-элементов>
Выбор отдельной компоненты одномерного массива осуществляется указанием идентификатора массива, за которым в квадратных скобках следует индексное выражение. Индексное выражение должно давать значение, лежащие в диапазоне, определяемом типом индекса. Например: M[1],M[2],…,M[n].
Для организации автоматического ввода случайных значений следует воспользоваться функцией random(n). Эта функция возвращает случайное число из диапазона от 0 до n–1. Для этого необходимо в основной программе инициализировать датчик случайных чисел командой randomize.
Формат вызова функций Random:
random(m), где m – значение, указывающее на правую границу диапазона выдаваемых значений.
Например, требуется заполнить одномерную таблицу размерностью 10, числами на диапазоне от 0 до 10.
program vector_full;
const n=10;
type vector=array[1…n] of integer;
var v:vector;
procedure enter(var vect: vector);
var i: integer;
begin
for i: =1 to n do
vect[i]:=random(11);
end;
begin
randomize;
enter(v);
end.
Задание. По заданному условию сформировать одномерный массив (вектор), вывести на печать и произвести операции по обработке полученных компонент массива. Для всех вариантов исходными данными являются одномерный массив, элементы которого задаются с помощью датчика случайных чисел от – 50 до +50, и целое положительное число К.
Вариант 1. Определить число элементов массива, больших К.
Вариант 2. Вычислить сумму первых К элементов массива с нечетными индексами.
Вариант 3. Найти произведение двух соседних элементов массива, наиболее близкое по модулю к К.
Вариант 4. Вычислить произведение последних K элементов массива.
Вариант 5. Найти сумму элементов массива с нечетными индексами, по модулю меньших К.
Вариант 6. Вычислить максимальную разность между К и суммой двух соседних элементов массива.
Вариант 7. Определить число элементов массива с четными индексами, по модулю не меньших К.
Вариант 8. Найти сумму тех элементов массива с нечетными индексами, каждый из которых по модулю меньше К.
Вариант 9. Найти разность между К и суммой всех положительных элементов массива с четными индексами.
Вариант 10. Определить индекс элемента массива, наиболее близкого к К.
Вариант 11. Определить число элементов массива, меньших К.
Вариант 12. Вычислить сумму последних К элементов массива с четными индексами.
Вариант 13. Найти произведение двух соседних элементов массива, наиболее удаленное по модулю от К.
Вариант 14. Найти произведение модулей первых К элементов массива.
Вариант 15. Найти сумму элементов массива с четными индексами, значение которых превышает К.
Вариант 16. Вычислить минимальную разность между К и суммой модулей двух соседних элементов массива.
Вариант 17. Определить индекс элемента массива, наиболее отдаленного от К.
Вариант 18. Найти сумму трех соседних элементов массива наиболее отдаленную от К.
Вариант 19. Найти разность между К и суммой всех положительных элементов массива с четными индексами.
Вариант 20. Найти сумму тех элементов массива с четными индексами, каждый из которых по модулю не превосходит К.
Цель работы. Научиться использовать различные алгоритмы упорядочивания.
Рассмотрим массив целых или действительных чисел А1,…,Аn. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по возрастанию А1< А2<…< Аn . Эта задача называется задачей сортировки или упорядочение массива. Для решения этой задачи можно воспользоваться следующими алгоритмами (другие варианты упорядочения, например, по убыванию А1> А2>…> Аn, различаются незначительно):
Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk>Ak-1, то элементы этой пары меняются местами; просмотр продолжается до Аn. В результате первого просмотра наибольший элемент оказывается на первом месте. Второй просмотр начинается с первого элемента и заканчивается элементом Аn-1. алгоритм заканчивается, когда в просмотре участвуют только два первых элемента.
Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk>Ak-1, то элементы меняются местами; после чего просмотр начинается с начала массива. Алгоритм заканчивается, когда в результате очередного просмотра не удается найти упорядоченной пары.
Из элементов массива выбирается минимальный и меняется местами с первым элементом. В результате первого выбора минимальный элемент оказывается на первом месте. Второй выбор минимума начинается со второго элемента. Далее процесс возобновляется до тех пор, пока среди выбираемых не останутся два последних элемента.
Применяется в этом случае, когда часть массива уже упорядочена. Просматриваются последовательно А2,…,An и каждый новый элемент Ai вставлять на подходящее место в уже упорядоченную совокупность A1…Ai-1. Это место определяется последовательным сравнением Ai с упорядоченными элементами A1…Ai-1.
Применяется, как и предыдущий метод, в тех случаях, когда часть массива уже упорядочена. Отличие от сортировки простыми вставками заключается в том, что позиция, в которую «вставляется» очередной элемент, определяется не последовательным сравнением, а алгоритм деления пополам.
Выбрать «средний» элемент массива. Затем переставить остальные элементы таким образом, чтобы слева от выбранного элемента оказались все элементы меньшие его, а справа – все элементы больше его. Тем самым выбранный элемент окажется «на своем месте». После чего следует рекурсивно применить данный алгоритм к частям массива справа и слева от очередного среднего.
Метод основан на многократных слияниях уже упорядоченных групп элементов массива. В начале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой. Слиянием соседних групп получают упорядоченные группы по два элемента (кроме, может быть, последней, если для неё не нашлось парной). Далее упорядоченные группы укрупняют тем же способом. Схематично это можно представить так (рисунок 15). Вначале происходит слияние групп по одному элементу. Образовались упорядоченные группы по 2 элемента. Далее процесс продолжается для укрупненных групп.
Рисунок 1. Пример сортировки фон Неймана
Задание. Для всех вариантов исходными данными являются одномерный массив, элементы которого задаются с помощью датчика случайных чисел от – 50 до +50. Варианты 1, 2, 3 4 и 5 используют сортировку простыми вставками, варианты 6, 7, 8, 9 и 10 сортировку обменами I, варианты 11, 12, 13, 14 и 15 – сортировку выбором, варианты 16, 17, 18, 19 и 20 – сортировку обменами II. Желающие получить повышенный балл могут использовать сортировку бинарными вставками, «быструю сортировку» или сортировку фон-Неймана.
Вариант 1, 6, 11, 16. Даны целые числа al,...,an. Получить в порядке возрастания различные числа из этого массива.
Вариант 2, 7, 12, 17. Даны целые числа al,...,an. Упорядочить массив по возрастанию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.
Вариант 3, 8, 13, 18. Даны целые числа al,...,an. Получить в порядке убывания различные числа из этого массива.
Вариант 4, 9, 14, 19. Даны целые числа al,...,an. Упорядочить массив по убыванию. Удалить из массива элемент с номером k, затем вставить число b так, чтобы упорядоченность не нарушалась. Числа k и b вводятся с клавиатуры.
Вариант 5, 10, 15, 20. В массиве al,...,an переставить числа таким образом, чтобы вначале шли элементы большие al, упорядоченные по возрастанию, затем сам элемент al, затем элементы меньшие al, упорядоченные по убыванию.