Программирование: типовые задачи, алгоритмы, методы

ТИПОВЫЕ ЗАДАЧИ, АЛГОРИТМЫ, МЕТОДЫ 

4-е издание, электронное

ПРОГРАММИРОВАНИЕ:

Москва
Лаборатория знаний
2020

Д. ЗЛАТОПОЛЬСКИЙ

УДК 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

2

Если вас, уважаемый читатель, спросят: «Какая программа лучше —
меньшая по объему, работающая быстрее, или та, исходный текст
которой более понятен?», то, подумав, вы, скорее всего, ответите:
«Более быстрая, понятная и занимающая меньше места». Конечно,
вы при этом будете правы. Но, к сожалению, такие программы встречаются крайне редко. Как правило, улучшение одного из показателей (размера, скорости работы и понятности листинга) приводит
к ухудшению другого.
Рассмотрим в качестве примера задачу определения наибольшего
общего делителя (НОД) двух натуральных чисел.
Сначала составим программу по принципу, который по-английски
называется «KISS». Правда, сразу скажу: с поцелуями он ничего общего не имеет. «KISS» — это всего лишь аббревиатура фразы: «Keep
it simple, stupid», что в переводе означает: «Делай это проще, дурачок» . Этот принцип призывает нас решать поставленные задачи
более простыми методами, прибегая к изощренным алгоритмам и
программным средствам только в крайнем случае.
Будем рассуждать так. Если два заданных числа a и b равны между собой, то их НОД равен одному из них; в противном случае НОД
равен либо минимальному из заданных чисел, либо некоему целому
числу, которое меньше этого минимального.
Программа, реализующая такие рассуждения, на школьном алгоритмическом языке будет иметь следующий вид, где mod — функция, определяющая остаток
1:

алг Определение_НОД
нач цел a, b, мин, НОД
| |Ввод чисел
| вывод "Задайте первое число"
| ввод a
| вывод нс, "Задайте второе число"
| ввод b

1. Какая программа лучше?

1
В других языках программирования для определения остатка используется не функция, а специальная операция (как правило, знак этой операции — mod).

| если a = b
| |то
| |
НОД = a
| |иначе
| | |Находим минимальное из заданных чисел
| | если a > b
| | |то
| | | мин = b
| | |иначе
| | | мин = a
| | все
| | |и проверяем, не является ли оно
| | |и меньшие него числа
| | |общим делителем заданных чисел
| | НОД = мин
| | |проверку прекращаем, как только
| | |будет найдено число, являющееся НОД
| | нц пока mod(a, НОД) <> 0 или mod(b, НОД) <> 0
| | | НОД = НОД - 1
| | кц
| все
| |Выводим результат
| вывод нс, "Наибольший общий делитель этих чисел равен", NOD
кон

Эту программу можно немного сократить, если не сравнивать заданные числа между собой, а сразу проверять одно из этих чисел (например, первое) и меньшие, чем оно:

алг Определение_НОД
нач цел a, b, НОД
| |Ввод чисел
| ...
| |Проверяем, не является ли число а
| |и меньшие него числа
| |общим делителем заданных чисел
| НОД = а
| нц пока mod(a, НОД) <> 0 или mod(b, НОД) <> 0
| | НОД = НОД - 1
| кц
| |Выводим результат
| ...
кон

4
Раздел 1

Выигрыш в размере программы существенный! «Понятность» ее
хуже, пожалуй, не стала — благодаря записи комментария
2 относительно проверки числа а и меньших него чисел. Но если число а будет больше числа b, то количество проверяемых чисел по сравнению
с первым вариантом возрастет, причем чем больше отношение а/b,
тем значительней растет количество проверяемых чисел!
Какой из двух приведенных выше вариантов программы лучше,
определять вам, уважаемый читатель.
По сути дела, оба рассмотренных варианта работают по методу
перебора. Вместе с тем, существует алгоритм нахождения НОД двух
чисел, не использующий перебор. Он носит имя древнегреческого
математика Евклида, который изложил его в своей знаменитой работе «Начала» (330–320 гг. до н. э.). Суть этого, считающегося самым древним, алгоритма состоит в следующем. Если число а больше числа b, то нужно из а вычесть b; в противном случае, наоборот,
нужно из b вычесть а и повторять эти действия до тех пор, пока а не
станет равно b. После этого искомый НОД будет равен одному из полученных чисел. Приведем программу, работающую по этому алгоритму:

алг Определение_НОД
нач цел a, b, НОД
| |Ввод чисел
| ...
| нц пока a <> b
| | если a > b
| | |то
| | |
a = a - b
| | |иначе
| | |
b = b - a
| | все
| кц
| НОД = а
| |Вывод результата
| ...
кон

Какая программа лучше?
5

2
Комментарии — оформляемые специальным образом фрагменты текста программы,
играющие исключительно информационную роль. Транслятор (системная программа, переводящая прикладную программу, написанную на языке программирования высокого уровня — на Бейсике, Си, Паскале или др., в машинный код) в процессе работы игнорирует комментарии. Наличие комментариев считается «хорошим тоном» в программировании, так как позволяет сделать листинг понятнее и
снабдить его подробными объяснениями (в том числе о назначении переменных,
смысле выполняемых операций и т. д.).

Как улучшить эту программу? Прежде всего, можно многократные вычитания заменить на определение остатка от деления одного
целого числа на другое:

нц
| если a > b
| |то
| |
a = mod(a, b)
| |иначе
| |
b = mod(b, a)
| все
кц при a = 0 или b = 0
NOD = a + b

Обратим внимание на условие окончания оператора цикла и на
способ определения НОД. Очевидно дальнейшее усовершенствование:
можно отказаться от многократного сравнения величин а и b — достаточно сделать это один раз, а потом учесть, что получаемый в цикле остаток всегда будет меньше, чем второй параметр функции mod.
В приведенной ниже программе, учитывающей это обстоятельство, использованы следующие новые величины: макс — максимальное из двух заданных чисел, мин — минимальное из двух заданных чисел, остаток — остаток от деления макс на мин.

алг Определение НОД
нач цел a, b, макс, мин, остаток, НОД
| |Ввод чисел
|
...
| если a > b
| |то
| |
макс = a
| |
мин = b
| |иначе
| |
макс = b
| |
мин = a
| все
| остаток = mod(макс, мин)
| нц пока остаток <> 0
| | макс = мин
| | мин = остаток
| | остаток = mod(макс, мин)
| кц
| НОД = мин
| вывод нс, "Наибольший общий делитель этих чисел равен", НОД
кон

Насколько понятной получилась эта программа — решите сами.

6
Раздел 1

И наконец, самая короткая возможная программа нахождения
НОД:

алг Определение_НОД
нач цел a, b, остаток, НОД
| |Ввод чисел
| ...
| нц пока остаток <> 0
| | остаток = mod(a, b)
| | a = b
| | b = остаток
| кц
| НОД = a
| вывод нс, "Наибольший общий делитель этих чисел равен", НОД
кон

В особенностях ее работы разберитесь самостоятельно.

Итак, мы убедились, что часто одна и та же задача может быть
решена различными способами, каждый из которых имеет свои преимущества и недостатки. Какой же путь разработки программ выбрать? По мнению автора, начинающему программисту лучше руководствоваться принципом «KIS» (четвертая буква здесь пропущена
сознательно ), а после приобретения достаточного опыта программирования надо всегда стремиться к усовершенствованию программы с точки зрения ее размера, быстродействия и т. д. Ведь, как писал выдающийся математик XIX века К. Гаусс, «достоинство науки
требует, чтобы прилежно совершенствовались средства, ведущие
к достижению цели...».

Какая программа лучше?
7

Рассмотрим такую задачу: Даны значения двух переменных a и b.
Требуется произвести взаимный обмен их значений.
«Очевидное» решение этой задачи, что называется, «в лоб»:
a := b
или
b := a
b := a
a := b
требуемого результата не даст (кстати — подумайте сами почему?).
Как же быть? Надо действовать так, как производят обмен содержимого двух чашек, в одной из которых находится молоко, а в другой —
чай. Нужна третья чашка!
3 То есть в нашей задаче для ее решения
потребуется третья (вспомогательная) переменная. С ее помощью обмен значениями может быть проведен следующим образом:
с := a |Запоминаем значение а
a := b |Переменной а присваиваем значение b
b := c |Переменной b присваиваем "старое" значение а

или
c := b
b := a
a := c
Но оказывается, что обменять значения двух переменных можно и без использования вспомогательной переменной. «Не может
быть!» — скажете вы. Еще как может, — и сделать это можно даже
несколькими способами. Вот один из них:

а := а + b
b := a - b
a := а – b

Красиво, не правда ли? С молоком так не сделаешь! Другие
подобные способы решения (а их, по крайней мере, еще 7) найдите
самостоятельно. А заодно решите следующую задачу: Даны значения
трех переменных a, b и с. Требуется составить программу, после
выполнения которой переменная b будет иметь значение переменной а, переменная с — значение переменной b, а переменная а —
значение переменной с. Дополнительные величины не применять.
Интересно, сколько способов ее решения вы найдете?

2. Обмен значениями
между двумя переменными

3
Можно, конечно, использовать и две дополнительные чашки, но это уже перебор!

Как вы, очевидно, знаете, операторами цикла называют операторы,
обеспечивающие повторение одних и тех же действий (поэтому их
иногда также называют операторами повторения). В большинстве современных языков программирования существует несколько разновидностей операторов цикла. Опишем некоторые их особенности.

3.1. Оператор цикла с параметром
(со счетчиком)

Применяется в тех случаях, когда в программе какие-либо действия
(операторы) повторяются заранее известное количество раз и при
этом некоторая величина меняется с постоянным шагом.
Пример. Для вывода «столбиком» всех целых чисел от 10 до 20
без использования оператора цикла потребовалось бы записать:
вывод нс, 10
вывод нс, 11
...
вывод нс, 20

Хорошо видно, что здесь есть повторяющиеся действия (вывод
числа на экран) и что при этом выводимое число меняется с шагом,
равным 1. А значит, можно применить оператор цикла с параметром.
Общий вид этого оператора
4:

нц для <параметр цикла> от <начальное значение>
до <конечное значение>
|
<тело оператора цикла>
кц

где <параметр цикла> — имя переменной, являющейся параметром цикла (меняющейся при повторении действий), <начальное
значение> — начальное значение этой переменной, <конечное
значение> — конечное значение этой переменной (предполагается,
что <конечное значение> больше, чем <начальное значение>, и

3. Об операторах цикла

4
С правилами оформления этого и других операторов цикла в конкретном языке программирования, который вы изучаете, ознакомьтесь самостоятельно.

что изменение от <начального значения> до <конечного значения>
происходит с шагом, равным 1), а <тело оператора цикла> — операторы, повторяющиеся при работе оператора цикла.
В рассмотренном примере оператор оформляется следующим образом:

нц для i от 10 до 20 |i — имя величины-параметра цикла
| вывод нс, i
кц

Схема, иллюстрирующая работу оператора цикла с параметром,
показана на рис. 3.1.

На этой схеме буквой а обозначено имя переменной — параметра
цикла, [н.з.] и [к.з.] — соответственно начальное и конечное значения параметра.
Возникает вопрос: какое значение имеет параметр цикла после
окончания работы оператора? Ответы здесь различны для разных
систем программирования: в программе на Бейсике оно равно (а + 1),
в программе на Паскале — а, а в программе на школьном алгоритмическом языке оно вообще считается неопределенным (не кажется
ли вам, уважаемый читатель, что в этом есть своя логика — ведь
параметр цикла нужен только для работы оператора цикла, когда
выполняются действия при различных его значениях?).

10
Раздел 3

Рис. 3.1