Разъяснения по методике решения задач и программы приведены на школьном алгоритмическом языке. <...> Программа, реализующая такие рассуждения, на школьном алгоритмическом языке будет иметь следующий вид, где mod — функция, определяющая остаток1 : алг Определение_НОД нач цел a, b, мин, НОД | |Ввод чисел | вывод "Задайте первое число" | ввод a | вывод нс, "Задайте второе число" | ввод b 1 В других языках программирования для определения остатка используется не функция, а специальная операция (как правило, знак этой операции—mod). <...> 4 Раздел 1 | если a=b | |то || НОД=a | |иначе | | |Находим минимальное из заданных чисел | | если a>b |||то |||мин=b | | |иначе |||мин=a | | все | | |и проверяем, не является ли оно | | |и меньшие него числа | | |общим делителем заданных чисел | | НОД = мин | | |проверку прекращаем, как только | | |будет найдено число, являющееся НОД ||нц пока mod(a, НОД) <> 0 или mod(b, НОД) <> 0 |||НОД=НОД-1 ||кц | все | |Выводим результат | вывод нс, "Наибольший общий делитель этих чисел равен", NOD кон Эту программу можно немного сократить, если не сравнивать заданные числа между собой, а сразу проверять одно из этих чисел (например, первое) и меньшие, чем оно: алг Определение_НОД нач цел a, b, НОД | |Ввод чисел | . <...> Приведем программу, работающую по этому алгоритму: алг Определение_НОД нач цел a, b, НОД | |Ввод чисел | . |нц пока a<>b | | если a>b |||то ||| a=a-b | | |иначе ||| b=b-a | | все |кц |НОД=а | |Вывод результата | . кон 2 Комментарии—оформляемые специальным образом фрагменты текста программы, играющие исключительно информационную роль. <...> В приведенной ниже программе, учитывающей это обстоятельство, использованы следующие новые величины: макс — максимальное из двух заданных чисел, мин — минимальное из двух заданных чисел, остаток — остаток от деления макс на мин. алг Определение НОД нач цел a, b, макс, мин, остаток, НОД | |Ввод чисел | . | если a <...>
Программирование_типовые_задачи,_алгоритмы,_методы.pdf
Д. ЗЛАТОПОЛЬСКИЙ
ПРОГРАММИРОВАНИЕ:
ТИПОВЫЕ ЗАДАЧИ, АЛГОРИТМЫ, МЕТОДЫ
4-е издание, электронное
Лаборатория знаний
2020
Москва
Стр.2
УДК 004.42
ББК 32.973-018
З-67
Златопольский Д. М.
З-67
Программирование: типовые задачи, алгоритмы,
методы / Д. М. Златопольский.—4-е изд., электрон.—
М. : Лаборатория знаний, 2020.—226 с.—Систем.
требования: Adobe Reader XI ; экран 10".— Загл.
с титул. экрана.—Текст : электронный.
ISBN 978-5-00101-789-9
Эта книга для тех, кто хочет научиться программировать.
В ней представлена методика решения типовых
задач программирования, не привязанная к конкретному
языку. Разъяснения по методике решения задач и программы
приведены на школьном алгоритмическом языке.
Русский синтаксис делает программы понятными и легко
переносимыми на любой язык программирования.
Для школьников и студентов, начинающих изучать
программирование или знакомых с его основами, а также
для всех, кого заинтересует решение сложных задач, в том
числе встречающихся на олимпиадах по программированию.
Книга будет полезна преподавателям различных учебных
заведений и студентам педагогических вузов.
УДК 004.42
ББК 32.973-018
Деривативное издание на основе печатного аналога: Программирование:
типовые задачи, алгоритмы, методы /
Д. М. Златопольский.—М. : БИНОМ. Лаборатория знаний,
2007.—223 с. : ил.—ISBN 978-5-94774-461-3.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных техническими средствами защиты авторских прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации
ISBN 978-5-00101-789-9
○c Лаборатория знаний, 2015
Стр.3
Содержание
1. Какая программа лучше? .............................. 3
2. Обмен значениями между двумя переменными ............ 8
3. Об операторах цикла .................................. 9
3.1. Оператор цикла с параметром (со счетчиком)................ 9
3.2. Оператор цикла с предусловием ......................... 13
3.3. Оператор цикла с постусловием ......................... 17
4. Типовые задачи на обработку
последовательности чисел ............................ 24
4.1. Суммирование всех чисел последовательности .............. 24
4.2. Суммирование чисел последовательности,
удовлетворяющих некоторому условию ................... 25
4.3. Подсчет количества чисел последовательности,
удовлетворяющих некоторому условию ................... 25
4.4. Определение среднего арифметического чисел
последовательности, удовлетворяющих некоторому условию .... 26
4.5. Определение порядкового номера некоторого значения
в заданной последовательности ......................... 26
4.6. Определение максимального значения
в последовательности чисел ............................ 27
4.7. Определение порядкового номера максимального
значения в последовательности чисел .................... 28
4.8. Определение максимального значения чисел
последовательности, удовлетворяющих некоторому условию . . . 29
5. Рекуррентные соотношения............................ 32
6. Типовые задачи обработки одномерных
числовых массивов .................................. 38
6.1. Нахождение суммы всех элементов массива................ 38
6.2. Нахождение суммы элементов массива с заданными
свойствами (удовлетворяющих некоторому условию)......... 39
6.3. Нахождение количества элементов массива
с заданными свойствами .............................. 39
6.4. Нахождение среднего арифметического
элементов массива с заданными свойствами................ 39
Стр.221
Содержание
221
6.5. Изменение значений элементов массива с заданными
свойствами......................................... 40
6.6. Вывод на экран элементов массива с заданными свойствами . . . 40
6.7. Нахождение номеров (индексов) элементов массива
с заданными свойствами .............................. 41
6.8. Определение индекса элемента массива, равного заданному
числу............................................. 41
6.9. Определение индекса элемента, равного заданному числу,
для массива, отсортированного по возрастанию ............ 43
6.10. Определение максимального элемента в массиве ........... 45
6.11. Определение индекса максимального элемента в массиве..... 46
6.12. Определение максимального значения среди элементов
массива, удовлетворяющих некоторому условию ........... 47
6.13. Определение места заданного числа в упорядоченном
массиве........................................... 48
6.14. Обмен местами двух элементов массива с заданными
номерами ......................................... 50
6.15. Удаление из массива k-го элемента со сдвигом всех
расположенных справа от него элементов на одну
позицию влево ..................................... 50
6.16. Вставка в массив заданного числа на k-е место
со сдвигом k-го, (k + 1)-го, (k + 2)-го и т. д. элемента
на одну позицию вправо .............................. 51
6.17. Циклическое перемещение элементов массива влево ........ 51
6.18. Циклическое перемещение элементов массива вправо ....... 52
6.19. Проверка массива на упорядоченность по неубыванию
(определение, верно ли, что каждый его элемент, начиная
со второго, не меньше предыдущего) .................... 53
6.20. Проверка наличия в массиве одинаковых элементов ........ 53
7. Случайные числа в программах ........................ 58
8. Типовые задачи обработки двумерных
числовых массивов................................... 65
8.1. Нахождение суммы всех элементов массива................ 65
8.2. Нахождение суммы элементов массива с заданными
свойствами (удовлетворяющих некоторому условию)......... 66
8.3. Нахождение количества элементов массива с заданными
свойствами......................................... 66
8.4. Нахождение среднего арифметического элементов массива
с заданными свойствами .............................. 67
8.5. Изменение значений элементов массива с заданными
свойствами......................................... 68
Стр.222
222
Содержание
8.6. Вывод на экран элементов массива с заданными
свойствами ........................................ 68
8.7. Нахождение индексов элементов массива с заданными
свойствами ........................................ 69
8.8. Определение максимального элемента массива ............. 69
8.9. Определение индексов максимального элемента массива ..... 70
8.10. Определение максимального значения среди элементов
массива, удовлетворяющих некоторому условию ........... 70
8.11. Нахождение суммы элементов в некоторой строке массива . . . 72
8.12. Нахождение суммы элементов с заданными свойствами
в некоторой строке массива ........................... 72
8.13. Нахождение количества элементов с заданными
свойствами в некоторой строке массива .................. 72
8.14. Нахождение среднего арифметического значений элементов
с заданными свойствами в некоторой строке массива........ 73
8.15. Изменение значений элементов массива
с заданными свойствами в некоторой строке массива........ 73
8.16. Вывод на экран элементов с заданными свойствами
из некоторой строки массива .......................... 73
8.17. Нахождение индексов элементов массива
с заданными свойствами.............................. 74
8.18. Определение максимального элемента в некоторой строке
массива .......................................... 74
8.19. Определение индекса столбца максимального элемента
в некоторой строке массив ............................ 74
8.20. Нахождение суммы элементов в каждой строке массива ..... 75
8.21. Нахождение суммы элементов с заданными свойствами
в каждой строке массива ............................. 75
8.22. Нахождение количества элементов с заданными
свойствами в каждой строке массива .................... 76
8.23. Нахождение среднего арифметического значений элементов
с заданными свойствами в каждой строке массива .......... 76
8.24. Определение максимального элемента в каждой строке
массива .......................................... 76
8.25. Определение индекса столбца для максимального элемента
в каждой строке массива ............................. 77
8.26. Определение максимальной суммы значений в строках
массива .......................................... 77
8.27. Определение номера строки массива с максимальной
суммой значений ................................... 78
8.28. Обмен местами двух элементов массива с заданными
индексами ........................................ 78
8.29. Обмен местами двух строк массива...................... 79
Стр.223
Содержание
223
8.30. Удаление из массива k-й строки со сдвигом всех
расположенных ниже нее элементов на одну строку вверх .... 80
8.31. Вставка в массив заданного одномерного массива
на k-ю строку со сдвигом k-й, (k+1)-й, (k+2)-й и т. д.
строк на одну позицию вниз ........................... 80
8.32. Циклическое перемещение строк массива вверх............ 81
8.33. Циклическое перемещение строк массива вниз ............ 82
8.34. Выяснение, имеется ли в массиве элемент, равный
некоторому значению................................ 82
8.35. Проверка наличия в массиве одинаковых элементов ........ 83
9. Использование процедур и функций ................... 89
10. Рекурсия.......................................... 101
11. Методы сортировки числовых массивов ............... 113
11.1. Сортировка подсчетом............................... 115
11.2. Сортировка выбором................................ 122
11.3. Сортировка обменом ................................ 127
11.4. Сортировка вставками .............................. 132
11.5. Сортировка вставками с убывающим шагом .............. 140
11.6. Сортировка с разделением (быстрая сортировка Хоара) ..... 144
11.7. Сортировка слиянием ............................... 147
11.8. Пирамидальная сортировка .......................... 153
12. Динамическое программирование .................... 158
13. Формирование комбинаторных объектов .............. 185
13.1. Перестановки ..................................... 186
13.2. Сочетания........................................ 193
13.3. Размещения ...................................... 199
14. Обработка деревьев................................. 204
Литература........................................... 219
Стр.224