Лабораторная работа 1
РАБОТА С ОДНОМЕРНЫМИ МАССИВАМИ. АЛГОРИТМЫ СОРТИРОВКИ
Цель и содержание:приобретение практических навыков в составлении программ с одномерными массивами.
Теоретическое обоснование
Массивы – структурированный тип данных с элементами одного типа, имеющий одно имя и определенное количество элементов. Количество элементов определяет размер массива. Например, массив составляют номера зачетных книжек студентов, здесь число элементов равно числу студентов; массив образуют набор чисел, их количество равно числу элементов массива. Порядковый номер элемента массива называется его индексом. Массив может иметь не один, а большее число индексов. Число индексов называется размерностью массива, например, массив с двумя индексами называется двумерным массивом. Строка символов является массивом символов, вектор – массив вещественных чисел, матрица – массив векторов.
Обработка массивов выполняется в следующем порядке: описание, ввод или инициализация элементов массива, преобразование и вывод.
При описании массивов после имени в квадратных скобках указывается число его элементов. В языке Си индекс элемента массива начинается с нуля, поэтому индекс последнего элемента массива на 1 меньше числа элементов в данном массиве.
Ввод и вывод элементов массива выполняется с использованием операторов цикла. Например, массив Х из 10 элементов можно ввести через форматный или потоковый ввод следующим образом:
Int i, Х [10];
for (i=0; i
Или
for (i=0; i X[[i]};
Манипулятор endl (сокращение end line) выполняет переход на новую строку при выводе значений.
Вывод элементов массива можно выполнить в строку или в столбец. Для вывода элементов массива Х [10] в строку:
for (i=0; i
Или
for (i=0; i
Для вывода в столбец надо написать:
printf ( %6d \n, a[i] ); или cout
Сортировка элементов массивов.Сортировка– это процесс обработки последовательности данных с целью их перестановки в определенном порядке: в порядке убывания значений или в порядке возрастания. Главными требованиями к алгоритмам сортировки массивов являются экономное использование памяти и быстродействие. Методы сортировки, в зависимости от способа перемещения элементов массива, делятся на три основных вида: включением, выбором, обменом. Рассмотрим наиболее распространенные методы.
Метод «пузырька» один из самых простых методов внутренней сортировки. На рисунке 4.1 представлена сортировка массива по возрастанию.
Суть алгоритма состоит в последовательном просмотре массива от конца к началу или от начала к концу и сравнении каждой пары элементов между собой. Если Х[i] и Х[i+1] не упорядочены, то их значения меняются местами. Если элементы массива переставлялись хотя бы единожды во время просмотра всего массива, то процесс сравнения каждой пары элементов повторяются заново. При сортировке по возрастанию «легкие» элементы с меньшим значением как бы «всплывают» к началу массива подобно тому, как это делают пузырьки воздуха в стакане с водой – отсюда и происходит популярное название алгоритма.
Метод сортировки выбором элементапредставленалгоритмом на рисунке 4.2.
| нет |
| да |
Рисунок 4.2 – Алгоритм сортировки выбором минимального элемента
В первую очередь определяется наименьший элемент (для сортировки по убыванию – наибольший) и его координата в заданном массиве. Этот элемент меняется местами с первым элементом массива Х. Затем определяются наименьший (наибольший) элемент и его координата среди оставшихся n-1 элементов. Он меняется со вторым элементом. Данная процедура повторяется со всеми оставшимися элементами, пока не останется только один наибольший (наименьший) элемент. В результате все элементы упорядочиваются.
Методика и порядок выполнения работы
1. Изучите теоретическое обоснование.
2. Выполните пример программы обработки одномерного массива:
Дан массив из 50 целых чисел. Найти наибольший элемент в массиве и его порядковый номер.
# include
# define n 50 // определение константы n=50
int max, nom, a[n]; //описание массива целых чисел из n элементов
main(){
for (i=0; i
max= a[0]; nom=1; // полагаем первый элемент наибольшим
for (i=1; i
if (max
printf(\n Вывод элементов исходного массива : \n);
for (i=0; i
printf (\n Максимальное число в массиве %d, его индекс %d\n , max, nom);
return 0;}
Пояснение. По окончании цикла переменная max будет иметь значение, равное максимальному элементу массива, а nom – порядковый номер этого элемента. Вывод элементов массива выполняется в строку.
3. Составьте алгоритмы и программы с применением массивов согласно вариантам задания 1 и задания 2, введите исходные данные, проверьте полученный результат. Исходные и результативные массивы вывести.
Таблица 4.1– Варианты заданий 1 и 2
| № варианта | Условия заданий |
| | 1) Все элементы массива А,которые больше 7 и меньше 20, переписать в новый массив. 2)Дан массив из N целых чисел. Отсортировать его по убыванию элементов методомпузырька |
| | 1) Из элементов массива А, получить массив положительных имассив отрицательных элементов. 2)Дан массив из N целых чисел. Отсортировать его по убыванию элементов методом выбора |
| | 1) Дан массив чисел В[0:N]. Вывести на печать первый отрицательный элемент массива иего порядковый номер. 2) Дан массив из N целых чисел. Получить изнего массив положительных чисел и отсортировать его по возрастанию методомпузырька |
| | 1) Дан массив чисел. Найти значение максимальногоэлемента. Если таких элементов несколько, то определить, сколько их. 2) Дан массив из N целых чисел. Получить изнего массив отрицательных чисел и отсортировать его по возрастанию методом выбора |
| | 1) Дан массив A[0:N].Вычислить среднее арифметическое всех чисел массива с нечетными индексами,количество чисел равных нулю. Получить массив отрицательных чисел. 2)Дан массив из N целых чисел. Получить из него массив положительных чисел иотсортировать его по убыванию методом пузырька |
| | 1) Дан массив A[0:N].Вместо отрицательных элементов массива записать 0. Получить массив положительных чисел. 2)Дан массив из N целых чисел. Получить из него массив отрицательных чисел иотсортировать его по убыванию методом выбора |
| | 1)В массиве вещественных чисел изменить знак отрицательныхчисел, после этого определить максимальный по величине элемент массива и егономер в массиве. 2)Дан массив из N целых чисел. Получить из него массив положительных чисел иотсортировать его по возрастанию методом пузырька |
| | 1) Дан массив чисел В[0:N]. Найти сумму отрицательных чисел и количество положительныхчисел массива с четными индексами. 2)Дан массив из N целых чисел. Получить из него массив отрицательных чисел иотсортировать его по возрастанию методом выбора |
| | 1) Дан массив чисел В[0:N]. Найти сумму положительных и отрицательных чисел массива снечетными индексами и количество элементов массива равных нулю 2)Дан массив из N целых чисел. Получить из него массив положительных чисел иотсортировать его по убыванию методом пузырька |
| | 1) Дан массив A[0:N].Определить количество отрицательных чисел с нечетными индексами. Найтиминимальный элемент массива. 2)Дан массив из N целых чисел. Получить из него массив отрицательных чисел иотсортировать его по убыванию методом выбора |
| | 1) Дан массив A[0:N].Найти сумму всех положительных элементов массива, а также среднееарифметическое всех чисел 2) Дан массив из N целых чисел. Получить из него массив чисел больших 15 и отсортировать его поубыванию методом пузырька |
| | 1) Дан массив чисел В[0:N]. Вычислить сумму и количество элементов массива, расположенных послепоследнего элемента, равного нулю. 2) Дан массив из N целых чисел. Получить из него массив чисел меньших 15 и отсортировать его повозрастанию методом пузырька |
| | 1) Дан массив A[0:N].Найти сумму всех отрицательных элементов, количество чисел, равных нулю ивычислить среднее арифметическое только положительных чисел. 2) Дан массив из N целых чисел. Получить из него массив чисел больших 10 иотсортировать его по возрастанию методом выбора |
| | 1) Дан массив чисел В[0:N]. Найти сумму и вычислить среднее арифметическое всех чиселмассива с четными индексами. 2) Дан массив из N целых чисел. Получить из него массив чисел меньших 20 и отсортировать его поубыванию методом быстрой сортировки |
| | 1) Дан массив A[0:N].Вычислить произведение между первым и последним положительными элементами 2) Дан массив из N целых чисел. Получить из него массив чисел меньших 20 и отсортировать его поубыванию методом выбора |
| | 1) Дан массив из N чисел. Найти наибольшийэлемент массива и поменять его местами с наименьшим элементом. 2) Дан массив из N целых чисел. Получить из него массив чисел, кратных 3 и отсортировать его по возрастанию методомпузырька. В полученном отсортированноммассиве выполнить поиск введенного с клавиатуры значения быстрымпоиском |
| | 1) Дан массив чисел В[0:N]. Записать подряд в массив А элементы массива В, имеющиечетные индексы, а имеющих, нечетные индексы – в массив У. 2) Дан массив из N целых чисел. Получить из него массив чисел, кратных 4 и отсортировать его поубыванию методом выбора. В полученном отсортированном массиве выполнить поиск введенного склавиатуры значения быстрым поиском. |
| | 1)Насколько каждый элемент массива А отличается от среднеарифметического значения элементов этого массива. 2) Дан массив из N целых чисел. Получить из него массив отрицательных и массивположительных чисел. Первый из массивовотсортировать по убываниюметодом выбора, а второй методом пузырька по возрастанию |
| | 1). Дан массив чисел В[0:N]. Найти сумму и произведение положительных элементов массива,расположенных до максимального элемента 2) Дан массив из N целых чисел. Получить из него массив отрицательных и массивположительных чисел. Первый из массивовотсортировать по убываниюметодом быстрой сортировки, а второй по возрастанию методом выбора |
| | 1) Дан массив чисел В[0:N]. Найти произведение элементовмассива, расположенных между максимальным и минимальным элементами. 2)Дан массив из N целых чисел. Получить из него массив нечетных чисел и отсортировать его по возрастаниюметодом выбора. Найти повторяющиеся числа в полученном массиве и посчитать ихколичество. |
| | 1) Найти наибольший элемент каждойпары из массива А и записать их вновый массив 2) Дан массив из N целыхчисел. Получить из него массив отрицательных и массив положительных чисел.Первый из массивов отсортировать по возрастанию методом быстрой сортировки,а второй по убыванию методом пузырька |
Содержание отчета и его форма
Выполните все описанные пункты задания, письменно оформите отчет, который должен содержать:
-тему, цель лабораторной работы;
-условия, блок–схемы, программы и результаты выполнения задания1 и задания 2.
Контрольные вопросы и защита работы
1.Что такое массив, индекс элемента массива?
2.Какие виды массивов?
3.В каком порядке выполняется обработка массивов?
4. Как ввести и вывести элементы одномерных массивов в строку и в столбец?
5.Способы описания и инициализации массивов.
Защита лабораторной работы включает в себя демонстрацию выполненных программ, подготовленный отчет и устный ответ на контрольные вопросы.
| # includeint sum, nom, a[n]; //описание массива целых чисел из nэлементов cout« Введите кол-во элементов массива; cin » n; main(){ for (i=0;i |