О БРАБОТКА МАССИВОВ 1. Включение элемента в заданную позицию массива 2. Удаление элементов массива. Удаление элементов массива. Удаление элементов массива. - презентация

1 О БРАБОТКА МАССИВОВ 1. Включение элемента в заданную позицию массива 2. Удаление элементов массива. Удаление элементов массива. Удаление элементов массива. 3. Сортировка массива по возрастанию (убыванию) методом «Пузырька». Сортировка массива по возрастанию (убыванию) методом «Пузырька». Сортировка массива по возрастанию (убыванию) методом «Пузырька». 4. Поиск в массиве. Поиск в массиве. Поиск в массиве. 5. Строки. Строки.

2 2 Использование ф-ции случайных чисел. Программа program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; Begin randomize; writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end; program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; Begin randomize; writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end; for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } случайные числа в интервале [50,150) поиск максимального

3 В КЛЮЧЕНИЕ 1- ГО ЭЛЕМЕНТА В ЗАДАННУЮ ПОЗИЦИЮ МАССИВА 1. Размер массива описывается с учетом вставляемого элемента. 2. Для ввода элементов массива организуется цикл без учета вставляемого элемента. К пусть это будет 2-я A[i+1]:=A[i] 3. Перед включением нового элемента в К-ю позицию ( пусть это будет 2-я ) необходимо раздвинуть массив, т.е. передвинуть «хвост» массива вправо на 1 позицию, выполняя операцию A[i+1]:=A[i]. 4. Перемещение элементов массива начинают с «хвоста». 5. Вставим новый элемент массива (например, 10) на 2-ю позицию

4 П РИМЕР ПРОГРАММЫ ВСТАВКИ 1- ГО ЭЛЕМЕНТА В МАССИВ МЕЖДУ 3- М И 4- М ЭЛЕМЕНТАМИ.

5 У ДАЛЕНИЕ 1- ГО ЭЛЕМЕНТОВ МАССИВА. хвостk+1] влево a[i]:=a[i+1]. 1. Удалить элемент массива, расположенный на К-той позиции, можно, сдвинуть «хвост» массива, начиная с [k+1]- го элемента, на одну позицию влево, т.е. выполняя операцию a[i]:=a[i+1]. 6-ой 2. Удалим 6-ой элемент массива: 3. Вывод элементов нового массива организуется на 1 элемент меньше

6 П РИМЕР ПРОГРАММЫ УДАЛЕНИЯ 1- ГО ЭЛЕМЕНТА В МАССИВА ( ПУСТЬ ЭТО БУДЕТ 10 ЭЛЕМЕНТ ).

7 Массив A[5] = {5, 7, 3, 6, 1} упорядочить (отсортировать) по возрастанию.Алгоритм: Шаг 1 Шаг 1. Сравним 5-ый элемент с 4-м, если он меньше, поменяем их местами. Шаг 2 – Шаг 2 – 4. Те же действия выполним для 4 3, 3 2, 2 1. В результате самый маленький элемент переместиться на 1-е место. n-1 но 1-ый элемент рассматривать не будем Повторим данный алгоритм сначала, но с (n-1) элемента, но 1-ый элемент рассматривать не будем, т.к. в него записан Min элемент массива Так повторяем до тех пор, пока не упорядочим весь массив У ПОРЯДОЧЕНИЕ ( СОРТИРОВКА ) ЭЛЕМЕНТОВ МАССИВА ПО ВОЗРАСТАНИЮ ( УБЫВАНИЮ ) МЕТОДОМ «П УЗЫРЬКА ».

8 Для организации сравнивания одного элемента массива поочередно со всеми остальными, организуется вложенный цикл: Внешний цикл For i:=2 to 9 do { Внешний цикл } Begin For j:=9 Downto i-1 Do Begin If A[j]>a[j+1] Then Begin Меньший элемент массива меняется { Меньший элемент массива меняется местами с большим местами с большим } min:=A[j+1]; A[j+1]:=A[j]; A[j]:=min End;

9 Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Напишите программу, которая находит и выводит второй максимум массива (элемент, который в отсортированном по невозрастанию массиве стоял бы вторым). Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них. const N=30; var a: array [1..N] of integer; i, k, max, max2: integer; begin for i:=1 to N do readln(a[i]);... end.

10 П РИМЕР ПРОГРАММЫ СОРТИРОВКИ ЭЛЕМЕНТОВ МАССИВА ПО ВОЗРАСТАНИЮ МЕТОДОМ «П УЗЫРЬКА ».

11 Сложность в том, что нужно найти не максимальный элемент, а второй по величине. Решение: Вар.1. Отсортировать массив по возрастанию (убыванию) и вывести нужные элементы. Вар.2. Сначала найти максимум, а потом искать следующий за ним. Вар.3. Можно сделать это за один проход по массиву. Нам нужны две переменные, max (максимальный элемент) и max2 (второй максимум). Сначала выбираем максимальный из первых двух элементов и записываем его значение в max, а второй по величине записываем в max2 : Затем в цикле перебираем все элементы, начиная с 3-го (первые два уже «задействованы»!) до последнего, 30-ого. Если очередной элемент a[i] больше, чем max, записываем значение max в max2 (предыдущий максимум становится вторым), а значение a[i] – в max. Иначе, если a[i] больше, чем max2, записываем значение a[i] в max2. После завершения цикла выводим значение переменной max2. if a[1] > a[2] then begin max:=a[1]; max2:=a[2]; end else begin max:=a[2]; max2:=a[1]; end; const N=30; var a: array [1..N] of integer; i, k, max, max2: integer; begin for i:=1 to N do readln(a[i]); if a[1] > a[2] then begin max:=a[1]; max2:=a[2] end else begin max:=a[2]; max2:=a[1] end; for i:=3 to N do if a[i] > max then begin max2 := max; max := a[i] end else if a[i] > max2 then max2 := a[i]; writeln(max2) end.

12 12 Поиск в массиве Задача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для произвольного массива: линейный поиск (перебор) недостаток: низкая скорость Как ускорить? – заранее подготовить массив для поиска как именно подготовить? как использовать "подготовленный массив"?

13 13 Линейный поиск nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; {выход из цикла} end; nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; {выход из цикла} end; nX := 0; { пока не нашли...} if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); nX := 0; { пока не нашли...} if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); nX – номер нужного элемента в массиве Что плохо? ? Улучшение: после того, как нашли X, выходим из цикла. for i:=1 to N do { цикл по всем элементам } if A[i] = X then { если нашли, то... } nX := i; {... запомнили номер} for i:=1 to N do { цикл по всем элементам } if A[i] = X then { если нашли, то... } nX := i; {... запомнили номер} nX := 0; i := 1; while i <= N do begin if A[i] = X then begin nX := i; i := N; end; i := i + 1; end; nX := 0; i := 1; while i <= N do begin if A[i] = X then begin nX := i; i := N; end; i := i + 1; end; break; i := N;