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

Решение таких задач сводится к выбору алгоритма просмотра массива с целью выполнить требуемые перестановки.

Пример 4. Дан одномерный целочисленный массив, заданный случайными числами на промежутке [-10; 10). Выполните циклический сдвиг элементов с нулевой позиции вправо на одну позицию. То есть должна быть реализована схема перестановок: x [0] ® x [1], x [1] ® x [2], …, x [ k -1] ® x [0].

Одним из алгоритмов такого циклического сдвига является следующая последовательность действий. Поместим в буфер последний элемент массива (buf=x[k-1]). Выполним смещение остальных элементов вправо на одну позицию (x[i]=x[i-1]). При этом важен порядок смещения: на освободившееся место последнего элемента перемещается предпоследний, на место предпоследнего – предшествующий ему и т.д. В результате таких перемещений освобождается место нулевого элемента, на которое перемещается элемент из буфера. В данной задаче целесообразно выполнить вывод массива дважды: до и после циклического сдвига.

//Циклический сдвиг элементов в массиве с нулевой позиции на одну позицию вправо

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

//подключение модуля для генератора случайных чисел

#define max 100

 

void gen (int k, int a, int b,int x[max]);

//прототип функции генерации массива

void out (int k, int x[max]);

//прототип функции вывода массива

void sdvig (int k, int x[max]);

//прототип функции циклического сдвига элементов массива

 

void main (){

int mas[max];

int n;

do {

printf("\nВведите количество элементов массива n

(n<=100): ");

scanf ("%d",&n);

}

while (n>max);

gen(n,-10,10,mas);

printf("Вывод сгенерированного массива из %d элементов:

\n",n);

out(n,mas);

sdvig (n,mas);

printf("\nВывод массива после циклического сдвига

элементов: \n");

out(n,mas);

}

//Описание функции генерации массива с клавиатуры

void gen(int k,int a, int b, int x[max]){

int i;

srand(time(NULL)*1000);

for (i=0;i<k;i++){

x[i]=int(rand()*1.0/(RAND_MAX)*(b-a)+a);

}

}

//Описание функции вывода массива в строку

void out (int k,int x[max]){

int i;

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

printf("%d ",x[i]);

}

//Описание функции циклического сдвига элементов массива

void sdvig(int k,int x[max]){

int i,buf;

buf=x[k-1];

for (i=k-1;i>0;i--)

x[i]=x[i-1];

x[0]=buf;

}

Задания

1. Наберите коды программ из Примеров 1 и 2. Выполните компиляцию и запуск программ.

2. Дан одномерный целочисленный массив из N элементов, заданных с клавиатуры. Найти: количество и процентное соотношение положительных, отрицательных и нулевых элементов.

3. Дан одномерный целочисленный массив из N элементов, заданных случайными числами на промежутке [ a; b). Заменить все элементы массива, кратные 3, на третий элемент массива.

4. Дан одномерный вещественный массив из N элементов (N – нечетное), заданных случайными числами на промежутке [ a; b). Поменять местами элементы симметричные относительно центрального.

Домашние задания

1. Наберите коды программ из Примеров 3 и 4. Выполните компиляцию и запуск программ.

2. Дан одномерный целочисленный массив из N элементов, заданных с клавиатуры. Найти: количество и процентное соотношение четных и нечетных значений элементов.

3. Дан одномерный целочисленный массив из N элементов, заданных случайными числами на промежутке [ a; b). Поменять местами первый минимальный и первый максимальный элементы.

4. Дан одномерный вещественный массив из N элементов, заданных случайными числами на промежутке [ a; b). Выполните циклический сдвиг элементов с n -ой позиции вправо на k позиций.

 

Лабораторная работа 30

Одномерные массивы: задачи сортировок элементов массива

 

Цель работы: изучить алгоритмы простейших сортировок и научиться решать задачи на их применение в одномерных массивах в языке C++.

 

Теоретические сведения

Задача сортировки является такой же базовой, как задача поиска. В практических условиях эти задачи взаимосвязаны. Решению проблем, связанных с сортировкой, посвящено множество фундаментальных научных исследований, разработано множество алгоритмов.

В общем случае сортировку следует понимать как процесс перегруппировки, заданного множества объектов в определенном порядке.

Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании.

Сортировка – это процесс перегруппировки заданного множества объектов в некотором установленном порядке.

Сортировки массивов подразделяются по быстродействию. Существуют простые методы сортировок, которые требуют n*n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют n*ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т. к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

Простые методы подразделяются на три основные категории:

· сортировка методом «пузырька» (простого обмена);

· сортировка методом простого выбора (простой перебор);

· сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг).

Сортировка методом «пузырька» (простого обмена)

Алгоритм попарного сравнения в литературе называют «методом пузырька», проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы увеличивались сверху вниз.

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

/*Описание функции сортировки методом "пузырька" (простым обменом)*/

void BubbleSort (int k,int x[max]) {

int i,j,buf;

for (i=k-1;i>0;i--)

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

if (x[j]>x[j+1]) {

buf=x[j];

x[j]=x[j+1];

x[j+1]=buf;

}

}

 

Сортировка методом простого выбора (простой перебор)

Это наиболее естественный алгоритм упорядочивания.

Шаги алгоритма:

1. находим минимальное значение в текущем списке

2. производим обмен этого значения со значением на первой неотсортированной позиции

3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

//Описание функции сортировки методом простого выбора

void SelectionSort (int k,int x[max]) {

int i,j,min,temp;

for (i=0;i<k-1;i++) {

//устанавливаем начальное значение минимального индекса

min=i;

//находим минимальный индекс элемента

for (j=i+1;j<k;j++){

if (x[j]<x[min])

min=j;

//меняем значения местами

}

temp=x[i];

x[i]=x[min];

x[min]=temp;

}

}

 

Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

· прост в реализации

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим

· эффективен на наборах данных, которые уже частично отсортированы

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

· может сортировать список по мере его получения

· не требует временной памяти, даже под стек

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

//Описание функции сортировки методом простого включения

void InsertSort (int k,int x[max]) {

int i,j, temp;

for (i=0;i<k;i++) {

//цикл проходов, i - номер прохода

temp=x[i];

//поиск места элемента

for (j=i-1; j>=0 && x[j]>temp; j--)

x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли

//место найдено, вставить элемент

x[j+1]=temp;

}

}

 

 

Задания

1. Отсортируйте по возрастанию методом «пузырька» одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100). Выведите на экран исходный и отсортированный массивы.

2. Отсортируйте по возрастанию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

3. Отсортируйте по возрастанию методом простого включения одномерный целочисленный массив, заданный с клавиатуры. Выведите на экран исходный и отсортированный массивы.

Домашние задания

1. Отсортируйте по убыванию методом простого обмена одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100).

2. Отсортируйте по убыванию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

3. Отсортируйте по убыванию методом простого включения одномерный целочисленный массив, заданный с клавиатуры. Выведите на экран исходный и отсортированный массивы.

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

Варианты индивидуального задания

№	Задание
1.	Найти максимальный четный из данных n ненулевых целочисленных элементов массива. Если требуемые элементы отсутствуют, то вывести 0.
2.	Даны числа a, b (0 < a < b) и набор из n элементов. Найти минимальный из элементов, содержащихся в интервале (a, b). Если требуемые элементы отсутствуют, то вывести – 1.
3.	Дан массив А, состоящий из n элементов. Вывести номер первого и последнего из тех его элементов A [ i ], которые удовлетворяют двойному неравенству: A [ 1 ] < A [ i ]< A [ n ]. Если таких элементов нет, то вывести 0.
4.	Найти номер последнего максимального из массива данных n целочисленных элементов.
5.	Найти минимальный четный из данных n ненулевых целочисленных элементов массива. Если требуемые элементы отсутствуют, то вывести 0.
6.	Дан набор из n целочисленных элементов. Найти максимальное количество подряд идущих максимальных элементов.
7.	Дано вещественное число R и массив размера n. Найти два элемента массива, сумма которых наименее близка к данному числу R.
8.	Найти минимальный положительный из данных n элементов. Если требуемые элементы отсутствуют, то вывести 0.
9.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, прибавив к четным числам последний элемент. Начальный и последний элементы массива не изменять.
10.	Дан набор из n целочисленных элементов. Найти количество элементов, расположенных после последнего максимального.
11.	Дан набор из n целочисленных элементов. Найти количество элементов, содержащихся между первым и последним минимальным. Если в наборе имеется единственный минимальный элемент, то вывести 0.
12.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, прибавив к четным числам первый элемент. Начальный и последний элементы массива не изменять.
13.	Найти номер максимального отрицательного из данных n элементов. Если требуемые элементы отсутствуют, то вывести 0
14.	Найти номера всех максимальных из массива данных n целочисленных элементов.
15.	Дан набор из n целочисленных элементов. Найти количество элементов, расположенных перед первым минимальным.
16.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, прибавив к нечетным числам первый элемент. Начальный и последний элементы массива не изменять.
17.	Найти количество минимальных и количество максимальных элементов в массиве из данных n целочисленных элементов.
18.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, умножив все положительные элементы на минимальный элемент.
19.	Найти минимальный нечетный из данных n ненулевых целочисленных элементов массива. Если требуемые элементы отсутствуют, то вывести 0.
20.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, разделив на 10 все элементы, оканчивающиеся хотя бы одним нулем.
21.	Найти максимальный нечетный из данных n ненулевых целочисленных элементов массива. Если требуемые элементы отсутствуют, то вывести 0.
22.	Дан целочисленный массив, состоящий из n элементов. Определите, есть ли в массиве элемент, равный среднему арифметическому всех элементов.
23.	Дан целочисленный массив, состоящий из n элементов. Замените нулевой элемент значением минимального, а последний – значением максимального элементов.
24.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, прибавив к нечетным числам последний элемент. Начальный и последний элементы массива не изменять.
25.	Дан набор из n целочисленных элементов. Найти количество элементов, содержащихся между первым и последним максимальным. Если в наборе имеется единственный максимальный элемент, то вывести 0.
26.	Дан целочисленный массив, состоящий из n элементов. Преобразовать его, умножив все его элементы на минимальный элемент. Минимальный элемент массива не изменять.
27.	Найдите максимальную разницу между соседними элементами вещественного массива.
28.	Замените единицами все простые элементы массива натуральных чисел.

Лабораторная работа 31