Урок 21. Сортировка массива

1. Сортировка массива
Сортировка массива - это расстановка элементов массива в заданном порядке (самое простое - по возрастанию или убыванию).
Существующие методы сортировки массива по возрастанию/убыванию:

• метод пузырька
• метод выбора
• "быстрая сортировка"
• сортировка "кучей"
• сортировка слиянием
• пирамидальная сортировка

2. Метод пузырька
Как пузырей воздуха поднимается со дна вверх в стакане воды, так самый маленький "легкий элемент" массива перемещается вверх (к началу массива) - всплывает.


Задача: сортировка массива по возрастанию (array112 стр. 59).


Алгоритм: начиная снизу (с конца массива), сравниваем два соседних элемента, если они стоят "неправильно", то меняем их местами.

За один проход на месте A[1] будет стоять минимальный элемент:
for  j:=n-1 downto 1 do
if A[j]>A[j+1] then begin  c:= A[j]; A[j]:=A[j+1]; A[j+1]:=c end;


Второй проход: 
for  j:=n-1 downto 2 do
if A[j]>A[j+1] then begin  c:= A[j]; A[j]:=A[j+1]; A[j+1]:=c end;
...


i-ый проход: 
for  j:=n-1 downto i do

Задача для самостоятельного решения: отсортировать массив в порядке возрастания последней цифры.

3. Метод простого выбора

Задача array113. Идея следующая: найти максимальный элемент массива и поменять его местами с последним (N-м) элементом; выполнить описанные действия N-1 раз, каждый раз уменьшая на 1 количество анализируемых элементов и выводя содержимое массива.

Первый проход:
nmin:=1;
for  j:=2 to n do
if A[j]>A[nmin] then nmin:=j;
if nmin<>1 then begin c:=A[1]; A[1]:=A[nmin];A[nmin]:=c end;


Второй проход:
nmin:=2;
for  j:=3 to n do
if A[j]>A[nmin] then nmin:=j;
if nmin<>2 then begin c:=A[2]; A[2]:=A[nmin];A[nmin]:=c end;
...


i-ый проход:
nmin:=i;
for  j:=i+1 to n do
if A[j]>A[nmin] then nmin:=j;
if nmin<>i then begin c:=A[i]; A[i]:=A[nmin];A[nmin]:=c end;


Задача для самостоятельного решения: отсортировать массив в порядке возрастания суммы цифр. Массив заполнить двузначными числами, например числами от 10 до 99.


4. Домашнее задание
На основе метода пузырька решите задачу array115.

Урок 20. Удаление и вставка элементов

1. Выполните задание
Задан массив A: 2 4 10 8 0
Выполните трассировку программы и определите что будет выдано на печать:
const n=5;
var i,j,s: integer;
A,B: array[1..n] of integer;
begin
writeln('Введите массив A: ');
for  i:=1 to n do  read( A[i]);
writeln;
s:=A[2];
for  i:=2 to n-1 do begin A[i]:=A[i+1]; A[i+1]:=A[i+1];end;
A[5]:=s;
writeln('Полученный массив A: ');
for  i:=1 to n do   write( A[i]:4);
end.


2. Проверка ДЗ
Рассмотреть решения задач array65 и array66.


3.  Удаление и вставка элементов массива

Рассмотреть решение следующих задач: array90 (вместе), array102 (вместе), самостоятельно array103 (только перед минимальным).

4. Домашнее задание

Выполните задачу array103 (полностью). 

Урок 19. Преобразование массива

1.Проверка домашнего задания
Рассмотрим решение задачи array54:
const n=10;
var i,j: integer;
A,B: array[1..n] of integer;
begin
writeln('Дан целочисленный массив A размера N.Переписать в новый массив B все четные числа из исходного массива(в том же порядке)и вывести размер полученног омассива B и его содержимое.');
writeln('Исходный массив A: ');
for  i:=1 to n do  begin A[i]:=random(10)+1;; write( A[i]:4); end;
writeln;
j:=0;
for  i:=1 to n do
if A[i] mod 2=0 then begin j:=j+1;B[j]:=A[i] end;
writeln('Размер массива В: ',j);
writeln('Полученный массив В: ');
for  i:=1 to j do   write( B[i]:4);
end.

Рассмотрим решение задачи array58:
const n=5;
var i,j,s: integer;
A,B: array[1..n] of integer;
begin
writeln('Дан массив A размера N. Сформировать новый массив B того же размера по следующему правилу:элемент B с номером K равен сумме элементов  массива A с номерами от 1 до K');
writeln('Исходный массив A: ');
for  i:=1 to n do  begin A[i]:=random(3)+1;; write( A[i]:4); end;
writeln;
s:=0;
for  i:=1 to n do
begin s:=s+A[i];B[i]:=s end;
writeln('Полученный массив В: ');
for  i:=1 to n do   write( B[i]:4);
end.

2. Изменение элементов массива

Обращаю ваше внимание, что использование вспомогательных массивов в этом разделе не предусмотрено.

Рассмотрим решение задачи array68.

Выполнить самостоятельно array74. 
Рассмотрим решение задачи array79.
Выполнить самостоятельно array83.  

3. Домашнее задание
Напишите программу для решения следующих задач: array65, array66.

Урок 18. Работа с несколькими массивами

1. Решение задач
Решаем вместе: array51, самостоятельно: array53.
Решаем вместе: array62,  array63.

Решение array63:
const n=3;
var i,j,k: integer;
A,B: array[1..n] of integer;
C: array[1..2*n] of integer;
begin
writeln('Даны дв амассива A и B размера 5,элементы которых упорядочены по возрастанию.Объединить эти массивы так,чтобы результирующий массив C (размера10)остался упорядоченным по возрастанию');
writeln('Исходный массив A: ');
for  i:=1 to n do  begin write('A[',i,']='); readln( A[i]); end;
writeln('Исходный массив B: ');
for  i:=1 to n do  begin write('B[',i,']='); readln( B[i]); end;
j:=1; k:=1;
for  i:=1 to 2*n do
begin
if (j>n)and (k<=n) then   begin C[i]:=B[k];k:=k+1 end;
if (k>n) and  (j<=n)then  begin C[i]:=A[j];j:=j+1 end;
if (j<=n) and (k<=n) then begin
                  if A[j]<=B[k] then begin C[i]:=A[j];j:=j+1 end
                     else begin C[i]:=B[k];k:=k+1 end;
                          end;
end;
writeln;
write('Полученный массив C:');
for  i:=1 to  2*n do   write( C[i]:6);
writeln;
end.

2. Домашнее задание
Решите самостоятельно задачи: array54, array58.

Урок 17. Зачет "Одномерный массив. Действия с элементами массива"

1. Домашнее задание
Рассмотрим решение задачи array47:

const n=10;
var i,k,j,s: integer;
mas: array[1..n] of integer;
begin
writeln('Дан целочисленный массив размера N. Найти количество различных элементов в данном массиве.');
write(' Исходный массив:');
for  i:=1 to n do
begin mas[i]:=random(100)+1; write( mas[i]:6); end;
writeln;
for  i:=1 to n-1 do
     for  j:=i+1 to n do
          if mas[i]=mas[j] then  mas[j]:=0;
write(' Преобразованный массив:');
for  i:=1 to n do write( mas[i]:6);
writeln;
s:=0;
for  i:=1 to n do if mas[i]<>0 then  s:=s+1;
writeln ('Различных элементов ',s);
end.

2. Зачет
Форматирование массива и вывод его элементов (20 баллов за задачу): 1, 4, 7, 10-17.
Анализ элементов массива (25 б. за задачу): 19, 21-25, 29-46, 48-50.

Урок 16. Действия с элементами массива (продолжение)

1. Рассмотреть решение ДЗ
Решение задачи array9:

const n=10;
var i,k: integer;
mas: array[1..n] of integer;
begin
writeln('Дан целочисленный массив размера N. Вывести все содержащиеся в данном массиве четные числа в порядке убывания их индексов, а также их количество K.');
write('Исходный массив:');
for  i:=1 to n do
begin mas[i]:=random(100); write( mas[i]:6); end;
writeln;
write('Четные элементы массива:');
k:=0;
for  i:=n downto 1 do
if mas[i] mod 2=0 then begin write (mas[i]:6); k:=k+1;  end; 
writeln;
writeln ('Количество четных элементов: ', k);
end.

Решение задачи array20:

const n=10;
var i,k,l,s: integer;
mas: array[1..n] of integer;
begin
writeln('Дан массив размера N и целые числа K и L (1<K<L<N). Найти сумму элементов массива с номерами от K до L включительно.');
write('Введите K и L:');
readln (k,l);
write(' Исходный массив:');
for  i:=1 to n do
begin mas[i]:=random(100)+1; write( mas[i]:6); end;
writeln;
s:=0;
for  i:=k to l do s:=s+mas[i];
writeln;
writeln ('Искомая сумма равна: ', s) ;
end.

2. Рассмотреть решения задач: 
Решаем вместе: array26:

const n=5;
var i,k,l,s: integer;
mas: array[1..n] of integer;
begin
writeln('Дан целочисленный массив размера N.Проверить,чередуются ли в нем четные и нечетные числа.Если чередуются,то вывести 0,если нет то вывести порядковый номер первого элемента,нарушающего закономерность.');
write(' Исходный массив:');
for  i:=1 to n do
begin mas[i]:=random(100)+1; write( mas[i]:6); end;
writeln;
k:=0;
for  i:=2 to n do
if ((mas[i]+mas[i-1]) mod 2=0)then begin k:=i; break; end;
writeln (k);
end.


Самостоятельно: array27.

3. Домашнее задание
Напишите программу для решения следующих задач: array28, array47.

Урок 15. Действия с элементами массива

1. Выполните задания
1) Есть ли ошибки в описании и обращении к элементам массива?

2) Чему будет равно A[5] после выполнения программы?
const n=10;
var i,p: integer;
a: array[1..n] of integer;
begin
a[1]:=2;  a[2]:=3;
for  i:=3 to n do  a[i]:=a[i-1]*a[i-2];
writeln ('Сформирован массив:');
for  i:=1 to n do  write(a[i]:8);
end.

2. Рассмотреть решение ДЗ
Решение задачи array3:
const n=10;
var i,a,d: integer;
mas: array[1..n] of integer;
begin
writeln(' Дано целое число N (>1),а так же первый член A и разность D арифметической прогрессии. Сформировать и вывести массив размера N,содержащий N первых членов данной прогрессии: A, A + D, A +2*D, A +3*D...');
writeln('Введите числа А и D: ');
readln(a,d);
mas[1]:=a;
for  i:=2 to n do  begin mas[i]:= mas[i-1]+d; end;
writeln ('Сформирован массив:');
for  i:=1 to n do  write(mas[i]:8);
end.



Решение задачи array6:
const n=10;
var i,a,b,s: integer;
mas: array[1..n] of integer;
begin
writeln(' Даны целые числа N (>2), A и B. Сформировать и вывести целочисленный массив размера N,первый элемент которого равен A, второй равен B,а каждыйпо следующий элемент равен сумме всех предыдущих.');
writeln('Введите числа А и B: ');
readln(a,b);
mas[1]:=a;  mas[2]:=b;  s:=mas[1];
for  i:=3 to n do  begin s:= s+mas[i-1];mas[i]:=s;  end;
writeln ('Сформирован массив:');
for  i:=1 to n do  write(mas[i]:8);
end.

3. Заполнение массива случайными числами. 
Генератор случайных чисел:

Пример заполнения массива целыми числами из диапазона [50, 150):

4. Решение задач
Напишите программы для решения следующих задач:  array8, array18.

5. Домашнее задание
Напишите программы для решения следующих задач:  array9, array20.