Лабораторная работа № 6 Алгоритмы обработки одномерных массивов. (сортровка и разбиение). 2

Содержание

Лабораторная работа № 6 АЛГОРИТМЫ ОБРАБОТКИ ОДНОМЕРНЫХ МАССИВОВ. (СОРТРОВКА И РАЗБИЕНИЕ)................................................. 2

6.1 КРАТКАЯ ТЕОРИЯ........................................................................... 2

6.1.1. СОРТИРОВКА ОДНОМЕРНЫХ МАССИВОВ........................ 2

6.1.2. РАЗБИЕНИЕ ОДНОМЕРНЫХ МАССИВОВ............................ 5

6.2 ЗАДАНИЯ........................................................................................... 6

Лабораторная работа № 6
АЛГОРИТМЫ ОБРАБОТКИ ОДНОМЕРНЫХ МАССИВОВ. (СОРТРОВКА И РАЗБИЕНИЕ)

Содержание

Цель работы – дальнейшее знакомство с типовыми алгоритмами работы с одномерными массивами такими, как сортировка и разбиение.

6.1 КРАТКАЯ ТЕОРИЯ

6.1.1. СОРТИРОВКА ОДНОМЕРНЫХ МАССИВОВ

Сортировка – это расположение чисел в порядке возрастания или убывания.

Наиболее распространенный и простой метод сортировки – метод "пузырька". Он требует минимального объема памяти для данных, но затраты времени на этот метод велики. Суть метода "пузырька" в следующем.

Пусть дано n чисел и необходимо расположить их (для определенности) в порядке возрастания. При упорядочении выполняются следующие операции:

1) числа сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1)-ым;

2) если меньшее стоит в паре на втором месте, то числа меняются местами.

За один такой просмотр массива минимальное число "вытолкнется", по крайней мере, на одно место вверх (вперед), а максимальное – переместится в самый конец (вниз). Т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда – название метода. За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в нем. Рассмотрим работу метода на примере, приведенном на рис. 6.1.

Содержание

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

1. Ввести массив из n чисел.

2. Для номера просмотра k= 0 до k < n –1.

2.1. Для номера числа i= 0 до i<n –1.

Если число[i] > число[i+1], то поменять их местами.

3. Вывести отсортированный массив.

4. Закончить.

– исходный массив

перестановки в
первом просмотре

– после первого просмотра

– после второго просмотра

перестановки в
третьем просмотре

– после третьего просмотра

перестановки в
четвертом просмотре

– после четвертого просмотра

В пятом просмотре перестановок нет. Сортировка окончена.

– отсортированный массив

Рис 6.1

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

for (int k = 0; k< x.length – 1; k++)

for (int i = 0; i < x.length –k; i++)

if…

Содержание

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

В алгоритме используется переменная «перестановка_есть», которой сначала присваивается значение «истина», а как только в одном из просмотров не будет перестановок – ей присваивается значение «ложь». Это позволяет прервать выполнение цикла while.

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

1. Ввести массив x из n элементов.

2. Признак перестановка_есть = истина.

3. Номер просмотра к =0.

4. Пока перестановка _ есть = истина выполнять

4.1. количество_перестановок =0.

4.2. Для i от 0 до i< n-k

Если x [i] > x [i+1], то

4.2.1. поменять x [i] и x [i+1]

4.2.2. количество_перестановок++

4.3. Если количество_перестановок=0

признак перестановка_есть =ложь.

4.4. к ++

5. Вывести массив x.

6. Закончить.

Содержание

6.1.2. РАЗБИЕНИЕ ОДНОМЕРНЫХ МАССИВОВ

Разбиение одномерного массива рассмотрим на приведенном ниже примере.

Пример 6.1. Ввести в ЭВМ массив а0 из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа во 2-ой – положительные согласно приведенному алгоритму.

Алгоритм.

1.Задать количество элементов k0 исходного массива а0.

2. Ввести массив а0.

3. Вывести исходный массив.

//разбиение на 2 массива а1 и а2

4. Принять k1= –1 // количество отрицательных чисел

5. Принять k2= –1 // количество положительных чисел

6. Для номера элемента (i) от 0 до n –1

Если a0[i]<0 то

k1=k1+1;

a1[k1]= a0[i]

Иначе

k2=k2+1;

a2[k2]= a0[i]

7. Если в 1-ом массиве количество элементов k1 > –1 то

переписать значимые элементы массива а1 в массив а11 размерностью k1

иначе выдать сообщение об отсутствии отрицательных элементов

8. Если во 2-ом массиве количество элементов k2 > –1 то

переписать значимые элементы массива а2 в массив а22 размерностью k2

иначе выдать сообщение об отсутствии положительных элементов

9. Вывести массив а11

10. Вывести массив а22.

11. Закончить.

6.2 ЗАДАНИЯ

Вариант 1

1. Ввести в ЭВМ массив f из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить положительные числа, во 2-ой - отрицательные

2. Создать 3 массива (а1,а2,а3) из n целых чисел (n <= 50). Для двух первых массивов ввести значения с клавиатуры и упорядочить их: один по убыванию (1-й способ), другой по возрастанию (2-й способ). Третий массив заполнить значениями согласно следующему правилу:

а3[i] =а1[i] +а2[i],

где i – номер элемента

Вариант 2

1. Ввести в ЭВМ массив mas из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить четные числа, во 2-ой - нечетные

а3[i] =а1[i] – а2[i],

где i – номер элемента

Вариант 3

1. Ввести в ЭВМ массив x из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить числа, которые делятся на 3, во 2-ой - числа, которые не делятся на 3

а3[i] =а1[i] *а2[i],

где i – номер элемента

Содержание

Вариант 4

1. Ввести в ЭВМ массив q из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа, во 2-ой – положительные числа

а3[i] =а1[i] +а2[i],

где i – номер элемента

Вариант 5

1. Ввести в ЭВМ массив p из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить числа, которые делятся на 5, во 2-ой - числа, которые не делятся на 5

а3[i] =а1[i] – а2[i],

где i – номер элемента

Вариант 6

1. Ввести в ЭВМ массив m из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа, во 2-ой – положительные числа

а3[i] =а1[i] *а2[i],

где i – номер элемента

Содержание

Вариант 7

1. Ввести в ЭВМ массив z из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить нечетные числа, во 2-ой –четные

а3[i] =а1[i] +а2[i],

где i – номер элемента

Вариант 8

1. Ввести в ЭВМ массив x из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа, во 2-ой – положительные

а3[i] =а1[i] –а2[i],

где i – номер элемента

Вариант 9

1. Ввести в ЭВМ массив ar из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить числа, которые делятся на 7, во 2-ой - числа, которые не делятся на 7

а3[i] =а1[i] *а2[i],

где i – номер элемента

Вариант 10

Содержание

1. Ввести в ЭВМ массив mas из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа, во 2-ой – положительные числа

а3[i] =а1[i] +а2[i],

где i – номер элемента

Вариант 11

1. Ввести в ЭВМ массив y из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить числа, которые делятся на 5, во 2-ой - числа, которые не делятся на 5

а3[i] =а1[i] –а2[i],

где i – номер элемента

Вариант 12

1. Ввести в ЭВМ массив b из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить положительные числа, во 2-ой – отрицательные числа

а3[i] =а1[i] *а2[i],

где i – номер элемента

Содержание

Вариант 13

1. Ввести в ЭВМ массив p из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить числа, которые делятся на 3,во 2-ой - числа, которые не делятся на 3

а3[i] =а1[i] +а2[i],

где i – номер элемента

Вариант 14

1. Ввести в ЭВМ массив y из n целых чисел (n <= 50). Разбить исходный массив на два: в 1-ый поместить отрицательные числа, во 2-ой – положительные числа

а3[i] =а1[i] –а2[i],

где i – номер элемента

Дата добавления: 2015-10-21; просмотров: 14 | Нарушение авторских прав

<== предыдущая лекция	\|	следующая лекция ==>
	\|	Я был крещен и воспитан в православной христианской вере. Меня учили ей и с детства, и во все время моего отрочества и юности. Но когда я 18-ти лет вышел со второго курса университета, я не верил 1 страница

mybiblioteka.su - 2015-2024 год. (0.048 сек.)