К. Поляков, 2010 -2012 Программирование на алгоритмическом языке. Часть III 1.Обработка массивовОбработка массивов 2.Сортировка. - презентация

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

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

3 Программирование на алгоритмическом языке. Часть 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)

4 Программирование на алгоритмическом языке. Часть 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 ? ?

5 Программирование на алгоритмическом языке. Часть 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; кц

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

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

8 Программирование на алгоритмическом языке. Часть 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 ?

9 Программирование на алгоритмическом языке. Часть 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;

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

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

12 Программирование на алгоритмическом языке. Часть 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 Что плохо? ?

13 Программирование на алгоритмическом языке. Часть 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

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

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

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