Д. ЗЛАТОПОЛЬСКИЙ ПРОГРАММИРОВАНИЕ: ТИПОВЫЕ ЗАДАЧИ, АЛГОРИТМЫ, МЕТОДЫ 4-е издание, электронное Москва Лаборатория знаний ң018 Зң67 Зң67 Златопольский Д. М. Программирование: типовые задачи, алгоритмы, методы / Д. М. Златопольский. Ҹ 4ңе изд., электрон. Ҹ М. : Лаборатория знаний, 2020. Ҹ 226 с. Ҹ Систем. требования: Adobe Reader XI ; экран 10".Ҹ Загл. с титул. экрана. Ҹ Текст : электронный. ң5ң00101ң789ң9 Эта книга для тех, кто хочет научиться программиң ровать. В ней представлена методика решения типовых задач программирования, не привязанная к конкретному языку. Разъяснения по методике решения задач и проң граммы приведены на школьном алгоритмическом языке. Русский синтаксис делает программы понятными и легко переносимыми на любой язык программирования. Для школьников и студентов, начинающих изучать программирование или знакомых с его основами, а также для всех, кого заинтересует решение сложных задач, в том числе встречающихся на олимпиадах по программированию. Книга будет полезна преподавателям различных учебных заведений и студентам педагогических вузов. ң018 Деривативное издание на основе печатного аналога: Проң граммирование: типовые задачи, алгоритмы, методы / Д. М. Златопольский. Ҹ М. : БИНОМ. Лаборатория знаний, 2007. Ҹ 223 с. : ил. Ҹ ң5ң94774ң461ң3. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации ң5ң00101ң789ң9 c Лаборатория знаний, 2015 1. Какая программа лучше? Если вас, уважаемый читатель, спросят: «Какая программа лучше — меньшая по объему, работающая быстрее, или та, исходный текст которой более понятен?», то, подумав, вы, скорее всего, ответите: «Более быстрая, понятная и занимающая меньше места». Конечно, вы при этом будете правы. Но, к сожалению, такие программы встречаются крайне редко. Как правило, улучшение одного из показателей (размера, скорости работы и понятности листинга) приводит к ухудшению другого. Рассмотрим в качестве примера задачу определения наибольшего общего делителя (НОД) двух натуральных чисел. Сначала составим программу по принципу, который по-английски называется «KISS». Правда, сразу скажу: с поцелуями он ничего общего не имеет. «KISS» — это всего лишь аббревиатура фразы: «Keep it simple, stupid», что в переводе означает: «Делай это проще, дурачок» J. Этот принцип призывает нас решать поставленные задачи более простыми методами, прибегая к изощренным алгоритмам и программным средствам только в крайнем случае. Будем рассуждать так. Если два заданных числа a и b равны между собой, то их НОД равен одному из них; в противном случае НОД равен либо минимальному из заданных чисел, либо некоему целому числу, которое меньше этого минимального. Программа, реализующая такие рассуждения, на школьном алгоритмическом языке будет иметь следующий вид, где mod — функ1 ция, определяющая остаток : нач цел a, b, мин, НОД | вывод "Задайте первое число" | ввод a | вывод нс, "Задайте второе число" | ввод b В других языках программирования для определения остатка используется не функция, а специальная операция (как правило, знак этой операции — mod). Раздел 1 | если a = b | |то | | НОД = a | |иначе | | |Находим минимальное из заданных чисел | | если a > b | | |то | | | мин = b | | |иначе | | | мин = a | | все | | |и проверяем, не является ли оно | | |и меньшие него числа | | |общим делителем заданных чисел | | НОД = мин | | |проверку прекращаем, как только | | |будет найдено число, являющееся НОД | | нц пока mod(a, НОД) <> 0 или mod(b, НОД) <> 0 | | | НОД = НОД - 1 | | кц | все | |Выводим результат | вывод нс, "Наибольший общий делитель этих чисел равен", NOD Эту программу можно немного сократить, если не сравнивать заданные числа между собой, а сразу проверять одно из этих чисел (например, первое) и меньшие, чем оно: нач цел a, b, НОД | |Проверяем, не является ли число а | |и меньшие него числа | |общим делителем заданных чисел | НОД = а | нц пока mod(a, НОД) <> 0 или mod(b, НОД) <> 0 | | НОД = НОД - 1 | |Выводим результат Какая программа лучше? Выигрыш в размере программы существенный! «Понятность» ее хуже, пожалуй, не стала — благодаря записи комментария относительно проверки числа а и меньших него чисел. Но если число а будет больше числа b, то количество проверяемых чисел по сравнению с первым вариантом возрастет, причем чем больше отношение а/b, тем значительней растет количество проверяемых чисел! Какой из двух приведенных выше вариантов программы лучше, определять вам, уважаемый читатель. По сути дела, оба рассмотренных варианта работают по методу перебора. Вместе с тем, существует алгоритм нахождения НОД двух чисел, не использующий перебор. Он носит имя древнегреческого математика Евклида, который изложил его в своей знаменитой работе «Начала» (330–320 гг. до н. э.). Суть этого, считающегося самым древним, алгоритма состоит в следующем. Если число а больше числа b, то нужно из а вычесть b; в противном случае, наоборот, нужно из b вычесть а и повторять эти действия до тех пор, пока а не станет равно b. После этого искомый НОД будет равен одному из полученных чисел. Приведем программу, работающую по этому алгоритму: нач цел a, b, НОД | нц пока a <> b | | если a > b | | |то | | | a = a - b | | |иначе | | | b = b - a | | все | НОД = а | |Вывод результата Комментарии — оформляемые специальным образом фрагменты текста программы, играющие исключительно информационную роль. Транслятор (системная программа, переводящая прикладную программу, написанную на языке программирования высокого уровня — на Бейсике, Си, Паскале или др., в машинный код) в процессе работы игнорирует комментарии. Наличие комментариев считается «хорошим тоном» в программировании, так как позволяет сделать листинг понятнее и снабдить его подробными объяснениями (в том числе о назначении переменных, смысле выполняемых операций и т. д.). Раздел 1 Как улучшить эту программу? Прежде всего, можно многократные вычитания заменить на определение остатка от деления одного целого числа на другое: | если 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(макс, мин) | НОД = мин | вывод нс, "Наибольший общий делитель этих чисел равен", НОД Насколько понятной получилась эта программа — решите сами. Какая программа лучше? И наконец, самая короткая возможная программа нахождения НОД: нач цел a, b, остаток, НОД | нц пока остаток <> 0 | | остаток = mod(a, b) | | a = b | | b = остаток | НОД = a | вывод нс, "Наибольший общий делитель этих чисел равен", НОД В особенностях ее работы разберитесь самостоятельно. Итак, мы убедились, что часто одна и та же задача может быть решена различными способами, каждый из которых имеет свои преимущества и недостатки. Какой же путь разработки программ выбрать? По мнению автора, начинающему программисту лучше руководствоваться принципом «KIS» (четвертая буква здесь пропущена сознательно J), а после приобретения достаточного опыта программирования надо всегда стремиться к усовершенствованию программы с точки зрения ее размера, быстродействия и т. д. Ведь, как писал выдающийся математик XIX века К. Гаусс, «достоинство науки требует, чтобы прилежно совершенствовались средства, ведущие к достижению цели...». 2. Обмен значениями между двумя переменными Рассмотрим такую задачу: Даны значения двух переменных 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 Красиво, не правда ли? С молоком так не сделаешь! J Другие подобные способы решения (а их, по крайней мере, еще 7) найдите самостоятельно. А заодно решите следующую задачу: Даны значения трех переменных a, b и с. Требуется составить программу, после выполнения которой переменная b будет иметь значение переменной а, переменная с — значение переменной b, а переменная а — значение переменной с. Дополнительные величины не применять. Интересно, сколько способов ее решения вы найдете? Можно, конечно, использовать и две дополнительные чашки, но это уже перебор! 3. Об операторах цикла Как вы, очевидно, знаете, операторами цикла называют операторы, обеспечивающие повторение одних и тех же действий (поэтому их иногда также называют операторами повторения). В большинстве современных языков программирования существует несколько разновидностей операторов цикла. Опишем некоторые их особенности. 3.1. Оператор цикла с параметром (со счетчиком) Применяется в тех случаях, когда в программе какие-либо действия (операторы) повторяются заранее известное количество раз и при этом некоторая величина меняется с постоянным шагом. Пример. Для вывода «столбиком» всех целых чисел от 10 до 20 без использования оператора цикла потребовалось бы записать: вывод нс, 10 вывод нс, 11 вывод нс, 20 Хорошо видно, что здесь есть повторяющиеся действия (вывод числа на экран) и что при этом выводимое число меняется с шагом, равным 1. А значит, можно применить оператор цикла с параметром. Общий вид этого оператора : нц для <параметр цикла> от <начальное значение> до <конечное значение> | <тело оператора цикла> где <параметр цикла> — имя переменной, являющейся параметром цикла (меняющейся при повторении действий), <начальное значение> — начальное значение этой переменной, <конечное значение> — конечное значение этой переменной (предполагается, что <конечное значение> больше, чем <начальное значение>, и С правилами оформления этого и других операторов цикла в конкретном языке программирования, который вы изучаете, ознакомьтесь самостоятельно.