1 Программирование на алгоритмическом языке § 62. Массивы § 63. Алгоритмы обработки массивов § 64. Сортировка § 65. Двоичный поиск § 66. Символьные строки § 67. Матрицы § 68. Работа с файлами
§ 62. Массивы 2
3 Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер. Надо : Как ввести 10000 переменных? ? выделять память записывать данные в нужную ячейку читать данные из ячейки
4 целтаб A[ 1 : 5 ] вещтаб V[ 0 : 5 ] логтаб L[ -5 : 5 ] симтаб S[ 65 : 90 ] Массив = таблица ! ! минимальный индекс максимальный индекс цел N = 10 целтаб A[ 1 : N ] размер через константу Зачем? ?
5 целтаб A [ 10 : 1 ] ... A[ 5 ] := 4.5 ; [ 1 : 10 ] целтаб A[ 1 : 10 ] ... A[ 15 ] := 'a'
6 5 10 15 20 25 1 2 3 4 5 A массив 3 15 НОМЕР элемента массива (ИНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива : 2 ЗНАЧЕНИЕ элемента массива : 10
7 Объявление : Обработка : цел N = 5 целтаб A[ 1 :N] | обработать A[1] | обработать A[2] | обработать A[3] | обработать A[4] | обработать A[5] 1) если N велико (1000, 1000000)? 2) при изменении N программа не должна меняться! ?
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:= i + 1 Обработка в цикле: i:= 1 нц пока i <= N | обработать A[i] i:= i + 1 кц Цикл с переменной: нц для i от 1 до N | обработать A[i] кц
9 алг Массив нач цел i, N = 10 целтаб A [ 1 : N ] нц для i от 1 до N A[i]:= i*i кц кон Чему равен A[9] ? ?
10 Объявление: Ввод с клавиатуры: Вывод на экран: цел N = 5, i целтаб A[ 1 :N] нц для i от 1 до N вывод ' A[ ',i, ' ]= ' ввод A[i] кц A[1] = A[2] = A[3] = A[4] = A[5] = 5 12 34 56 13 вывод ' Массив A', нс нц для i от 1 до N вывод A[i], ' ' кц Зачем пробел? ?
11 нц для i от 1 до N A[i]:= irand ( 20, 100 ) вывод A[i], ' ' кц Задача. Заполнить массив (псевдо)случайными целыми числами в диапазоне от 20 до 100.
12 Общая схема: нц для i от 1 до N ... | сделать что-то с A[i] кц Подсчёт нужных элементов: Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше 180 см, но меньше 190 см? цел count = 0 нц для i от 1 до N если 180 < A[ i ] и A[ i ] < 190 то count:= count + 1 все кц
13 Среднее арифметическое: цел count = 0, sum = 0 нц для i от 1 до N если 180 < A[ i ] и A[ i ] < 190 то count:= count + 1 sum := sum + A[ i ] все кц вывод sum/count среднее арифметическое
14 « A »: Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений. Пример : Массив: 1 2 3 4 5 Среднее арифметическое 3.000 « B »: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50. Пример : Массив: 3 2 52 4 60 Ср. арифм. элементов [0,50): 3.000 Ср. арифм. элементов [50,100 ] : 56.000
15 « C »: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку). Пример : Массив: 3 2 1 4 5
§ 63. Алгоритмы обработки массивов 16
17 Найти элемент, равный 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 <= N должно быть первым!
18 nX:= 0 нц для i от 1 до N если A[ i ] = X то nX:= i все кц если nX > 0 то вывод 'A[', i, ']=',X иначе вывод 'Не нашли!' все Вариант с досрочным выходом: выход досрочный выход из цикла
19 « A »: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X. Пример : Массив: 1 2 3 1 2 Что ищем: 2 Нашли: A[2]=2, A[5]=2 Пример : Массив: 1 2 3 1 2 Что ищем: 6 Ничего не нашли.
20 « B »: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом. Пример : Массив: 1 2 3 3 2 1 Есть: 3 Пример : Массив: 1 2 3 4 2 1 Нет
21 « C »: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом. Пример : Массив: 3 2 1 3 2 5 Есть: 3, 2 Пример : Массив: 3 2 1 4 0 5 Нет
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] все кц вывод ' A[',nMax, ']=',M nMax:= 1 nMax:= i Что можно улучшить? ? Как найти его номер? ?
23 По номеру элемента можно найти значение! ! nMax:= 1 нц для i от 2 до N если A[i] > то nMax := i все кц вывод ' A[',nMax, ']=', A[nMax] A[nMax]
24 « A »: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера. Пример : Массив: 1 2 3 4 5 Минимальный элемент: A[1]=1 Максимальный элемент: A[5]=5 « B »: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера. Пример : Массив: 5 5 3 4 1 Максимальный элемент: A[1]=5 Второй максимум: A[2]=5
25 « C »: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение. Пример : Массив: 3 4 5 5 3 4 5 Максимальное значение 5 Количество элементов 3
26 1 2 3 4 N-3 N-2 N -1 N 7 12 5 8 18 34 40 23 1 2 3 4 N-3 N-2 N -1 N 23 40 34 18 8 5 12 7 « Простое » решение: нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц div (N, 2 ) Что плохо? ? остановиться на середине!
27 нц для i от 1 до div (N, 2 ) c:= A[i] A[i]:= A[N+ 1 -i] A[N+ 1 -i]:= c кц * Как обойтись без переменной c ? ?
1 2 3 4 N-3 N-2 N -1 N 12 5 8 15 34 40 23 7 Циклический сдвиг элементов 28 1 2 3 4 N-3 N-2 N -1 N 7 12 5 8 18 34 40 23 « Простое » решение: c:= A[ 1 ] нц для i от 1 до N- 1 A[i]:= A[i+ 1 ] кц A[N]:= c Что плохо? ? Почему не до N ? ?
29 « A »: Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент. Пример : Массив: 1 2 3 4 5 6 Результат: 6 1 2 3 4 5 « B »: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине. Пример : Массив: 1 2 3 4 5 6 Результат: 3 2 1 6 5 4
30 « C »: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов. Пример : Массив: 20 -90 15 -34 10 0 Результат: 20 15 10 -90 -34 0 Количество положительных элементов: 3
31 « Простое » решение: Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B. нц для i от 1 до N если условие выполняется для A[ i ] то B[ i ]:= A[ i ] все кц Что плохо? ? 1 2 3 4 5 6 12 3 34 11 23 46 A 12 ? 34 ? ? 46 B выбрать чётные элементы
32 1 2 3 4 5 6 12 3 34 11 23 46 A 12 34 46 ? ? ? B выбрать чётные элементы count:= 0 | счётчик нц для i от 1 до N если mod (A[ i ], 2 ) = 0 то count:= count + 1 все кц нц для i от 1 до вывод B[i], ' ' кц count Как вывести на экран? ? Если A и B – один и тот же массив? ? B[count]:= A[i]
33 « A »: Заполнить массив случайными числами в интервале [-10,10] и отобрать в другой массив все чётные отрицательные числа. Пример : Массив А: -5 6 7 -4 -6 8 -8 Массив B: -4 -6 -8 « B »: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым. Пример : Массив А: 12 13 85 96 47 Массив B: 13 47
34 « C »: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи. Пример : Массив А: 12 13 85 34 47 Массив B: 13 34
§ 64. Сортировка 35
36 Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, … Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» ( QuickSort ) сортировка «кучей» ( HeapSort ) сортировка слиянием ( MergeSort ) пирамидальная сортировка время работы N
37 Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх ( «всплывает» ). 4 5 2 1 3 4 5 2 1 3 4 5 1 2 3 1 4 5 2 3 сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1-й проход : 4 1 5 2 3
38 1 4 5 2 3 1 4 5 2 3 1 4 2 5 3 2-й проход : 3-й проход : 1 2 4 5 3 1 2 3 4 5 1 2 4 5 3 4 -й проход : 1 2 3 4 5 1 2 3 4 5 1 2 4 3 5 Для сортировки массива из N элементов нужен N -1 проход (достаточно поставить на свои места N-1 элементов). !
39 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] все кц 2 единственное отличие!
40 нц для i от 1 до N-1 нц для j от N- 1 до шаг -1 если A[j+ 1 ]< A[j] то | поменять местами A[j] и A[j+1] все кц кц i Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?
41 « A »: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива. « B »: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.
42 Идея : найти минимальный элемент и поставить его на первое место. нц для i от 1 до N- 1 | найти номер nMin минимального элемента | из A[i]..A[N] если i <> nMin то | поменять местами A[i] и A[nMin] все кц
43 нц для i от 1 до N- 1 если i <> nMin то | поменять местами A[i] и A[nMin] все кц nMin := i нц для j от i+ 1 до N если A[j] < A[ nMin ] то nMin := j все кц Как поменять местами два значения? ?
44 « A »: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Пример : Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1
45 « B »: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример : Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5 « C »: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.
46 Ч.Э.Хоар Идея : выгоднее переставлять элементы, который находятся дальше друг от друга. 6 5 4 3 2 1 1 5 4 3 2 6 1 2 4 3 5 6 1 2 3 4 5 6 Для массива из N элементов нужно всего N/2 обменов! !
47 Шаг 2 : переставить элементы так: при сортировке элементы не покидают « свою область»! Шаг 1 : выбрать некоторый элемент массива X A[ i ] <= X A[ i ] >= X Шаг 3 : так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer ) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов ( для этого надо отсортировать массив… ). 78 6 82 67 55 44 34 Как лучше выбрать X ? ?
48 Разделение : выбрать средний элемент массива ( X =67 ) установить L:=1, R:=N увеличивая L, найти первый элемент A[L], который >= X ( должен стоять справа ) уменьшая R, найти первый элемент A[R], который <= X ( должен стоять слева ) если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп. 78 6 82 67 55 44 34
49 78 6 82 67 55 44 34 L R 34 6 82 67 55 44 78 L R 34 6 44 67 55 82 78 L R 34 6 44 55 67 82 78 R L L > R : разделение закончено! !
50 цел N = 7 целтаб A[ 1 :N] алг Быстрая сортировка нач | заполнить массив qSort (1, N) | сортировка | вывести результат кон Основная программа : глобальные данные
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 ) кон
52 N метод пузырька метод выбора быстрая сортировка 1000 0, 2 4 с 0, 12 с 0, 004 с 5000 5,3 с 2, 9 с 0, 024 с 15000 4 5 с 3 4 с 0, 068 с Сортировка массива случайных значений :
53 « A »: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки. Пример : Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1
54 « B »: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки. Пример : Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5
55 « C »: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода. « D »: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).
§ 65. Двоичный поиск 56
57 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 X = 7 X < 8 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 X > 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 6 X > 6 Выбрать средний элемент A[c] и сравнить с X. Если X = A[c], то нашли ( стоп ). Если X < A[c], искать дальше в первой половине. Если X > A[c], искать дальше во второй половине.
58 A[1] A[N] A[N+1] 6 34 44 55 67 78 82 L R с 6 34 44 55 67 78 82 L с R X = 44 6 34 44 55 67 78 82 L с R 6 34 44 55 67 78 82 L R L = R-1 : поиск завершен! !
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 иначе вывод 'Не нашли!' все
60 N линейный поиск двоичный поиск 2 2 2 16 16 5 1024 1024 11 1048576 1048576 21 скорость выше, чем при линейном поиске нужна предварительная сортировка Когда нужно применять? ? Число сравнений :
61 « A »: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 2 Число 2 найдено. Количество сравнений: 2
62 « B »: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 4 Число 4 встречается 2 раз(а). Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 7 9 Введите число X: 14 Число 14 не встречается.
63 « C »: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 12 19 Введите число X: 12 Число 12 найдено. Пример : Массив: 1 4 7 3 9 2 4 5 2 После сортировки: 1 2 2 3 4 4 5 12 19 Введите число X: 11 Число 11 не найдено. Ближайшее число 12.
§ 66. Символьные строки 64
65 симтаб s[ 1 : 80 ] | массив символов элементы массива – отдельные объекты сложно работать со строками переменной длины Хочется : строка – единый объект длина строки может меняться во время работы программы лит s | символьная строка лит ерный тип
66 Присваивание : s:= ' Вася пошёл гулять' Ввод с клавиатуры : ввод s Вывод на экран : вывод s А если массив? ? Отдельный символ : s[ 4 ]:= 'a' Длина строки : цел n n:= длин ( s ) лит s
67 алг Замена а на б нач лит s вывод 'Введите строку: ' ввод s цел i нц для i от 1 до длин ( s ) если s [ i ] = 'а' то s [ i ]:= 'б' все кц вывод s кон Задача : заменить в строке все буквы ' а ' на буквы ' б '.
68 « A »: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные). Пример : Введите строку: ааббААББссСС Результат: ббааББААссСС
69 « B »: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример : Введите строку: Вася пошел гулять Найдено слов: 3
70 « C »: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы. Пример : Введите строку: Вася пошел гулять Самое длинное слово: гулять, длина 6
71 Объединение (конкатенация) : s1:= ' Привет' s2:= ' Вася' s := s1 + ', ' + s2 + '!' ' Привет, Вася!' Срез : s:= '123456789' s1:= s[ 3 : 7 ] | '34567' с какого символа до какого символа
72 Вставка : s:= '123456789' вставить ( ' ABC', s, 3 ) | '12 ABC 3456789 ' что куда с какого символа Удаление : s:= '123456789' удалить ( s, 3, 6 ) | '129' с какого символа сколько символов
73 s:= 'Зде с ь был Вася.' n:= позиция ( 'с', s ) если n > 0 то вывод 'Номер символа ', n иначе вывод 'Символ не найден.' все что где Находит первое слева вхождение подстроки! !
74 Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы». Пример: Введите имя, отчество и фамилию: Василий Алибабаевич Хрюндиков Результат: Хрюндиков В.А. Алгоритм: найти первый пробел и выделить имя удалить имя с пробелом из основной строки найти первый пробел и выделить отчество удалить отчество с пробелом из основной строки «сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы… Алибабаевич Хрюндиков Хрюндиков Хрюндиков В.А.
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 кон
76 « A »: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы. Пример : Введите фамилию, имя и отчество: Иванов Петр Семёнович П.С. Иванов
77 « B »: Ввести адрес файла и «разобрать» его на части, разделенные знаком '/'. Каждую часть вывести в отдельной строке. Пример : Введите адрес файла: C:/Фото/2013/Поход/vasya.jpg C: Фото 2013 Поход vasya.jpg
78 « C »: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую. Пример : Введите строку: (X > 0) and (Y < X) and (Z > Y) and (Z <> 5) Что меняем: and Чем заменить: & Результат (X > 0) & (Y < X) & (Z > Y) & (Z <> 5)
79 Из строки в число: s:= ' 123 ' N:= лит_в_цел (s, OK) | N = 123 если не OK то вывод ' Ошибка! ' все s:= '123.456' ; X:= лит_в_вещ (s, OK) | X = 123.456 если не OK то вывод ' Ошибка! ' все Из числа в строку: N:= 1 23 s:= цел_в_лит (N) | '123' X:= 123.456 s:= вещ_в_лит (X) | '123.456' цел N, вещ X, лит s, лог OK да или нет
80 « A »: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые. Пример : Введите выражение: 12+3+45 Ответ: 60 « B »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые. Пример : Введите выражение: 12-3+45 Ответ: 54
81 « C »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / »). Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление ( div ). Пример : Введите выражение: 12*3+45 Ответ: 81
82 « D »: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки « + », « – », « * » и « / ») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция « / » выполняется как целочисленное деление ( div ). Пример : Введите выражение: 2*(3+45)+4 Ответ: 100
83 Задача : построить процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew. нц пока | слово wOld есть в строке s | удалить слово wOld из строки | вставить на это место слово wNew кц Что плохо? ? wOld : '12' wNew: 'A 12 B' зацикливание
84 s res б ) wNew s res в ) s res г ) wOld res s а ) wNew
85 рабочая строка s результат res '12.12.12' '' '.12.12' ' A 12 B ' '.12' 'A12B.A12B' '' 'A12B.A12B.A12B' алг Замена всех нач лит s = '12.12.12' replaceAll (s, '12', 'A12B' ) вывод s кон
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 кон найти слово wOld не нашли… добавить то, что перед ним добавить wNew взять «хвост»
87 алг Замена всех нач лит s = '12.12.12' s:= replaceAll (s, '12', 'A12B' ) вывод s кон алг лит replaceAll ( лит s0, wOld, wNew ) нач лит s s:= s0 ... | тело процедуры знач := res кон
88 « A »: Напишите функцию, которая возвращает первое слово переданной ей символьной строки. Пример : Введите строку: Однажды в студёную зимнюю пору... Первое слово: Однажды
89 « B »: Напишите функцию, которая заменяет расширение файла на заданное новое расширение. Пример : Введите имя файла: qq Введите новое расширение: tmp Результат: qq.tmp Пример : Введите имя файла: qq.exe Введите новое расширение: tmp Результат: qq.tmp Пример : Введите имя файла: qq.work.xml Введите новое расширение: tmp Результат: qq.work.tmp
90 « C »: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа. Пример : Введите строку: В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов. Результат: В 2013 году в школе 123 состоялся очередной выпуск 11 классов.
91 Задача. В алфавите языке племени «тумба-юмба» четыре буквы: « Ы », « Ш », « Ч » и « О ». Нужно вывести на экран все слова, состоящие из K букв, которые можно построить из букв этого алфавита. Ы ? ? ? перебор K-1 символов Ш ? ? ? Ч ? ? ? 0 ? ? ? задача для слов длины К сведена к задаче для слов длины К-1!
92 алг перебор К символов нач w [1]:= 'Ы' | перебор последних K-1 символов w [1]:= 'Ш' | перебор последних K-1 символов w [1]:= 'Ч' | перебор последних K-1 символов w [1]:= 'О' | перебор последних K-1 символов кон
93 алг ЫШЧО нач лит 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 ) | рекурсия кц кон уже установлено когда все символы уже установлены по всем символам алфавита алфавит слово
94 « A »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов. « B »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.
95 « C »: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.
96 пар парк Пар ? ? Сравнение по кодам символов: A B ... Y Z CP-1251 65 66 ... 89 90 UNCODE 65 66 ... 89 90 a b ... y z CP-1251 97 98 ... 121 122 UNCODE 97 98 ... 121 122 0 1 ... 8 9 CP-1251 48 49 ... 56 57 UNCODE 48 49 ... 56 57
97 А Б ... Ё ... Ю Я CP-1251 192 193 ... 168 ... 222 223 UNCODE 1040 1041 ... 1025 ... 1070 1071 а б ... ё ... ю я CP-1251 224 225 ... 184 ... 254 255 UNCODE 1072 1073 ... 1105 ... 1102 1103 5STEAM < S TEAM < S t eam < s team steam < П АР < П а р < п Ар < п а р < пар к
98 алг Сортировка строк нач цел 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 все кц кц массив строк
99 « A »: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке. Пример : Введите 5 строк: 1. тепловоз 2. арбуз 3. бурундук 4. кефир 5. урядник Список слов в алфавитном порядке: арбуз, бурундук, кефир, тепловоз, урядник
100 « B »: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке. Пример : Введите слова: 1. тепловоз 2. арбуз Список слов в алфавитном порядке: арбуз, тепловоз
101 « C »: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии. Пример : Введите ФИО: А.Г. Урядников Б.В. Тепловозов В.Д. Арбузов Список в алфавитном порядке: В.Д. Арбузов Б.В. Тепловозов А.Г. Урядников
§ 67. Матрицы 102
103 1 2 3 1 -1 0 1 2 -1 0 1 3 0 1 -1 Как закодировать? ? Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца. нет знака нолик крестик строка 2, столбец 3
104 цел N = 3, M = 4 целтаб A[ 1 :N, 1 :M] вещ таб X[ -3 : 0, -8 :M] логтаб L[ 1 :N, 0 : 1 ] строки столбцы строки столбцы
105 Заполнение случайными числами: нц для 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 ] кц кц Вложенный цикл! !
106 « A »: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы. Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 11 40 12 35 15 Максимальный элемент A[2,2]=87 Минимальный элемент A[3,4]=11
107 « B »: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму: вычислить среднюю яркость пикселей по всему рисунку все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255) Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 11 40 12 35 15 Средняя яркость 37.88 Результат: 0 0 255 255 0 255 0 255 255 255 0 0 255 0 0 0
108 «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:
109 Главная диагональ: нц для i от 1 до N | работаем с A[ i,i ] кц Побочная диагональ: нц для i от 1 до N | работаем с A[ i, N+1-i ] кц Главная диагональ и под ней: нц для i от 1 до N нц для j от 1 до i | работаем с A[ i,j ] кц кц
110 2-я и 4-я строки: нц для j от 1 до M c:= A[ 2,j] A[ 2,j]:= A[ 4,j] A[ 4,j]:= c кц 1 2 3 4 5 6 1 2 3 4 5 6
111 « A »: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы. Пример : Матрица А: 12 14 67 45 32 87 45 63 69 45 14 30 40 12 35 65 Результат: 12 0 0 0 32 87 0 0 69 45 14 0 40 12 35 65
112 « B »: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз: 1 2 3 4 5 6 7 8 9 7 8 9 4 5 6 1 2 3 «С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов: 1 2 3 4 5 6 7 8 9 7 4 1 8 5 2 9 6 3
§ 68. Работа с файлами 113
114 файлы текстовые двоичные « plain text » : текст, разбитый на строки; из специальных символов только символы перехода на новую строку любые символы рисунки, звуки, видео, …
115 открыть файл работа с файлом закрыть файл хлеб хлеб начинка файл Fin, Fout Fin := открыть на чтение ( ' input. txt ' ) Fout := открыть на запись ( ' output. txt ' ) | здесь работаем с файлами закрыть (F out ) закрыть (Fi n ) файловые переменные
116 цел a, b файл Fin Fin := открыть на чтение ( ' input. txt ' ) закрыть ( Fi n ) начать чтение ( Fin) ввод Fin, a, b Переход к началу открытого файла : если конец файла ( Fin ) вывод 'Данные кончились' все Определение конца файла :
117 цел a = 1, b = 2 файл Fout Fout := открыть на запись ( ' output. txt ' ) закрыть (F out ) вывод Fout, a, '+', b, '=', a+b
118 нц пока | не конец файла | прочитать число из файла | добавить его к сумме кц Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму. цел x, S файл Fin Fin := открыть на чтение ( ' input. txt ' ) S:= 0 нц пока не конец файла ( Fin ) ввод Fin, x S:= S + x кц закрыть ( Fi n )
119 « A »: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл. « B »: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть. « C »: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.
120 Задача. В файле записано не более 100 целых чисел. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания. В чем отличие от предыдущей задачи? ? цел MAX = 100 целтаб A[ 1 :MAX] Для сортировки нужно удерживать все элементы в памяти одновременно. !
121 Ввод массива : файл Fin Fin := открыть на чтение ( ' input. txt ' ) цел N N:= 0 | счётчик прочитанных данных нц пока не конец файла (Fin) и N:= N + 1 ввод Fin, A[N] кц закрыть (Fi n ) N < MAX Зачем? ?
122 Вывод результата : файл Fout Fout := открыть на запись ( ' output. txt ' ) нц для i от 1 до вывод Fout, A[i], нс кц закрыть (F out ) N
123 « A »: В файле записано не более 100 чисел. Отсортировать их по возрастанию последней цифры и записать в другой файл. « B »: В файле записано не более 100 чисел. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа. « C »: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.
124 Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода: Мухтар 4 немецкая овчарка Вывести в другой файл сведения о собаках, которым меньше 5 лет. нц пока не конец файла ( Fin ) | прочитать строку из файла Fin | разобрать строку – выделить возраст если возраст < 5 то | записать строку в файл Fout все кц
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 p p
126 лит s, s0 нц пока не конец файла ( Fi n) ввод Fin, s0 s:= s0 ... | обработка строки s если age < 5 то вывод Fo ut, s 0, нс все кц Зачем s0 ? ?
127 « A »: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: <Фамилия> <Имя> <Количество баллов> Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов. « B »: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией: П. Иванов И. Петров ...
128 « C »: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами: <Фамилия> <Имя> <Количество баллов> Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных: П. Иванов 98 И. Петров 96 ...
129 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
130 www.mcdonalds.com иллюстрации художников издательства «Бином» авторские материалы
