Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д.
int i,min,n_min,j;
for(i=0;i<n-1;i++)
{
min=a[i];n_min=i;//поиск минимального
for(j=i+1;j<n;j++)
if(a[j]<min)
{
min=a[j];
n_min=j;
}
a[n_min]=a[i];//обмен
a[i]=min;
}
Сортировка методом простого обмена
Сравниваются и меняются местами пары элементов, начиная с последнего. В результате самый маленький элемент массива оказывается самым левым элементом массива. Процесс повторяется с оставшимися элементами массива.
for(int i=1;i<n;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
{
int r=a[j];
a[j]=a[j-1];
a[j-1]=r;}
}
Поиск в отсортированном массиве
В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом поиске требуется не более m сравнений, если n- m-ая степень 2, если n не является степенью 2, то n<k=2m.
Массив делится пополам S:=(L+R)/ 2+1 и определяется в какой части массива находится нужный элемент Х. Так как массив упорядочен, то, если a[S]<X – искомый элемент находится в правой части массива, иначе – находится в левой части. Выбранную часть массива снова надо разделить пополам и т. д., до тех пор, пока границы отрезка L и R не станут равны.
L S R
Console.WriteLine("Введите элемент для поиска");
buf=Console.ReadLine();
int x = int.Parse(buf);
int l = 0, r = n - 1, s;
do
{
s = (l + r) / 2;//средний элемент
if (c[s] < x) l = s + 1;//перенести леую границу
else r = s;//перенести правую границу
} while (l != r);
if (c[l] == x) Console.WriteLine("элемент "+c[l]+", его номер=" +(l+1));
else Console.WriteLine("Элемент не найден");
Постановка задачи
1) Сформировать массив из n элементов с помощью датчика случайных чисел (n задается пользователем с клавиатуры).
2) Распечатать полученный массив.
3) Выполнить удаление указанных элементов из массива.
4) Вывести полученный результат.
5) Выполнить добавление указанных элементов в массив.
6) Вывести полученный результат.
7) Выполнить перестановку элементов в массиве.
8) Вывести полученный результат.
9) Выполнить поиск указанных в массиве элементов и подсчитать количество сравнений, необходимых для поиска нужного элемента.
10) Вывести полученный результат.
11) Выполнить сортировку массива указанным методом.
12) Вывести полученный результат.
13) Выполнить поиск указанных элементов в отсортированном массиве и подсчитать количество сравнений, необходимых для поиска нужного элемента.
14) Вывести полученный результат.
Варианты
| Вариант | Удаление | Добавление | Перестановка | Поиск | Сортировка |
| Максимальный элемент | К элементов в начало массива | Перевернуть массив | Первый четный | Простой обмен | |
| Минимальный элемент | К элементов в конец массива | Сдвинуть циклически на M элементов вправо | Первый отрицательный | Простой выбор | |
| Элемент с заданным номером | N элементов, начиная с номера К | Сдвинуть циклически на M элементов влево | Элемент с заданным ключом (значением) | Простое включение | |
| N элементов, начиная с номера K | Элемент с номером К | Поменять местами элементы с четными и нечетными номерами | Элемент равный среднему арифметическому элементов массива | Простой обмен | |
| Все четные элементы | К элементов в начало массива | Четные элементы переставить в начало массива, нечетные - в конец | Первый четный | Простой выбор | |
| Все элементы с четными индексами | К элементов в конец массива | Поменять местами минимальный и максимальный элементы | Первый отрицательный | Простое включение | |
| Все нечетные элементы | N элементов, начиная с номера К | Положительные элементы переставить в начало массива, отрицательные - в конец | Элемент с заданным ключом (значением) | Простой обмен | |
| Все элементы с нечетными индексами | Элемент с номером К | Перевернуть массив | Элемент равный среднему арифметическому элементов массива | Простой выбор | |
| Все элементы больше среднего арифметического элементов массива | К элементов в начало массива | Сдвинуть циклически на M элементов вправо | Первый четный | Простое включение | |
| Максимальный элемент | К элементов в конец массива | Сдвинуть циклически на M элементов влево | Первый отрицательный | Простой обмен | |
| Минимальный элемент | N элементов, начиная с номера К | Поменять местами элементы с четными и нечетными номерами | Элемент с заданным ключом (значением) | Простой выбор | |
| Элемент с заданным номером | Элемент с номером К | Четные элементы переставить в начало массива, нечетные - в конец | Элемент равный среднему арифметическому элементов массива | Простое включение | |
| N элементов, начиная с номера K | К элементов в начало массива | Поменять местами минимальный и максимальный элементы | Первый четный | Простой обмен | |
| Все четные элементы | К элементов в конец массива | Положительные элементы переставить в начало массива, отрицательные - в конец | Первый отрицательный | Простой выбор | |
| Все элементы с четными индексами | N элементов, начиная с номера К | Перевернуть массив | Элемент с заданным ключом (значением) | Простое включение | |
| Все нечетные элементы | Элемент с номером К | Сдвинуть циклически на M элементов вправо | Элемент равный среднему арифметическому элементов массива | Простой обмен | |
| Все элементы с нечетными индексами | К элементов в начало массива | Сдвинуть циклически на M элементов влево | Первый четный | Простой выбор | |
| Все элементы больше среднего арифметического элементов массива | К элементов в конец массива | Поменять местами элементы с четными и нечетными номерами | Первый отрицательный | Простое включение | |
| Максимальный элемент | N элементов, начиная с номера К | Четные элементы переставить в начало массива, нечетные - в конец | Элемент с заданным ключом (значением) | Простой обмен | |
| Минимальный элемент | Элемент с номером К | Поменять местами минимальный и максимальный элементы | Элемент равный среднему арифметическому элементов массива | Простой выбор | |
| Элемент с заданным номером | К элементов в начало массива | Положительные элементы переставить в начало массива, отрицательные - в конец | Первый четный | Простое включение | |
| N элементов, начиная с номера K | К элементов в конец массива | Перевернуть массив | Первый отрицательный | Простой обмен | |
| Все четные элементы | N элементов, начиная с номера К | Сдвинуть циклически на M элементов вправо | Элемент с заданным ключом (значением) | Простой выбор | |
| Все элементы с четными индексами | Элемент с номером К | Сдвинуть циклически на M элементов влево | Элемент равный среднему арифметическому элементов массива | Простое включение | |
| Все нечетные элементы | К элементов в начало массива | Поменять местами элементы с четными и нечетными номерами | Первый четный | Простой обмен |
Методические указания
1. Используются массивы, под которые количество памяти выделяется в процессе выполнения программы:
Console.Write("Введите количество элементов в массиве ");
buf=Console.ReadLine();
n=int.Parse(buf);
int [] arr=new int[n];
2. Формирование массива осуществляется с помощью датчика случайных чисел. Для этого
используется класс Random.
Random a=new Random(0);//инициализация ДСЧ
. . . .
arr[i] = a.Next(0,100);//генерация элемента массива
3. Вывод результатов должен выполняться после выполнения каждого задания. Элементы массива рекомендуется выводить в строчку, разделяя их между собой пробелом.
for ( i = 0; i < n; i++) Console.Write(arr[i] + " ");
Console.WriteLine();
6. Содержание отчета:
1) Постановка задачи (общая и конкретного варианта).
2) Анализ поставленного задания: определить к какому классу задач относится задача и объяснить почему.
3) Алгоритмы для каждой подзадачи.
4) Текст программы.
5) Результаты тестов (тесты, ЧЯ, МГТ)