Страницы

Уроки 19, 20 Решение задач (массив). Задачи сортировки массива

 Решение задач с использованием массивов

Задания

1.Дан массив целых чисел. Количество запросить с клавиатуры. Найти:
•сумму элементов массива, больших данного числа А (А вводить с клавиатуры).

Экспериментальный раздел работы

Измените программу, для определения:
•суммы элементов массива, принадлежащих промежутку от А до В (А и В вводить с клавиатуры);
•суммы элементов массива с k1-ro по k2-й, где k1 и k2 вводятся с клавиатуры;
•суммы последних пяти элементов массива
•количества нечетных элементов массива;
•количества отрицательных элементов массива;
• количества  элементов массива, которые превосходят по модулю заданное число А;
• наличие в данном массиве два соседних положительных элемента;
• наличие 2 пар соседних элементов с одинаковыми знаками;
• номер последней  пары соседних элементов с  разными знаками.



Сортировка элементов массива

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

Элементы массива можно сортировать:
·         по возрастанию — каждый следующий элемент больше предыдущего — А[1] < А[2] <... < A[N];
·         по не убыванию — каждый следующий элемент не меньше предыдущего, то есть больше или равен А[1 ] ≤ А[2] ≤... ≤A[N];
·         по убыванию — каждый следующий элемент меньше предыдущего А[1 ] > А[2] > ... > A[N];
·   по не возрастанию — каждый следующий элемент не больше предыдущего, то есть меньше или равен А[1] ≥ А[2] ≥ ... ≥ A[N].

Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, произведенных в процессе сортировки.
Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена.
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

Метод пузырька (простой обмен):


                     При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.
Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
                     При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
                     На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
                     В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
                     После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно n-1, где n – это количество элементов массива.
                     Количество сравнений в каждом проходе равно n-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
                     При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.
0
1
4
6
2
0
1
4
2
6
0
1
2
4
6

program sort1;
const
    mn = 10;
 var
    a: array[1..mn] of integer;
    i, j, k,n: integer;
 begin
readln(n);
    randomize;
    for i := 1 to n do
     begin
        a[i] := random(256);
        write (a[i]:4);
    end;
    writeln;
    for i := 1 to n-1 do
        for j := i+1 to n do
            if a[i] > a[j] then
                begin
                k := a[i];
                a[i] := a[j];
                a[j] := k
                end;
    for i := 1 to n do
        write (a[i]:4);
end.

Экспериментальная часть

1.                 Выполните программу для n=10.
2.                 Выполните программу для n=5.
3.                 Добавьте в окно просмотра a[1], a[2], a[3], a[4], a[5]. Выполните программу по шагам.
4.                 Измените программу, чтобы элементы располагались от большего к меньшему.



Задания

1.    Рассмотреть сортировку простым выбором:
Program Sort2;
Const mn=10;
Var A:Array[1..mn] of real;
 i, j, m,n: Integer; k,max:real;
 begin
readln(n);
      randomize;
   for i := 1 to n do
     begin
        a[i] := random(256);
        write (a[i]:8:1);
    end;
    writeln;
For i:=n DownTo 2 Do
Begin
  m:=i; max:=a[i];
  For j:=1 to i-1 Do
  If A[j ] >max Then Begin m:=j; max:=A[j] End;
  If m<>i Then Begin  A[m] :=A[i] ;A[i] :=max; End;
End;
for i := 1 to n do
        write (a[i]:8:1);
End.
Каким образом выполняется сортировка простым выбором?

2.    Изменить решения в двух рассмотренных методах так, чтобы осуществлялась сортировка:
 1)    четных элементов массива;
 2)    отрицательных элементов массива;
 3)    элементов, записанных на нечетных местах.

3. Определить есть ли в массиве равные элементы. Вывести их на экран.



Задания для самостоятельного решения

1. Дан массив целых чисел. Количество запросить с клавиатуры. Найти:
•максимальный элемент массива и его номер, при условии, что все элементы различные;
•минимальный элемент массива.

2. Дан массив из 10 элементов. Первые 4 упорядочить по возрастанию, последние 4 по убыванию.

3. Измените алгоритм предыдущей задачи для n элементов.

4. Дан массив 20 целых чисел на отрезке [-2;5]. Упорядочить массив, удалив нули со сдвигом влево, ненулевыми элементами.

5. Дан массив 15 целых чисел на отрезке [-5;5]. Упорядочить массив, удалив повторяющиеся элементы.