К.Ю. Поляков, Е.А. Ерёмин, 2013 1 Программирование на алгоритмическом языке § 62. МассивыМассивы § 63. Алгоритмы обработки массивовАлгоритмы обработки. - презентация

1 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 62. Массивы Массивы § 63. Алгоритмы обработки массивов Алгоритмы обработки массивов § 64. Сортировка Сортировка § 65. Двоичный поиск Двоичный поиск § 66. Символьные строки Символьные строки § 67. Матрицы Матрицы § 68. Работа с файлами Работа с файлами

2 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 62. Массивы 2

3 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что такое массив? 3 Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер. Надо: Как ввести переменных? ? выделять память записывать данные в нужную ячейку читать данные из ячейки

4 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Выделение памяти (объявление) 4 целтаб A[1:5] вещтаб V[0:5] логтаб L[-5:5] симтаб S[65:90] целтаб A[1:5] вещтаб V[0:5] логтаб L[-5:5] симтаб S[65:90] Массив = таблица! ! минимальный индекс максимальный индекс цел N = 10 целтаб A[1:N] цел N = 10 целтаб A[1:N] размер через константу Зачем? ?

5 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что неправильно? 5 целтаб A [10:1]... A[5] := 4.5; целтаб A [10:1]... A[5] := 4.5; [1:10] целтаб A[1:10]... A[15] := 'a' целтаб A[1:10]... A[15] := 'a'

6 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обращение к элементу массива A A массив НОМЕР элемента массива (ИНДЕКС) НОМЕР элемента массива (ИНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива: 2 ЗНАЧЕНИЕ элемента массива: 10

7 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Как обработать все элементы массива? 7 Объявление: Обработка: цел N = 5 целтаб A[1:N] цел N = 5 целтаб A[1:N] | обработать A[1] | обработать A[2] | обработать A[3] | обработать A[4] | обработать A[5] | обработать A[1] | обработать A[2] | обработать A[3] | обработать A[4] | обработать A[5] 1) если N велико (1000, )? 2) при изменении N программа не должна меняться! 1) если N велико (1000, )? 2) при изменении N программа не должна меняться! ?

8 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Как обработать все элементы массива? 8 Обработка с переменной: i:= 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 | обработать A[i] i:= i + 1 Обработка в цикле: i:= 1 нц пока i <= N | обработать A[i] i:= i + 1 кц i:= 1 нц пока i <= N | обработать A[i] i:= i + 1 кц Цикл с переменной: нц для i от 1 до N | обработать A[i] кц нц для i от 1 до N | обработать A[i] кц

9 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Заполнение массива 9 алг Массив нач цел i, N = 10 целтаб A[1:N] нц для i от 1 до N A[i]:= i*i кц кон алг Массив нач цел i, N = 10 целтаб A[1:N] нц для i от 1 до N A[i]:= i*i кц кон Чему равен A[9] ? ?

10 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Ввод с клавиатуры и вывод на экран 10 Объявление: Ввод с клавиатуры: Вывод на экран: цел N = 5, i целтаб A[1:N] цел N = 5, i целтаб A[1:N] нц для i от 1 до N вывод 'A[',i,']=' ввод A[i] кц нц для i от 1 до N вывод 'A[',i,']=' ввод A[i] кц A[1] = A[2] = A[3] = A[4] = A[5] = вывод 'Массив A', нс нц для i от 1 до N вывод A[i], ' ' кц вывод 'Массив A', нс нц для i от 1 до N вывод A[i], ' ' кц Зачем пробел? ?

11 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Заполнение случайными числами 11 нц для i от 1 до N A[i]:= irand(20,100) вывод A[i], ' ' кц нц для i от 1 до N A[i]:= irand(20,100) вывод A[i], ' ' кц Задача. Заполнить массив (псевдо)случайными целыми числами в диапазоне от 20 до 100.

12 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов 12 Общая схема: нц для i от 1 до N... | сделать что-то с A[i] кц нц для i от 1 до N... | сделать что-то с A[i] кц Подсчёт нужных элементов: Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше 180 см, но меньше 190 см? цел count = 0 нц для i от 1 до N если 180 < A[i] и A[i] < 190 то count:= count + 1 все кц цел count = 0 нц для i от 1 до N если 180 < A[i] и A[i] < 190 то count:= count + 1 все кц

13 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов 13 Среднее арифметическое: цел count = 0, sum = 0 нц для i от 1 до N если 180 < A[i] и A[i] < 190 то count:= count + 1 sum:= sum + A[i] все кц вывод sum/count цел count = 0, sum = 0 нц для i от 1 до N если 180 < A[i] и A[i] < 190 то count:= count + 1 sum:= sum + A[i] все кц вывод sum/count среднее арифметическое

14 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 14 «A»: Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений. Пример: Массив: Среднее арифметическое «B»: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые 50. Пример: Массив: Ср. арифм. элементов [0,50): Ср. арифм. элементов [50,100):

15 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 15 «C»: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку). Пример: Массив:

16 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 63. Алгоритмы обработки массивов 16

17 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Поиск в массиве 17 Найти элемент, равный X: i:= 1 нц пока A[i] <> X i:= i + 1 кц вывод 'A[',i,']=',X i:= 1 нц пока A[i] <> X i:= i + 1 кц вывод 'A[',i,']=',X Что плохо? ? i:= 1 нц пока и A[i] <> X i:= i + 1 кц если i <= N то вывод 'A[',i,']=',X иначе вывод 'Не нашли!' все i:= 1 нц пока и A[i] <> X i:= i + 1 кц если i <= N то вывод 'A[',i,']=',X иначе вывод 'Не нашли!' все Что если такого нет? ? i <= N должно быть первым!

18 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Поиск в массиве 18 nX:= 0 нц для i от 1 до N если A[i] = X то nX:= i все кц если nX > 0 то вывод 'A[',i,']=',X иначе вывод 'Не нашли!' все nX:= 0 нц для i от 1 до N если A[i] = X то nX:= i все кц если nX > 0 то вывод 'A[',i,']=',X иначе вывод 'Не нашли!' все Вариант с досрочным выходом: выход досрочный выход из цикла

19 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 19 «A»: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X. Пример: Массив: Что ищем: 2 Нашли: A[2]=2, A[5]=2 Пример: Массив: Что ищем: 6 Ничего не нашли.

20 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 20 «B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом. Пример: Массив: Есть: 3 Пример: Массив: Нет

21 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 21 «C»: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом. Пример: Массив: Есть: 3, 2 Пример: Массив: Нет

22 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Максимальный элемент 22 M:= A[1] нц для i от 2 до N если A[i] > M то M:= A[i] все кц вывод M M:= A[1] нц для i от 2 до N если A[i] > M то M:= A[i] все кц вывод M M:= A[1]; нц для i от 2 до N если A[i] > M то M:= A[i] все кц вывод 'A[',nMax,']=',M M:= A[1]; нц для i от 2 до N если A[i] > M то M:= A[i] все кц вывод 'A[',nMax,']=',M nMax:= 1 nMax:= i Что можно улучшить? ? Как найти его номер? ?

23 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Максимальный элемент и его номер 23 По номеру элемента можно найти значение! ! nMax:= 1 нц для i от 2 до N если A[i] > то nMax:= i все кц вывод 'A[',nMax,']=', nMax:= 1 нц для i от 2 до N если A[i] > то nMax:= i все кц вывод 'A[',nMax,']=', A[nMax]

24 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 24 «A»: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера. Пример: Массив: Минимальный элемент: A[1]=1 Максимальный элемент: A[5]=5 «B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера. Пример: Массив: Максимальный элемент: A[1]=5 Второй максимум: A[2]=5

25 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 25 «C»: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение. Пример: Массив: Максимальное значение 5 Количество элементов 3

26 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Реверс массива N-3N-2N-1N N-3N-2N-1N «Простое» решение: нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц div(N,2) Что плохо? ? остановиться на середине!

27 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Реверс массива 27 нц для 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 кц *Как обойтись без переменной c ? ?

28 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, N-3N-2N-1N Циклический сдвиг элементов N-3N-2N-1N «Простое» решение: 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 Что плохо? ? Почему не до N ? ?

29 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 29 «A»: Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент. Пример: Массив: Результат: «B»: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине. Пример: Массив: Результат:

30 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 30 «C»: Заполнить массив случайными числами в интервале [- 100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов. Пример: Массив: Результат: Количество положительных элементов: 3

31 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Отбор нужных элементов 31 «Простое» решение: Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B. нц для i от 1 до N если условие выполняется для A[i] то B[i]:= A[i] все кц нц для i от 1 до N если условие выполняется для A[i] то B[i]:= A[i] все кц Что плохо? ? A 12?34??46 B выбрать чётные элементы

32 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Отбор нужных элементов A ??? B выбрать чётные элементы count:= 0 | счётчик нц для i от 1 до N если mod(A[i],2) = 0 то count:= count + 1 все кц count:= 0 | счётчик нц для i от 1 до N если mod(A[i],2) = 0 то count:= count + 1 все кц нц для i от 1 до вывод B[i], ' ' кц нц для i от 1 до вывод B[i], ' ' кц count Как вывести на экран? ? Если A и B – один и тот же массив? ? B[count]:= A[i]

33 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 33 «A»: Заполнить массив случайными числами в интервале [-10,10] и отобрать в другой массив все чётные отрицательные числа. Пример: Массив А: Массив B: «B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым. Пример: Массив А: Массив B: 13 47

34 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 34 «C»: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи. Пример: Массив А: Массив B: 13 34

35 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 64. Сортировка 35

36 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что такое сортировка? 36 Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, … Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (QuickSort) сортировка «кучей» (HeapSort) сортировка слиянием (MergeSort) пирамидальная сортировка время работы N

37 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька (сортировка обменами) 37 Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает») сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1-й проход:

38 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька й проход: 3-й проход: й проход: Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов). !

39 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 39 1-й проход: нц для j от N-1 до 1 шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц нц для j от N-1 до 1 шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц 2-й проход: нц для j от N-1 до шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц нц для j от N-1 до шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц 2 единственное отличие!

40 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 40 нц для i от 1 до N-1 нц для j от N-1 до шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц нц для i от 1 до N-1 нц для j от N-1 до шаг -1 если A[j+1]< A[j] то | поменять местами A[j] и A[j+1] все кц i Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?

41 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 41 «A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива. «B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

42 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 42 Идея: найти минимальный элемент и поставить его на первое место. нц для i от 1 до N-1 | найти номер nMin минимального элемента | из A[i]..A[N] если i <> nMin то | поменять местами A[i] и A[nMin] все кц нц для i от 1 до N-1 | найти номер nMin минимального элемента | из A[i]..A[N] если i <> nMin то | поменять местами A[i] и A[nMin] все кц

43 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 43 нц для i от 1 до N-1 если i <> nMin то | поменять местами A[i] и A[nMin] все кц нц для i от 1 до N-1 если i <> nMin то | поменять местами A[i] и A[nMin] все кц nMin:= i нц для j от i+1 до N если A[j] < A[nMin] то nMin:= j все кц Как поменять местами два значения? ?

44 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 44 «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Пример: Массив: После сортировки:

45 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 45 «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример: Массив: После сортировки: Различных чисел: 5 «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

46 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка (QuickSort) 46 Ч.Э.Хоар Идея: выгоднее переставлять элементы, который находятся дальше друг от друга Для массива из N элементов нужно всего N/2 обменов! !

47 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 47 Шаг 2: переставить элементы так: при сортировке элементы не покидают « свою область»! Шаг 1: выбрать некоторый элемент массива X A[i] <= XA[i] >= X Шаг 3: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…) Как лучше выбрать X? ?

48 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 48 Разделение: 1)выбрать средний элемент массива ( X=67 ) 2)установить L:=1, R:=N 3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) 4)уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева) 5)если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп

49 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка LR LR LR RL L > R : разделение закончено! !

50 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 50 цел N = 7 целтаб A[1:N] алг Быстрая сортировка нач | заполнить массив qSort(1, N) | сортировка | вывести результат кон цел N = 7 целтаб A[1:N] алг Быстрая сортировка нач | заполнить массив qSort(1, N) | сортировка | вывести результат кон Основная программа: глобальные данные

51 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 51 алг qSort(цел nStart, nEnd) нач цел L, R, c, X если nStart >= nEnd то выход все L:= nStart; R:= nEnd X:= A[div(L+R,2)] | или X:= A[irand(L,R)] нц пока L <= R | разделение нц пока A[L] < X; L:= L + 1 кц нц пока A[R] > X; R:= R - 1 кц если L <= R то c:= A[L]; A[L]:= A[R]; A[R]:= c L:= L+1; R:= R-1 все кц qSort(nStart, R) | рекурсивные вызовы qSort(L, nEnd) кон алг qSort(цел nStart, nEnd) нач цел L, R, c, X если nStart >= nEnd то выход все L:= nStart; R:= nEnd X:= A[div(L+R,2)] | или X:= A[irand(L,R)] нц пока L <= R | разделение нц пока A[L] < X; L:= L + 1 кц нц пока A[R] > X; R:= R - 1 кц если L <= R то c:= A[L]; A[L]:= A[R]; A[R]:= c L:= L+1; R:= R-1 все кц qSort(nStart, R) | рекурсивные вызовы qSort(L, nEnd) кон

52 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 52 N метод пузырька метод выбора быстрая сортировка 10000,24 с 0,12 с 0,004 с 50005,3 с 2,9 с 0,024 с с 34 с 0,068 с Сортировка массива случайных значений:

53 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 53 «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки. Пример: Массив: После сортировки:

54 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 54 «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки. Пример: Массив: После сортировки: Различных чисел: 5

55 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 55 «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода. «D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

56 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 65. Двоичный поиск 56

57 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск X = 7X = 7 X = 7X = 7 X < 8X < X > 4X > X > 6 1. Выбрать средний элемент A[c] и сравнить с X. 2. Если X = A[c], то нашли (стоп). 3. Если X < A[c], искать дальше в первой половине. 4. Если X > A[c], искать дальше во второй половине. 1. Выбрать средний элемент A[c] и сравнить с X. 2. Если X = A[c], то нашли (стоп). 3. Если X < A[c], искать дальше в первой половине. 4. Если X > A[c], искать дальше во второй половине.

58 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 58 A[1]A[N]A[N+1] LRс LсR X = LсR LR L = R-1 : поиск завершен! !

59 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 59 цел L, R, c L:= 1; R:= N + 1 | начальный диапазон нц пока L < R-1 c:= div(L+R,2) | нашли середину если X < A[c] то R:= c | изменить диапазон иначе L:= c все кц если A[L] = X то вывод 'A[',L,']=',X иначе вывод 'Не нашли!' все цел L, R, c L:= 1; R:= N + 1 | начальный диапазон нц пока L < R-1 c:= div(L+R,2) | нашли середину если X < A[c] то R:= c | изменить диапазон иначе L:= c все кц если A[L] = X то вывод 'A[',L,']=',X иначе вывод 'Не нашли!' все

60 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 60 N линейный поиск двоичный поиск скорость выше, чем при линейном поиске нужна предварительная сортировка Когда нужно применять? ? Число сравнений:

61 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 61 «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений. Пример: Массив: После сортировки: Введите число X: 2 Число 2 найдено. Количество сравнений: 2

62 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 62 «B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве. Пример: Массив: После сортировки: Введите число X: 4 Число 4 встречается 2 раз(а). Пример: Массив: После сортировки: Введите число X: 14 Число 14 не встречается.

63 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 63 «C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X. Пример: Массив: После сортировки: Введите число X: 12 Число 12 найдено. Пример: Массив: После сортировки: Введите число X: 11 Число 11 не найдено. Ближайшее число 12.

64 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 66. Символьные строки 64

65 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Зачем нужны символьные строки? 65 симтаб s[1:80] | массив символов элементы массива – отдельные объекты сложно работать со строками переменной длины Хочется: строка – единый объект длина строки может меняться во время работы программы лит s | символьная строка литерный тип

66 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Символьные строки 66 Присваивание: s:= 'Вася пошёл гулять' Ввод с клавиатуры: ввод s Вывод на экран: вывод s А если массив? ? Отдельный символ: s[4]:= 'a' Длина строки: цел n n:= длин(s) цел n n:= длин(s) лит s

67 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Символьные строки 67 алг Замена а на б нач лит s вывод 'Введите строку: ' ввод s цел i нц для i от 1 до длин(s) если s[i] = 'а' то s[i]:= 'б' все кц вывод s кон алг Замена а на б нач лит s вывод 'Введите строку: ' ввод s цел i нц для i от 1 до длин(s) если s[i] = 'а' то s[i]:= 'б' все кц вывод s кон Задача: заменить в строке все буквы 'а' на буквы 'б'.

68 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 68 «A»: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные). Пример: Введите строку: аабб ААББссСС Результат: ббаа ББААссСС

69 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 69 «B»: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример: Введите строку: Вася пошел гулять Найдено слов: 3

70 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 70 «C»: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример: Введите строку: Вася пошел гулять Самое длинное слово: гулять, длина 6

71 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операции со строками 71 Объединение (конкатенация) : s1:= 'Привет' s2:= 'Вася' s := s1 + ', ' + s2 + '!' s1:= 'Привет' s2:= 'Вася' s := s1 + ', ' + s2 + '!' 'Привет, Вася!' Срез: s:= ' ' s1:= s[3:7] | '34567' s:= ' ' s1:= s[3:7] | '34567' с какого символа до какого символа

72 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операции со строками 72 Вставка: s:= ' ' вставить('ABC', s, 3) | '12ABC ' s:= ' ' вставить('ABC', s, 3) | '12ABC ' что куда с какого символа Удаление: s:= ' ' удалить(s, 3, 6) | '129' s:= ' ' удалить(s, 3, 6) | '129' с какого символа сколько символов

73 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Поиск в строках 73 s:= 'Здесь был Вася.' n:= позиция('с', s) если n > 0 то вывод 'Номер символа ', n иначе вывод 'Символ не найден.' все s:= 'Здесь был Вася.' n:= позиция('с', s) если n > 0 то вывод 'Номер символа ', n иначе вывод 'Символ не найден.' все что где Находит первое слева вхождение подстроки! !

74 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Пример обработки строк 74 Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы». Пример: Введите имя, отчество и фамилию: Василий Алибабаевич Хрюндиков Результат: Хрюндиков В.А. Алгоритм: найти первый пробел и выделить имя удалить имя с пробелом из основной строки найти первый пробел и выделить отчество удалить отчество с пробелом из основной строки «сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы… Алибабаевич Хрюндиков Хрюндиков Хрюндиков В.А.

75 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Пример обработки строк 75 алг FIO нач лит s, name, name2 цел n вывод 'Введите имя, отчество и фамилию' ввод s n:= позиция(' ', s); name:= s[1:n-1] | вырезать имя удалить(s, 1, n) n:= позиция(' ', s) name2:= s[1:n-1] | вырезать отчество удалить(s, 1, n) | осталась фамилия s:= s + ' ' + name[1] + '.' + name2[1] + '.' вывод s кон алг FIO нач лит s, name, name2 цел n вывод 'Введите имя, отчество и фамилию' ввод s n:= позиция(' ', s); name:= s[1:n-1] | вырезать имя удалить(s, 1, n) n:= позиция(' ', s) name2:= s[1:n-1] | вырезать отчество удалить(s, 1, n) | осталась фамилия s:= s + ' ' + name[1] + '.' + name2[1] + '.' вывод s кон

76 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 76 «A»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы. Пример: Введите фамилию, имя и отчество: Иванов Петр Семёнович П.С. Иванов

77 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 77 «B»: Ввести адрес файла и «разобрать» его на части, разделенные знаком '/'. Каждую часть вывести в отдельной строке. Пример: Введите адрес файла: C:/Фото/2013/Поход/vasya.jpg C: Фото 2013 Поход vasya.jpg

78 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 78 «C»: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую. Пример: Введите строку: (X > 0) and (Y Y) and (Z <> 5) Что меняем: and Чем заменить: & Результат (X > 0) & (Y Y) & (Z <> 5)

79 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Преобразования «строка» – «число» 79 Из строки в число: s:= '123' N:= лит_в_цел(s, OK) | N = 123 если не OK то вывод 'Ошибка!' все s:= ' '; X:= лит_в_вещ(s, OK) | X = если не OK то вывод 'Ошибка!' все s:= '123' N:= лит_в_цел(s, OK) | N = 123 если не OK то вывод 'Ошибка!' все s:= ' '; X:= лит_в_вещ(s, OK) | X = если не OK то вывод 'Ошибка!' все Из числа в строку: N:= 123 s:= цел_в_лит(N) | '123' X:= s:= вещ_в_лит(X) | ' ' N:= 123 s:= цел_в_лит(N) | '123' X:= s:= вещ_в_лит(X) | ' ' цел N, вещ X, лит s, лог OK да или нет

80 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 80 «A»: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые. Пример: Введите выражение: Ответ: 60 «B»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые. Пример: Введите выражение: Ответ: 54

81 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 81 «C»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / »). Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление ( div ). Пример: Введите выражение: 12*3+45 Ответ: 81

82 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 82 «D»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / ») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление ( div ). Пример: Введите выражение: 2*(3+45)+4 Ответ: 100

83 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Строки в процедурах и функциях 83 Задача: построить процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew. нц пока | слово wOld есть в строке s | удалить слово wOld из строки | вставить на это место слово wNew кц нц пока | слово wOld есть в строке s | удалить слово wOld из строки | вставить на это место слово wNew кц Что плохо? ? wOld: '12' wNew: 'A12B' зацикливание

84 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена всех экземпляров подстроки 84 s res б)б) wNew s res в)в) s г)г) wOld res s а)а) wNew

85 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена всех экземпляров подстроки 85 рабочая строка s результат res ' ''' '.12.12''A12B' '.12''A12B.A12B' '''A12B.A12B.A12B' алг Замена всех нач лит s = ' ' replaceAll(s, '12', 'A12B') вывод s кон алг Замена всех нач лит s = ' ' replaceAll(s, '12', 'A12B') вывод s кон

86 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена всех экземпляров подстроки 86 алг replaceAll(аргрез лит s, арг лит wOld, wNew) нач лит res; цел p, len len:= длин(wOld) res:= '' нц пока длин(s) > 0 p:= позиция(wOld, s) если p < 0 то res:= res + s; выход все если p > 1 то res:= res + s[1:p-1] все res:= res + wNew если p+len > длин(s) то s:= '' иначе s:= s[p+len:длин(s)] все кц s:= res кон алг replaceAll(аргрез лит s, арг лит wOld, wNew) нач лит res; цел p, len len:= длин(wOld) res:= '' нц пока длин(s) > 0 p:= позиция(wOld, s) если p < 0 то res:= res + s; выход все если p > 1 то res:= res + s[1:p-1] все res:= res + wNew если p+len > длин(s) то s:= '' иначе s:= s[p+len:длин(s)] все кц s:= res кон найти слово wOld не нашли… добавить то, что перед ним добавить wNew взять «хвост»

87 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена: из процедуры в функцию 87 алг Замена всех нач лит s = ' ' s:= replaceAll(s, '12', 'A12B') вывод s кон алг Замена всех нач лит s = ' ' s:= replaceAll(s, '12', 'A12B') вывод s кон алг лит replaceAll(лит s0, wOld, wNew) нач лит s s:= s0... | тело процедуры знач:= res кон алг лит replaceAll(лит s0, wOld, wNew) нач лит s s:= s0... | тело процедуры знач:= res кон

88 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 88 «A»: Напишите функцию, которая возвращает первое слово переданной ей символьной строки. Пример: Введите строку: Однажды в студёную зимнюю пору... Первое слово: Однажды

89 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 89 «B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение. Пример: Введите имя файла: qq Введите новое расширение: tmp Результат: qq.tmp Пример: Введите имя файла: qq.exe Введите новое расширение: tmp Результат: qq.tmp Пример: Введите имя файла: qq.work.xml Введите новое расширение: tmp Результат: qq.work.tmp

90 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 90 «C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа. Пример: Введите строку: В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов. Результат: В 2013 году в школе 123 состоялся очередной выпуск 11-х классов.

91 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Рекурсивный перебор 91 Задача. В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из K букв, которые можно построить из букв этого алфавита. Ы??? перебор K-1 символов Ш??? Ч??? 0??? задача для слов длины К сведена к задаче для слов длины К-1!

92 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Рекурсивный перебор 92 алг перебор К символов нач w[1]:='Ы' | перебор последних K-1 символов w[1]:='Ш' | перебор последних K-1 символов w[1]:='Ч' | перебор последних K-1 символов w[1]:='О' | перебор последних K-1 символов кон алг перебор К символов нач w[1]:='Ы' | перебор последних K-1 символов w[1]:='Ш' | перебор последних K-1 символов w[1]:='Ч' | перебор последних K-1 символов w[1]:='О' | перебор последних K-1 символов кон

93 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Рекурсивный перебор 93 алг ЫШЧО нач лит word = '...'; | из K символов TumbaWords('ЫШЧО', word, 0) кон алг ЫШЧО нач лит word = '...'; | из K символов TumbaWords('ЫШЧО', word, 0) кон алг TumbaWords(лит A, w0, цел N) нач если N = длин(w0) то | слово построено вывод w0, нс выход все цел i; лит w w:= w0 нц для i от 1 до длин(A) w[N+1]:= A[i] TumbaWords(A, w, N+1) | рекурсия кц кон алг TumbaWords(лит A, w0, цел N) нач если N = длин(w0) то | слово построено вывод w0, нс выход все цел i; лит w w:= w0 нц для i от 1 до длин(A) w[N+1]:= A[i] TumbaWords(A, w, N+1) | рекурсия кц кон уже установлено когда все символы уже установлены по всем символам алфавита алфавит слово

94 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 94 «A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов. «B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

95 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 95 «C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.

96 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сравнение строк 96 парпарк Пар?? Сравнение по кодам символов: AB...YZ CP UNCODE ab...yz CP UNCODE CP UNCODE

97 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сравнение строк 97 АБ...Ё ЮЯ CP UNCODE аб...ё юя CP UNCODE STEAM < STEAM < Steam < steam steam < ПАР < Пар < п Ар < пар < парк

98 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сортировка строк 98 алг Сортировка строк нач цел i, j, N = 10 литтаб S[1:N] лит s1 нц для i от 1 до N ввод S[i] кц... нц для i от 1 до N вывод S[i], нс кц кон алг Сортировка строк нач цел i, j, N = 10 литтаб S[1:N] лит s1 нц для i от 1 до N ввод S[i] кц... нц для i от 1 до N вывод S[i], нс кц кон нц для i от 1 до N-1 нц для j от N-1 до i шаг -1 если S[j+1] < S[j] то s1:= S[j] S[j]:= S[j+1] S[j+1]:= s1 все кц нц для i от 1 до N-1 нц для j от N-1 до i шаг -1 если S[j+1] < S[j] то s1:= S[j] S[j]:= S[j+1] S[j+1]:= s1 все кц массив строк

99 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 99 «A»: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке. Пример: Введите 5 строк: 1. тепловоз 2. арбуз 3. бурундук 4. кефир 5. урядник Список слов в алфавитном порядке: арбуз, бурундук, кефир, тепловоз, урядник

100 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 100 «B»: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке. Пример: Введите слова: 1. тепловоз 2. арбуз Список слов в алфавитном порядке: арбуз, тепловоз

101 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 101 «C»: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии. Пример: Введите ФИО: А.Г. Урядников Б.В. Тепловозов В.Д. Арбузов Список в алфавитном порядке: В.Д. Арбузов Б.В. Тепловозов А.Г. Урядников

102 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 67. Матрицы 102

103 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что такое матрица? Как закодировать? ? Матрица это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца. нет знака нолик крестик строка 2, столбец 3

104 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Объявление матриц 104 цел N = 3, M = 4 целтаб A[1:N, 1:M] вещтаб X[-3:0, -8:M] логтаб L[1:N, 0:1] цел N = 3, M = 4 целтаб A[1:N, 1:M] вещтаб X[-3:0, -8:M] логтаб L[1:N, 0:1] строки столбцы строки столбцы

105 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Простые алгоритмы 105 Заполнение случайными числами: нц для i от 1 до N нц для j от 1 до M A[i,j]:= irand(20,80) вывод A[i,j], ' ' кц вывод нс кц нц для i от 1 до N нц для j от 1 до M A[i,j]:= irand(20,80) вывод A[i,j], ' ' кц вывод нс кц Суммирование: s:= 0 нц для i от 1 до N нц для j от 1 до M s:= s + A[i,j] кц s:= 0 нц для i от 1 до N нц для j от 1 до M s:= s + A[i,j] кц Вложенный цикл! !

106 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 106 «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы. Пример: Матрица А: Максимальный элемент A[2,2]=87 Минимальный элемент A[3,4]=11

107 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 107 «B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму: 1)вычислить среднюю яркость пикселей по всему рисунку 2)все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255) Пример: Матрица А: Средняя яркость Результат:

108 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 108 «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:

109 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов матрицы 109 Главная диагональ: нц для i от 1 до N | работаем с A[i,i] кц нц для i от 1 до N | работаем с A[i,i] кц Побочная диагональ: нц для i от 1 до N | работаем с A[i,N+1-i] кц нц для i от 1 до N | работаем с A[i,N+1-i] кц Главная диагональ и под ней: нц для i от 1 до N нц для j от 1 до i | работаем с A[i,j] кц нц для i от 1 до N нц для j от 1 до i | работаем с A[i,j] кц

110 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перестановка строк я и 4-я строки: нц для j от 1 до M c:= A[2,j] A[2,j]:= A[4,j] A[4,j]:= c кц нц для j от 1 до M c:= A[2,j] A[2,j]:= A[4,j] A[4,j]:= c кц

111 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 111 «A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы. Пример: Матрица А: Результат:

112 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 112 «B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз: «С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

113 К.Ю. Поляков, Е.А. Ерёмин, Программирование на алгоритмическом языке § 68. Работа с файлами 113

114 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Как работать с файлами? 114 файлы текстовые двоичные «plain text»: текст, разбитый на строки; из специальных символов только символы перехода на новую строку любые символы рисунки, звуки, видео, …

115 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Принцип сэндвича 115 открыть файл работа с файлом закрыть файл хлеб начинка файл Fin, Fout Fin:= открыть на чтение('input.txt') Fout:= открыть на запись('output.txt') | здесь работаем с файлами закрыть(Fout) закрыть(Fin) файл Fin, Fout Fin:= открыть на чтение('input.txt') Fout:= открыть на запись('output.txt') | здесь работаем с файлами закрыть(Fout) закрыть(Fin) файловые переменные

116 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Ввод данных 116 цел a, b файл Fin Fin:= открыть на чтение('input.txt') закрыть(Fin) цел a, b файл Fin Fin:= открыть на чтение('input.txt') закрыть(Fin) начать чтение(Fin) ввод Fin, a, b Переход к началу открытого файла: если конец файла(Fin) вывод 'Данные кончились' все если конец файла(Fin) вывод 'Данные кончились' все Определение конца файла:

117 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Вывод данных в файл 117 цел a = 1, b = 2 файл Fout Fout:= открыть на запись('output.txt') закрыть(Fout) цел a = 1, b = 2 файл Fout Fout:= открыть на запись('output.txt') закрыть(Fout) вывод Fout, a, '+', b, '=', a+b

118 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Чтение неизвестного количества данных 118 нц пока | не конец файла | прочитать число из файла | добавить его к сумме кц нц пока | не конец файла | прочитать число из файла | добавить его к сумме кц Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму. цел x, S файл Fin Fin:= открыть на чтение('input.txt') S:= 0 нц пока не конец файла(Fin) ввод Fin, x S:= S + x кц закрыть(Fin) цел x, S файл Fin Fin:= открыть на чтение('input.txt') S:= 0 нц пока не конец файла(Fin) ввод Fin, x S:= S + x кц закрыть(Fin)

119 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 119 «A»: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл. «B»: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть. «C»: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.

120 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка массивов 120 Задача. В файле записано не более 100 целых чисел. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания. В чем отличие от предыдущей задачи? ? цел MAX = 100 целтаб A[1:MAX] цел MAX = 100 целтаб A[1:MAX] Для сортировки нужно удерживать все элементы в памяти одновременно. !

121 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка массивов 121 Ввод массива: файл Fin Fin:= открыть на чтение('input.txt') цел N N:= 0 | счётчик прочитанных данных нц пока не конец файла(Fin) и N:= N + 1 ввод Fin, A[N] кц закрыть(Fin) файл Fin Fin:= открыть на чтение('input.txt') цел N N:= 0 | счётчик прочитанных данных нц пока не конец файла(Fin) и N:= N + 1 ввод Fin, A[N] кц закрыть(Fin) N < MAX Зачем? ?

122 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка массивов 122 Вывод результата: файл Fout Fout:= открыть на запись('output.txt') нц для i от 1 до вывод Fout, A[i], нс кц закрыть(Fout) файл Fout Fout:= открыть на запись('output.txt') нц для i от 1 до вывод Fout, A[i], нс кц закрыть(Fout) N

123 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 123 «A»: В файле записано не более 100 чисел. Отсортировать их по возрастанию последней цифры и записать в другой файл. «B»: В файле записано не более 100 чисел. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа. «C»: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.

124 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка строк 124 Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода: Мухтар 4 немецкая овчарка Вывести в другой файл сведения о собаках, которым меньше 5 лет. нц пока не конец файла(Fin) | прочитать строку из файла Fin | разобрать строку – выделить возраст если возраст < 5 то | записать строку в файл Fout все кц нц пока не конец файла(Fin) | прочитать строку из файла Fin | разобрать строку – выделить возраст если возраст < 5 то | записать строку в файл Fout все кц

125 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка строк 125 | найти в строке пробел | удалить из строки кличку с первым пробелом | найти в строке пробел | выделить возраст перед пробелом | преобразовать возраст в числовой вид | найти в строке пробел | удалить из строки кличку с первым пробелом | найти в строке пробел | выделить возраст перед пробелом | преобразовать возраст в числовой вид Разбор строки: лит s, sAge цел age, p лог OK... | s = ' Мухтар 4 овчарка' p:= позиция(' ', s) | 'Мухтар 4 овчарка' s:= s[p+1:длин(s)] | s = '4 овчарка' p:= позиция (' ',s) | '4 овчарка' sAge:= s[1:p-1] | sAge = '4' age:= лит_в_цел(sAge, OK) | age = 4 лит s, sAge цел age, p лог OK... | s = ' Мухтар 4 овчарка' p:= позиция(' ', s) | 'Мухтар 4 овчарка' s:= s[p+1:длин(s)] | s = '4 овчарка' p:= позиция (' ',s) | '4 овчарка' sAge:= s[1:p-1] | sAge = '4' age:= лит_в_цел(sAge, OK) | age = 4 pp

126 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка строк 126 лит s, s0 нц пока не конец файла(Fin) ввод Fin, s0 s:= s0... | обработка строки s если age < 5 то вывод Fout, s0, нс все кц лит s, s0 нц пока не конец файла(Fin) ввод Fin, s0 s:= s0... | обработка строки s если age < 5 то вывод Fout, s0, нс все кц Зачем s0 ? ?

127 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 127 «A»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов. «B»: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией: П. Иванов И. Петров...

128 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 128 «C»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных: П. Иванов 98 И. Петров 96...

129 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

130 Алгоритмизация и программирование, Алг Язык, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Источники иллюстраций иллюстрации художников издательства «Бином» 3. авторские материалы