К. Поляков, Программирование на алгоритмическом языке. Часть III 1.Обработка массивовОбработка массивов 2.Сортировка массивовСортировка массивов 3.Двоичный поискДвоичный поиск 4.Символьные строкиСимвольные строки 5.МатрицыМатрицы 6.ФайлыФайлы

К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 1. Обработка массивов

Программирование на алгоритмическом языке. Часть II К. Поляков, Реверс массива Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами A[1] и A[N], A[2] и A[N-1], … Псевдокод: 35…97 79…53 12…N-1N 12… N нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц сумма индексов N+1 Что неверно? ? div(N,2)

Программирование на алгоритмическом языке. Часть II К. Поляков, Как переставить элементы? Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти ? ? x y c c:= x x:= y y:= c c:= x x:= y y:= c x:= y y:= x x:= y y:= x Можно ли обойтись без c ? ?

Программирование на алгоритмическом языке. Часть II К. Поляков, Программа алг Реверс нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон алг Реверс нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон нц для i от 1 до div(N,2) c:= A[i] A[i]:= A[N+1-i] A[N+1-i]:= c; кц нц для i от 1 до div(N,2) c:= A[i] A[i]:= A[N+1-i] A[N+1-i]:= c; кц

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс всех элементов, кроме первого. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: Результат:

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить реверс для каждой трети массива. Пример: Исходный массив: Результат:

Программирование на алгоритмическом языке. Часть II К. Поляков, Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N]; 3581… …N-1N 581…973 нц для i от 1 до N-1 A[i]:= A[i+1] кц нц для i от 1 до N-1 A[i]:= A[i+1] кц Что неверно? ? почему не N ?

Программирование на алгоритмическом языке. Часть II К. Поляков, Программа алг Циклический сдвиг влево нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон алг Циклический сдвиг влево нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон c:= A[1] нц для i от 1 до N-1 A[i]:= A[i+1] кц A[N]:= c; c:= A[1] нц для i от 1 до N-1 A[i]:= A[i+1] кц A[N]:= c;

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 10 «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг влево без первого элемента. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО. Пример: Исходный массив: Результат:

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 11 «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО на 4 элемента. Пример: Исходный массив: Результат:

Программирование на алгоритмическом языке. Часть II К. Поляков, Выбор нужных элементов Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: цел i, N = 5 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i] < 0 то B[i]:= A[i] все кц цел i, N = 5 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i] < 0 то B[i]:= A[i] все кц ? ? ? ? ? A B Что плохо? ?

Программирование на алгоритмическом языке. Часть II К. Поляков, Выбор нужных элементов 13 Решение: ввести счетчик найденных элементов count, очередной элемент ставится на место B[count]. цел i, N = 5, count = 0 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i]< 0 то count:= count + 1 B[ ]:= A[i] все кц цел i, N = 5, count = 0 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i]< 0 то count:= count + 1 B[ ]:= A[i] все кц ? ? ? ? ? A B count

Программирование на алгоритмическом языке. Часть II К. Поляков, Как вывести массив B? Примитивное решение: вывод "Выбранные элементы:", нс нц для i от 1 до N вывод B[i], " " кц вывод "Выбранные элементы:", нс нц для i от 1 до N вывод B[i], " " кц Что плохо? ? Правильное решение: вывод "Выбранные элементы:", нс нц для i от 1 до вывод B[i], " " кц вывод "Выбранные элементы:", нс нц для i от 1 до вывод B[i], " " кц count

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «3»: Заполнить массив случайными числами в интервале [-10,10] и записать в другой массив все положительные числа. Пример: Исходный массив: Положительные числа: 3 7 «4»: Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0. Пример: Исходный массив: Заканчиваются на 0: 40 30

Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: Результат: 1 2