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

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Как обработать все элементы массива? 7 Объявление: Обработка: const N = 5; var A: array[1..N] of integer; const N = 5; var A: array[1..N] of integer; { обработать 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 программа не должна меняться! ?

Алгоритмизация и программирование, Паскаль, 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; while i <= N do begin { обработать A[i] } i:= i + 1; end; i:= 1; while i <= N do begin { обработать A[i] } i:= i + 1; end; Цикл с переменной: for i:=1 to N do begin { обработать A[i] } end; for i:=1 to N do begin { обработать A[i] } end;

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Заполнение массива 9 program Arr; const N = 10; var A: array[1..N] of integer; i: integer; begin for i:=1 to N do A[i]:= i*i; end. program Arr; const N = 10; var A: array[1..N] of integer; i: integer; begin for i:=1 to N do A[i]:= i*i; end. Чему равен A[9] ? ?

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Ввод с клавиатуры и вывод на экран 10 Объявление: Ввод с клавиатуры: Вывод на экран: const N = 5; var A: array[1..N] of integer; i: integer; const N = 5; var A: array[1..N] of integer; i: integer; for i:=1 to N do begin write('A[', i, ']='); read ( A[i] ) end; for i:=1 to N do begin write('A[', i, ']='); read ( A[i] ) end; A[1] = A[2] = A[3] = A[4] = A[5] = writeln('Массив A:'); for i:=1 to N do write(A[i]:4); writeln('Массив A:'); for i:=1 to N do write(A[i]:4); Зачем «:4»? ? Почему write ? ?

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Заполнение случайными числами 11 for i:=1 to N do begin A[i]:= 20 + random(81); write(A[i],' ') end; for i:=1 to N do begin A[i]:= 20 + random(81); write(A[i],' ') end; Задача. Заполнить массив (псевдо)случайными целыми числами в диапазоне от 20 до 100.

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов 12 Общая схема: for i:=1 to N do begin... { сделать что-то с A[i] } end; for i:=1 to N do begin... { сделать что-то с A[i] } end; Подсчёт нужных элементов: Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше 180 см, но меньше 190 см? count:= 0; for i:=1 to N do if (180 < A[i]) and (A[i] < 190) then count:= count + 1; count:= 0; for i:=1 to N do if (180 < A[i]) and (A[i] < 190) then count:= count + 1;

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов 13 Среднее арифметическое: count:= 0; sum:= 0; for i:=1 to N do if (180 < A[i]) and (A[i] < 190) then begin count:= count + 1; sum:= sum + A[i] end; write(sum/count); count:= 0; sum:= 0; for i:=1 to N do if (180 < A[i]) and (A[i] < 190) then begin count:= count + 1; sum:= sum + A[i] end; write(sum/count); среднее арифметическое

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Поиск в массиве 18 nX:= 0; for i:=1 to N do if A[i] = X then begin nX:= i; end; if nX > 0 then write('A[',i,']=',X) else write('Не нашли!'); nX:= 0; for i:=1 to N do if A[i] = X then begin nX:= i; end; if nX > 0 then write('A[',i,']=',X) else write('Не нашли!'); Вариант с досрочным выходом: break досрочный выход из цикла

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

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

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

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Реверс массива 27 for i:= 1 to N div 2 do begin c:= A[i]; A[i]:= A[N+1-i]; A[N+1-i]:= c; end; for i:= 1 to N div 2 do begin c:= A[i]; A[i]:= A[N+1-i]; A[N+1-i]:= c; end; *Как обойтись без переменной c ? ?

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, N-3N-2N-1N Циклический сдвиг элементов N-3N-2N-1N «Простое» решение: c:= A[1]; for i:= 1 to N-1 do A[i]:= A[i+1] A[N]:= c; c:= A[1]; for i:= 1 to N-1 do A[i]:= A[i+1] A[N]:= c; Что плохо? ? Почему не до N ? ?

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Отбор нужных элементов A ??? B выбрать чётные элементы count:= 0; { счётчик } for i:= 1 to N do if A[i] mod 2 = 0 then begin count:= count + 1; end; count:= 0; { счётчик } for i:= 1 to N do if A[i] mod 2 = 0 then begin count:= count + 1; end; for i:= 1 to do write(B[i], ' '); for i:= 1 to do write(B[i], ' '); count Как вывести на экран? ? Если A и B – один и тот же массив? ? B[count]:= A[i];

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

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 39 1-й проход: for j:= N-1 downto 1 do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for j:= N-1 downto 1 do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; 2-й проход: for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; 2 единственное отличие!

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 40 for i:= 1 to N-1 do for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for i:= 1 to N-1 do for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; i Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 42 Идея: найти минимальный элемент и поставить его на первое место. for i:= 1 to N-1 do begin { найти номер nMin минимального элемента из A[i]..A[N] } if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end; for i:= 1 to N-1 do begin { найти номер nMin минимального элемента из A[i]..A[N] } if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end;

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 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 иначе стоп

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 50 program QuickSort; const N = 7; var A: array[1..N] of integer;... begin { заполнить массив } qSort(1, N); { сортировка } { вывести результат } end; program QuickSort; const N = 7; var A: array[1..N] of integer;... begin { заполнить массив } qSort(1, N); { сортировка } { вывести результат } end; Основная программа: глобальные данные

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 51 procedure qSort(nStart, nEnd: integer); var L, R, c, X: integer; begin if nStart >= nEnd then Exit; L:= nStart; R:= nEnd; X:= A[(L+R) div 2]; { или X:= A[L+random(R-L+1)] } while L <= R do begin { разделение } while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L+1; R:= R-1 end end; qSort(nStart, R); { рекурсивные вызовы } qSort(L, nEnd) end; procedure qSort(nStart, nEnd: integer); var L, R, c, X: integer; begin if nStart >= nEnd then Exit; L:= nStart; R:= nEnd; X:= A[(L+R) div 2]; { или X:= A[L+random(R-L+1)] } while L <= R do begin { разделение } while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L+1; R:= R-1 end end; qSort(nStart, R); { рекурсивные вызовы } qSort(L, nEnd) end;

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

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

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

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

Алгоритмизация и программирование, Паскаль, 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], искать дальше во второй половине.

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 58 var L, R, c: integer;... L:= 1; R:= N + 1; { начальный диапазон } while L < R-1 do begin c:= (L+R) div 2; { нашли середину } if X < A[c] then R:= c { изменить диапазон } else L:= c; end; if A[L] = X then writeln('A[',L,']=',X) else writeln('Не нашли!') var L, R, c: integer;... L:= 1; R:= N + 1; { начальный диапазон } while L < R-1 do begin c:= (L+R) div 2; { нашли середину } if X < A[c] then R:= c { изменить диапазон } else L:= c; end; if A[L] = X then writeln('A[',L,']=',X) else writeln('Не нашли!')

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Зачем нужны символьные строки? 64 var s: array[1..80] of char; { массив символов } var s: array[1..80] of char; { массив символов } элементы массива – отдельные объекты сложно работать со строками переменной длины Хочется: строка – единый объект длина строки может меняться во время работы программы var s: string; { символьная строка } строка

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Символьные строки 66 program ReplaceAB; var s: string; i: integer; begin writeln('Введите строку'); readln(s); for i:=1 to Length(s) do if s[i]= 'а' then s[i]:= 'б'; writeln(s); end. program ReplaceAB; var s: string; i: integer; begin writeln('Введите строку'); readln(s); for i:=1 to Length(s) do if s[i]= 'а' then s[i]:= 'б'; writeln(s); end. Задача: заменить в строке все буквы 'а' на буквы 'б'.

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операции со строками 70 Объединение (конкатенация) : s1:= 'Привет'; s2:= 'Вася'; s := s1 + ', ' + s2 + '!'; s1:= 'Привет'; s2:= 'Вася'; s := s1 + ', ' + s2 + '!'; 'Привет, Вася!' Срез: s:= ' '; s1:= Copy(s, 3, 5); { '34567' } s:= ' '; s1:= Copy(s, 3, 5); { '34567' } с какого символа откуда 5 сколько символов сколько символов

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Пример обработки строк 74 program FIO; var s, name, name2: string; n: integer; begin write('Введите имя, отчество и фамилию: '); readln(s); n:= Pos(' ', s); name:= Copy(s, 1, n-1); { взять имя } Delete(s, 1, n); n:= Pos(' ', s); name2:= Copy(s, 1, n-1);{ взять отчество } Delete(s, 1, n); { осталась фамилия } s:= s + ' ' + name[1] + '.' + name2[1] + '.'; writeln(s) end. program FIO; var s, name, name2: string; n: integer; begin write('Введите имя, отчество и фамилию: '); readln(s); n:= Pos(' ', s); name:= Copy(s, 1, n-1); { взять имя } Delete(s, 1, n); n:= Pos(' ', s); name2:= Copy(s, 1, n-1);{ взять отчество } Delete(s, 1, n); { осталась фамилия } s:= s + ' ' + name[1] + '.' + name2[1] + '.'; writeln(s) end.

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Преобразования «строка» – «число» 78 Из строки в число: s:= '123'; Val(s, N, r); { N = 123 } s:= ' '; Val(s, X, r); { X = } s:= '123'; Val(s, N, r); { N = 123 } s:= ' '; Val(s, X, r); { X = } Из числа в строку: N:= 123; Str(N, s); { s = '123' } X:= ; Str(X, s); { s =' E+002' } Str(X:10:3, s); { s = ' ' } N:= 123; Str(N, s); { s = '123' } X:= ; Str(X, s); { s =' E+002' } Str(X:10:3, s); { s = ' ' } var N: integer; X: real; s: string; r: integer; var N: integer; X: real; s: string; r: integer; 0 или номер неверного символа

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена всех экземпляров подстроки 84 program Replace; var s: string;... { здесь будет процедура } begin s:= ' '; replaceAll(s, '12', 'A12B'); writeln(s) end; program Replace; var s: string;... { здесь будет процедура } begin s:= ' '; replaceAll(s, '12', 'A12B'); writeln(s) end; рабочая строка s результат res ' ''' '.12.12''A12B' '.12''A12B.A12B' '''A12B.A12B.A12B'

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена всех экземпляров подстроки 85 procedure replaceAll(var s: string; wOld, wNew: string); var res: string; p, len: integer; begin len:= Length(wOld); res:= ''; while Length(s) > 0 do begin p:= Pos(wOld, s); if p < 0 then begin res:= res + s; Exit; end; if p > 1 then res:= res + Copy(s,1,p-1); res:= res + wNew; if p+len > Length(s) then s:= '' else s:= Copy(s,p+len,Length(s)); end; s:= res end; procedure replaceAll(var s: string; wOld, wNew: string); var res: string; p, len: integer; begin len:= Length(wOld); res:= ''; while Length(s) > 0 do begin p:= Pos(wOld, s); if p < 0 then begin res:= res + s; Exit; end; if p > 1 then res:= res + Copy(s,1,p-1); res:= res + wNew; if p+len > Length(s) then s:= '' else s:= Copy(s,p+len,Length(s)); end; s:= res end; найти слово wOld не нашли… добавить то, что перед ним добавить wNew взять «хвост»

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Замена: из процедуры в функцию 86 program Replace; var s: string; begin s:= ' '; s:= replaceAll(s, '12', 'A12B'); writeln(s) end; program Replace; var s: string; begin s:= ' '; s:= replaceAll(s, '12', 'A12B'); writeln(s) end; function replaceAll(s, wOld, wNew: string): string;... begin... { тело процедуры } replaceAll:= res end; function replaceAll(s, wOld, wNew: string): string;... begin... { тело процедуры } replaceAll:= res end;

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Рекурсивный перебор 91 Перебор К символов var w: string; begin w[1]:='Ы'; { перебор последних K-1 символов } w[1]:='Ш'; { перебор последних K-1 символов } w[1]:='Ч'; { перебор последних K-1 символов } w[1]:='О'; { перебор последних K-1 символов } end; Перебор К символов var w: string; begin w[1]:='Ы'; { перебор последних K-1 символов } w[1]:='Ш'; { перебор последних K-1 символов } w[1]:='Ч'; { перебор последних K-1 символов } w[1]:='О'; { перебор последних K-1 символов } end;

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Рекурсивный перебор 92 program YSCHO; var word: string; begin word:= '...'; TumbaWords('ЫШЧО', word, 0); end. program YSCHO; var word: string; begin word:= '...'; TumbaWords('ЫШЧО', word, 0); end. procedure TumbaWords(A, w: string; N: integer); var i: integer; begin if N = Length(w) then begin writeln(w); exit; end; for i:=1 to Length(A) do begin w[N+1]:= A[i]; TumbaWords(A, w, N+1); end; procedure TumbaWords(A, w: string; N: integer); var i: integer; begin if N = Length(w) then begin writeln(w); exit; end; for i:=1 to Length(A) do begin w[N+1]:= A[i]; TumbaWords(A, w, N+1); end; уже установлено когда все символы уже установлены по всем символам алфавита алфавит слово

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сортировка строк 97 const N = 10; var i,j: integer; s1: string; S: array[1..N] of string; begin for i:= 1 to N do readln(S[i]); for i:= 1 to N do writeln(S[i]); end. const N = 10; var i,j: integer; s1: string; S: array[1..N] of string; begin for i:= 1 to N do readln(S[i]); for i:= 1 to N do writeln(S[i]); end. for i:= 1 to N-1 do for j:= N-1 downto i do if S[j+1] < S[j] then begin s1:= S[j]; S[j]:= S[j+1]; S[j+1]:= s1; end; for i:= 1 to N-1 do for j:= N-1 downto i do if S[j+1] < S[j] then begin s1:= S[j]; S[j]:= S[j+1]; S[j+1]:= s1; end; массив строк

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

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Объявление матриц 103 const N = 3; M = 4; var A: array[1..N, 1..M] of integer; X: array[-3..0, -8..M] of double; L: array[1..N, 0..1] of boolean; const N = 3; M = 4; var A: array[1..N, 1..M] of integer; X: array[-3..0, -8..M] of double; L: array[1..N, 0..1] of boolean; строки столбцы строки столбцы

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Простые алгоритмы 104 Заполнение случайными числами: for i:=1 to N do begin for j:=1 to M do begin A[i,j]:= random(61) + 20; write(A[i,j]:3) end; writeln end; for i:=1 to N do begin for j:=1 to M do begin A[i,j]:= random(61) + 20; write(A[i,j]:3) end; writeln end; Суммирование: s:= 0; for i:=1 to N do for j:=1 to M do s:= s + A[i,j]; s:= 0; for i:=1 to N do for j:=1 to M do s:= s + A[i,j]; Вложенный цикл! !

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перебор элементов матрицы 108 Главная диагональ: for i:= 1 to N do begin { работаем с A[i,i] } end; for i:= 1 to N do begin { работаем с A[i,i] } end; Побочная диагональ: for i:= 1 to N do begin { работаем с A[i,N+1-i] } end; for i:= 1 to N do begin { работаем с A[i,N+1-i] } end; Главная диагональ и под ней: for i:= 1 to N do for j:= 1 to i do begin { работаем с A[i,j] } end; for i:= 1 to N do for j:= 1 to i do begin { работаем с A[i,j] } end;

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Перестановка строк я и 4-я строки: for j:= 1 to M do c:= A[2,j]; A[2,j]:= A[4,j]; A[4,j]:= c end; for j:= 1 to M do c:= A[2,j]; A[2,j]:= A[4,j]; A[4,j]:= c end;

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Принцип сэндвича 114 var Fin, Fout: Text; Assign(Fin, 'input.txt'); Assign(Fout, 'output.txt'); Reset(Fin); { открыть на чтение } Rewrite(Fout); { открыть на запись } { здесь работаем с файлами } Close(Fout); { закрыть файлы } Close(Fin); var Fin, Fout: Text; Assign(Fin, 'input.txt'); Assign(Fout, 'output.txt'); Reset(Fin); { открыть на чтение } Rewrite(Fout); { открыть на запись } { здесь работаем с файлами } Close(Fout); { закрыть файлы } Close(Fin); файловые переменные связать с файлами открыть файл работа с файлом закрыть файл хлеб начинка

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Ввод данных 115 var a, b: integer; Fin: Text;... Assign(Fin, 'input.txt'); Reset(Fin); Close(Fin); var a, b: integer; Fin: Text;... Assign(Fin, 'input.txt'); Reset(Fin); Close(Fin); Reset(Fin); Close(Fin); Reset(Fin); readln(Fin, a, b); Переход к началу открытого файла: if Eof(Fin) then { end of file } write('Данные кончились'); if Eof(Fin) then { end of file } write('Данные кончились'); Определение конца файла:

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Чтение неизвестного количества данных 117 while { не конец файла } do begin { прочитать число из файла } { добавить его к сумме } end; while { не конец файла } do begin { прочитать число из файла } { добавить его к сумме } end; Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму. var x, S: integer; Fin: Text;... Assign(Fin,'input.txt'); Reset(Fin); S:= 0; while not Eof(Fin) do begin readln(Fin, x); S:= S + x; end; Close(Fin); var x, S: integer; Fin: Text;... Assign(Fin,'input.txt'); Reset(Fin); S:= 0; while not Eof(Fin) do begin readln(Fin, x); S:= S + x; end; Close(Fin);

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка массивов 120 Ввод массива: var N: integer; Fin: Text;... Assign(Fin,'input.txt'); Reset(Fin); N:= 0; while (not Eof(Fin)) and do begin N:= N + 1; readln(Fin, A[N]); end; Close(Fin); var N: integer; Fin: Text;... Assign(Fin,'input.txt'); Reset(Fin); N:= 0; while (not Eof(Fin)) and do begin N:= N + 1; readln(Fin, A[N]); end; Close(Fin); (N < MAX) Зачем? ? счётчик прочитанных данных

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка массивов 121 Вывод результата: var Fout: Text;... Assign(Fout, 'output.txt'); Rewrite(Fout); for i:= 1 to do writeln(Fout, A[i]); Close(Fout); var Fout: Text;... Assign(Fout, 'output.txt'); Rewrite(Fout); for i:= 1 to do writeln(Fout, A[i]); Close(Fout); N

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка строк 124 { найти в строке пробел } { удалить из строки кличку с первым пробелом } { найти в строке пробел } { выделить возраст перед пробелом } { преобразовать возраст в числовой вид } { найти в строке пробел } { удалить из строки кличку с первым пробелом } { найти в строке пробел } { выделить возраст перед пробелом } { преобразовать возраст в числовой вид } Разбор строки: var s, sAge: string; age, p, r: integer;... { s = 'Мухтар 4 овчарка' } p:= Pos(' ', s); { 'Мухтар 4 овчарка' } Delete(s, 1, p); { s = '4 овчарка' } p:= Pos(' ', s); { '4 овчарка' } sAge:= Copy(s, 1, p-1); { sAge = '4' } Val(sAge, age, r); { age = 4 } var s, sAge: string; age, p, r: integer;... { s = 'Мухтар 4 овчарка' } p:= Pos(' ', s); { 'Мухтар 4 овчарка' } Delete(s, 1, p); { s = '4 овчарка' } p:= Pos(' ', s); { '4 овчарка' } sAge:= Copy(s, 1, p-1); { sAge = '4' } Val(sAge, age, r); { age = 4 } pp

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обработка строк 125 var s, s0: string;... while not Eof(Fin) do begin readln(Fin, s0); s:= s0; { обработка строки s } if age < 5 then writeln(Fout, s0); end; var s, s0: string;... while not Eof(Fin) do begin readln(Fin, s0); s:= s0; { обработка строки s } if age < 5 then writeln(Fout, s0); end; Зачем s0 ? ?

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

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

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

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