Лабораторные работы

Метод «пузырька». Данный метод относится к сортировкам обменом. Метод «пузырька» получил своё название оттого, что продвижение максимальных элементов массива к его вершине происходит постепенно, подобно всплытию пузырька на поверхность воды. Этот метод требует нескольких проходов массива. На каждом проходе сравнивается пара соседних друг с другом элементов.

Если пара расположена в порядке возрастания, переставляем эти элементы местами. В противном случае элементы остаются на исходных позициях. Процедура должна быть повторена n-1 раз для гарантированного достижения результата. Пример поэтапной работы алгоритма показан на рис. 3. Изображенные на каждом проходе перестановки должны выполняться последовательно слева направо.

проход 1

0

5

3

7

9

проход 2
	5	3	7	9	0
проход 3
	5	7	9	3	0
проход 4
	7	9	5	3	0
итог	9	7	5	3	0

Рис. 3. Алгоритм сортировки «пузырьком»

Листинг программы primer 3_11.c демонстрирует реализацию этого метода.

41

//primer 3_11.c

#include <stdio.h> #include <conio.h> #define n 5

int main ()

{

int i,j, temp=0;

int a[n]={0,5,3,7,9}; for (i=0; i<n-1; i++)

{

for (j=0; j<n-1; j++) if (a[j]<a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

printf ("\n"); for (i=0; i<n; i++)

printf ("%d ", a[i]); getch ();

return 0;

}

Сортировка выбором. Алгоритм состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом и так далее n-1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива). Последовательность шагов при n = 5 изображена на рис. 4 ниже.

Рис. 4. Алгоритм сортировки выбором

42

Вне зависимости от номера текущего шага i последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n], оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Листинг программы primer 3_12.c демонстрирует реализацию этого метода:

//primer 3_12.c #include <stdio.h> #include <conio.h>

#define n 7

int main ()

{

int a[n]={1,3,4,5,6,7,1}; int i, j, index, temp; for (i=0; i<n-1; i++)

{

index=i;

for (j=i+1; j<n; j++) if (a[j]<a[i])

{

index=j;

temp=a[i];

a[i]=a[index];

a[index]=temp;}

}

for (i=0; i<n; i++) printf("\n%d ",a[i]);

getch(); return (0);

}

Поиск минимального (максимального) элемента массива.

Алгоритм поиска будет выглядеть следующим образом:

1.Будем считать минимальным (максимальным) элементом первый элемент массива.

2.Последовательно сравнить минимальный (максимальный) элемент с элементами массива, начиная от второго элемента. Если нашелся элемент меньший (больший) минимального (максимального), поместить его на место минимального (максимального) элемента. Ниже приведен соответствующий код программы.

43

//primer 3_13.c #include <stdio.h>

#include <conio.h> #define n 5

int main ()

{

int min, i;

int a[n]={4,2,9,1,3}; min=a[0];

for (i=1; i<n;i++ )

if (a[i]<min) min=a[i]; printf ("\n min=%d", min); getch ();

return 0;

}

Объединение двух одномерных массивов. Типовой алгоритм объ-

единения двух одномерных массивов заключается в применении дополнительного массива, что и продемонстрировано в программе primer 3_14.c. Новая деталь в этой программе – это использование числа вместо имени переменной при задании размера массива.

//primer 3_14.c #include <stdio.h>

#include <conio.h>

int main (){ int i;

int mas[10];

int a[5]={4,2,9,1,3}; int b[5]={5,7,8,11,12}; for (i=0; i<5; i++)

{

mas[i]=a[i]; mas [5+i]=b[i];

}

for (i=0; i<10; i++) printf ("%d ", mas[i]);

getch (); return 0;

}

44

Циклический сдвиг элементов массива. При циклическом сдвиге вправо выталкиваемые элементы с конца массива заполняют освобождающиеся места в начале массива. Например, при сдвиге вправо на 3 разряда массива А (1, 2, 3, 4, 5, 6, 7) получаем массив А (5, 6, 7, 1, 2, 3, 4). Ниже представлена соответствующая программа.

//primer 3_15.c

#include <stdio.h>

#include <conio.h> #include <locale.h > #define n 7

int main ()

{

setlocale(LC_CTYPE, "russian"); int m, i, j;

int a[n]={1, 2, 3, 4, 5, 6, 7}; printf ("введите m\n");

scanf ("%d",&m); m= m % n;

for (i=0; i<m; i++)

{

int temp=a[n-1];

for (j=0; j<n-1; j++)

{

a[n-j-1]=a[n-j-2];

}

a[0]=temp;

}

for (i=0; i<n; i++) printf ("%d ",a[i]);

getch (); return 0;

}

Типовые алгоритмы обработки одномерных массивов применяются для решения самых разнообразных задач. Продемонстрируем применение типовых алгоритмов для решения задачи «Преобразование последовательности»: задана последовательность, содержащая n

45

целых чисел (n >= 3). Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.

Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.

Требуется написать программу, которая решает названную задачу. Выполним структурную декомпозицию программы. Анализ условия задачи показывает, что ее решение можно разбить на следу-

ющие подзадачи:

1.Основная программа: ввод - вывод элементов массива.

2.Нахождение в одномерном массиве последовательности наибольшей длины.

3.Сдвиг элементов одномерного массива.

Подзадача «Нахождение в одномерном массиве последователь-

ности наибольшей длины» разбивается на две подзадачи: сортировка и подсчет количества вхождений.

Подзадача «Сдвиг элементов массива» является типовой и не требует разбивки на подзадачи. Следовательно, на первом шаге декомпозиции с использованием метода пошаговой детализации полу-

чаем (рис. 5).

ОСНОВНАЯ

ПРОГРАММА

НАХОЖДЕНИЕ			СДВИГ
ПОСЛЕДОВАТЕЛЬНОСТИ			ЭЛЕМЕНТОВ
ЧИСЕЛ НАИБОЛЬШЕЙ
			МАССИВА
ДЛИНЫ

СОРТИРОВКА

ПОДСЧЕТ КОЛИЧЕСТВА ВХОЖДЕНИЙ

Рис. 5. Структурная декомпозиция программы

46

Первая подзадача. Так как размер массива задается с клавиатуры и значения элементов массива не заданы, выбираем способ заполнения массива – ввод с клавиатуры.

Вторая подзадача «Нахождение последовательности чисел наибольшей длины» разбивается на две типовые подзадачи:

1)сортировка одномерного массива;

2)нахождение последовательности чисел наибольшей длины. Первая подзадача. Используем любую известную сортировку,

например сортировку пузырьком.

Вторая подзадача. Поиск числа, входящего в последовательность наибольшее количество раз. Идея решения: перебираем элементы массива, сравнивая два соседних элемента. Если они равны,

впеременной k накапливаем длину и сохраняем в переменной max. Как только числа стали неравны, содержимое переменной k = 1. Так как массив отсортирован по возрастанию, если найдется большее по значению число с таким же количеством вхождений, оно не заменит минимальное.

Третья подзадача. По окончании подсчета числа вхождений

впеременной temp останется минимальное из чисел, входящих в последовательность наибольшее количество раз. Для сохранения порядка следования элементов, не равных temp, можно использовать другой массив размера исходного массива. Используем для этой цели массив а. Идея решения: просматривать элементы массива b, если элемент не равен temp, записываем его в массив a и подсчитываем количество этих элементов для того, чтобы с индекса k+1 поставить элемент, хранящийся в temp. Блок-схема алгоритма программы представлена на рис. 6.

47

	Начало
	Ввод n
	нет
да	n<3
	i=0; i<n; i++

Ввод a[i]

да

a[i]>32767 || a[i] < -32768

Вывод «Error”

нет

i=0; i<n; i++

b[i]=a[i]

C

A

Основная программа

Рис. 6. Алгоритм программы примера (см. также с. 49, 50)

48

C

да

temp=a[j]

a[j]=a[j+1]

a[j+1]=temp

да

k=k+1

да

max=k;

temp=a[i]

a[j]=b[i]

j=j+1 k=j-1

A

		Нахождение последова-
	i=0; i<n-1; i++	тельности наибольшей
		длины
	j=0; j<=n-i; j++

a[j]>a[j+1]

нет

Поиск числа max=0; k=1; min=a[0] вхождений

i=0; i<n-1; i++

нет

a[i]=a[i+1]

k=1

max<k

нет

			Сдвиг эле-
	J=0
			ментов

i=0; i<n; i++

temp<>b[i]

C

В

Рис. 6. Продолжение

49

C	В
	i=k+1; i<n; i++
	a[i]=temp

Основная

программа

i=0; i<n; i++

Вывод a[i]

конец

Рис. 6. Окончание

Полный текст программы приведен ниже:

//primer 3_16.c

#include <stdio.h>

#include <conio.h>

#define m 100 //резервируем память под 100 элементов массива

int main ()

{

int a[m],b[m];

int n, i, j, temp, max, k, min;

do {

printf ("input n\n"); scanf ("%d", &n);

}

while (n<3);

printf ("\n input massiv\n"); for (i=0; i<n; i++)

{

scanf("%d", &a[i]);

if (a[i]>32767 || a[i]<-32768) printf ("Input Error\n"); break;

}

for (i=0; i<n; i++) printf("%d ", a[i]);

50