|
|||||||||||||||||||||
Методика преподавания основ алгоритмизации на базе системы "КуМир". Лекция 7Методы алгоритмизации. Рекуррентные соотношения. Метод итерации. Инвариант цикла. РекурсияИ в математике, и в информатике часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие.
Вот, например, в банке “Новый” можно открывать зарплатные счета трех типов: · “Базовый” — проценты не выплачиваются, но и плата за содержание счета не взимается; · “Накопительный” — каждый месяц начисляется 1% от вклада предыдущего месяца, затем из полученной суммы удерживается 300 рублей; · “Сберегательный” — после каждых 12 месяцев хранения вклада банк добавляет к вкладу 12% от минимума остатка на счете за 12-месячный период. При открытии каждого счета нужно положить на него сумму 10 тыс. рублей. Клиент банка “Новый” хочет за три года накопить возможно большую сумму, переводя на счет каждый месяц по 8 тыс. рублей. Каким вкладом ему выгоднее всего воспользоваться? С вкладом “Базовый” все просто. Результат трехлетнего накопления можно посчитать вручную. Если обозначить через Si сумму, которая окажется на счету после i месяцев, то Si = 10 тыс. + i*8 тыс., и через 36 месяцев на счетe окажется 10 + 36*8 = 298 тыс. руб.
С вкладом “Сберегательный” также все просто. Если обозначить через S0 начальную сумму в 10 тыс. рублей, через S1, S2, S3 — суммy на счетe после начисления процентов за первый, второй и третий год соответственно, то окажется, что S1 = S0*1,12 + 96; S2 = S1*1,12 + 96; S3 = S2*1,12 + 96. Подобные формулы, выражающие следующий член числовой последовательности через предыдущие члены, называют рекуррентными. Считая по этим формулам вручную или на калькуляторе, получим, что S1 = 107 200 руб.; S2 = 216 064 руб.; S3 = 337 991 руб. 70 коп. То есть вклад “Сберегательный” оказывается заметно выгоднее, чем вклад “Базовый”, что неудивительно — ведь никакие проценты по вкладу “Базовый” не выплачиваются. Труднее всего разобраться со вкладом “Накопительный”. Если обозначить через S0 начальную сумму в 10 тыс. рублей, через Si — суммy на счетe после i месяцев (в тысячах рублей), то Si = Si –1*1,01 + 8 – 0,3, то есть S1 = S0*1,01 + 7,7, S2 = S1*1,01 + 7,7, S3 = S2*1,01 + 7,7, S4 = S3*1,01 + 7,7, ... S35 = S34*1,01 + 7,7, S36 = S35*1,01 + 7,7. Если бы проценты не начислялись, то формула записывалась бы как Si = Si–1 + 7,7, последовательность {Si} оказалась бы арифметической прогрессией и S36 можно было бы вычислить по известной школьной формуле: S36 = 10 + 36*7,7 (вручную или с помощью калькулятора). Если бы проценты начислялись, но ежемесячных переводов 8 тыс. рублей и удержания 300 рублей не происходило, то формула записывалась бы как Si+1 = Si*1,01, последовательность {Si}
оказалась бы геометрической прогрессией и S36
тоже можно было бы вычислить по известной
школьной формуле: S36 = 10*1,0136 (с
помощью калькулятора, используя клавиши 10х
и Однако последовательность, заданная формулой Si = Si–1*1,01 + 7,7, не является ни арифметической, ни геометрической прогрессией, и формул, задающих общий вид члена такой последовательности, в школе не проходят. Но отсутствие или незнание такой формулы не мешает нам написать программу, которая последовательно вычислит все 36 неизвестных членов последовательности. Для этого зададим таблицу вещтаб s[0:36] и зададим значение начального элемента таблицы: s[0] := 10 Значение следующих 36 элементов таблицы вычисляют команды s[1] := s[0]*1.01 + 7.7 s[2] := s[1]*1.01 + 7.7 s[3] := s[2]*1.01 + 7.7 ... s[35] := s[34]*1.01 + 7.7 s[36] := s[35]*1.01 + 7.7 Эту не выписанную нами полностью последовательность из 36 команд можно записать с помощью конструкции цикл для, и мы получим алгоритм, который подсчитывает результат 36-месячного накопления:
В результате выполнения этого алгоритма выясняется, что вклад “Накопительный” оказывается для клиента самым выгодным, за 3 года он накопит сумму, чуть меньшую 366 тысяч рублей. А еще банк “Новый” ежегодно, в полдень 1 января, проводит среди владельцев зарплатных счетов лотерею, в которой разыгрывается всего один выигрыш — право немедленно открыть вклад Фибоначчи. Начальная сумма вклада Фибоначчи равна нулю, то есть при открытии вклада ничего платить не надо. По истечении первого месяца к вкладу добавляется одна копейка. По истечении второго и каждого последующего месяца вклад увеличивается на сумму, которая была на счету 32 дня назад. Через 36 месяцев вклад Фибоначчи закрывается и накопившаяся сумма переводится на зарплатный счет владельца. Кроме того, владелец вклада Фибоначчи может в любой момент закрыть вклад досрочно, получив за это премию 100 тысяч рублей1. Подсчитаем сумму Si , которая будет на счете Фибоначчи через i месяцев: S0 = 0, S1 = 1, S2 = S1 + S0 = 1, S3 = S2 + S1 = 2, S4 = S3 + S2 =3, S5 = S4 + S3 = 5, S6 = S5 + S4 = 8, ..., то есть последовательность {Si} — это известная последовательность Фибоначчи, в которой Si = Si–1 + Si–2. Равенство S6 = 8 означает, что через полгода на счете Фибоначчи будет аж 8 копеек! Похоже, что ждать окончания 36 месяцев бессмысленно — нужно закрывать вклад досрочно, зарабатывая на своем выигрыше 100 тыс. рублей. Попробуем проверить этот вывод, написав программу, которая будет вычислять (в копейках) сумму, накопленную за 36 месяцев. Как и в предыдущем случае, зададим таблицу вещтаб s[0:36] Зададим значения двух начальных элементов таблицы s[0] = 0; s[1] = 1 Значение следующих 35 элементов таблицы вычисляют команды s[2] := s[1] + s[0] s[3] := s[2] + s[1] ... Эту последовательность из 35 команд нужно заменить циклом, и мы получим алгоритм, который подсчитывает результат 36-месячного накопления:
Таким образом, мы поторопились с выводами: выгоднее не брать сразу премию, а подождать 36 месяцев, тогда выигрыш составит чуть больше 149 тыс. рублей. Но 100 тысяч мы могли бы получить сразу, в момент выигрыша (точнее, в первый рабочий день после 1 января), а вот 149 тыс. рублей мы получим на 3 года позже. Что предпочтительнее? Этот вопрос не относится к точным наукам. Разные люди по-разному оценивают одни и те же вещи. А в точных науках сравнивают вещи, выраженные в числах, и результат сравнения зависит от чисел, а не от предпочтений того, кто сравнивает. Чтобы перевести вопрос о сравнении “100 тысяч сегодня” со “149 тысячами 3 года спустя” в плоскость точных наук, переформулируем его так. Предположим, что у нас есть возможность открыть срочный вклад на 3 года, заключив договор, по которому банк обязуется добавлять к сумме вклада полтора процента каждый месяц. Сколько мы получим через 3 года, если сегодня положим на счет 100 тыс. рублей? Если эта сумма составит более 149 тысяч, то нет смысла ждать 36 месяцев, пока на счете Фибоначчи “подрастет” сумма 149 тысяч. Для решения этой задачи снова напишем программу:
Получается, что выгоднее сразу получить премию в 100 тыс. рублей и положить эту сумму на 3 года на срочный вклад под полтора процента в месяц. Однако, сделав такой вывод, мы забыли о том, что владелец вклада Фибоначчи может получить премию в 100 тыс. рублей, закрыв вклад после любого числа месяцев. Может быть, выгоднее подождать, пока вклад подрастет, а потом закрыть его, заработав и на росте вклада, и на премии? Немного изменим программу и посмотрим, что будет, если закрыть вклад Фибоначчи через 35 месяцев.
Изменив стратегию, удалось довести выигрыш до 192 тыс. рублей. Вывод. С появлением компьютеров стало возможным описывать окружающий нас мир, моделировать и предсказывать результаты практической деятельности и оптимизировать эти результаты не только с помощью “ручных” вычислений по математическим формулам, но и с помощью вычислений по компьютерным программам, которые можно провести только на ЭВМ. Один из методов, используемых при построении таких программ, — метод рекуррентных соотношений. Этот метод позволяет построить длинную последовательность чисел, зная только несколько первых членов последовательности. Замечание. Если нам нужен только последний член последовательности, заданной рекуррентным соотношением, то можно обойтись без таблиц и сэкономить память ЭВМ. Например, в задаче о сложном проценте можно вместо таблицы x[0:36] использовать простую величину X и считать так:
Важно отметить, что с программистской точки зрения в алгоритмах, вычисляющих конечный элемент, заданный рекуррентным соотношением, экономится память ЭВМ. Сравним еще раз два алгоритма “Сложный процент”. В первом случае запоминаются все элементы последовательности — каждый в отдельном элементе таблицы. Во втором алгоритме величина X меняется в процессе вычисления и на каждом шаге содержит i-й элемент последовательности. Этот переход от математических индексов в описании последовательности к обычным величинам в алгоритмах и их значениям в разные моменты времени Г.В. Лебедев назвал “исчезновением индексов”2. Дело в том, что когда пишется алгоритм для вычисления по рекуррентным соотношениям, не нужны не только таблицы, но и индексы. Например, в алгоритме сложный процент вычисление можно проводить так: X := 100 нц 36 раз . X := X*1.015 кц При выяснении того, какие величины и как будут меняться в цикле, удобно описать взаимосвязь между значениями величин в виде неизменного условия, которое должно быть выполнено после любого числа выполнений тела цикла. Такое неизменное условие, которое соблюдается после каждого выполнения тела цикла, в информатике называется инвариантом (лат. invariant — неизменный). По окончании цикла инвариант выполняется совершенно независимо от того, сколько раз выполнялось тело цикла и что происходило при каждом выполнении. Поэтому с помощью инварианта легче понять цель выполнения цикла или составить цикл для достижения требуемой цели. Рассмотрим пример программы, возводящей вещественное число a в целую положительную степень n простым умножением a само на себя n–1 раз:
Поскольку мы запустили алгоритм в отладочном режиме с выводом результатов на поля, пришлось чуть-чуть набраться терпения, дожидаясь завершения алгоритма (чуть более минуты). И это естественно, величина число получена в результате выполнения целых 999 операций умножения — 999 :)> ! К положительным свойствам алгоритма степень можно отнести его простоту, так как при его составлении мы действовали по определению. Нельзя ли ускорить работу алгоритма? Оказывается, можно, и притом весьма существенно. Ниже приведен алгоритм быстрого возведения в степень, для n = 1000 потребовалось всего 15 умножений! Этот алгоритм не так прозрачен: введена вспомогательная величина t, проверяется, четно ли k, величина t возводится в квадрат и т.п. Непонятно, какое это все имеет отношение к исходной задаче возведения числа а в степень n. Так почему же этот алгоритм работает правильно, и как это понять самому и доказать правильность учителю или дотошным одноклассникам? Ключ к пониманию и доказательству дает инвариант цикла, то есть равенство b · tk = an, которое описывает взаимосвязь между
значениями величин b, t и k в процессе
выполнения алгоритма. Проверим сначала, что
инвариант соблюдается перед циклом. В этот
момент, согласно нашей программе, 1 · an = an. Посмотрим, будет ли инвариант соблюдаться после очередного выполнения тела цикла, если он соблюдался перед этим выполнением. Так как внутри цикла есть команда если, то возможны два случая: · k четно. В этом случае выполняются команды t := t*t; k := k/2 (нацело, но так как k — четное, то результат и так целое число). Но, поскольку (t2)k1/2 = tk, то tk не изменится и инвариант останется выполненным. · k нечетно. В этом случае выполняются команды b := b*t; k := k–1. Поскольку (bt)tk–1 = btk, то btk не изменится и инвариант также останется выполненным. Итак, что бы ни происходило при выполнении тела цикла, инвариант сохранится. В обоих случаях k уменьшается, следовательно, цикл рано или поздно завершится. После окончания цикла инвариант будет по-прежнему выполнен, а k будет равно 0. Поэтому bt0 = an, т.е. b будет равно аn, что и требовалось. Другой пример, как всегда, связан с Роботом. Пусть известно, что Робот находится у левого края, и горизонтальный ряд клеток, в котором находится Робот, свободен от препятствий. Над Роботом находится полоса препятствий (несколько прямоугольных препятствий одинаковой высоты), но, возможно, разной ширины. Препятствия могут прилегать, а могут и не прилегать к левой и правой стенам. В задаче требуется, чтобы Робот оказался у правой стены, подсчитав число препятствий в полосе. Решение задачи не кажется таким простым. Больше всего “мешают” препятствия, прилегающие к левой и правой границам, так как совершенно не понятно, как их учесть в алгоритме3. Ясно одно: для решения задачи придется использовать конструкцию цикл и не обойтись без какого-то “счетчика” для подсчета числа препятствий (цел счетчик). Раз так, в цикле будут меняться две вещи: положение Робота и значение счетчика, и инвариант должен описать желаемое отношение между ними. Выберем общую стратегию: идем направо и “по дороге” считаем число пройденных препятствий в величине (цел счетчик). Условием завершения цикла будет достижение правой стены (то есть — справа не свободно). В конце пути, когда Робот оказался у правой границы, в счетчике должно оказаться общее число препятствий в полосе, и потому надо не забыть учесть в счетчике препятствие, расположенное в клетке над Роботом, если оно есть. Таким образом, получается такой инвариант: содержимое счетчика равно числу препятствий в пройденной Роботом части полосы, учитывая клетку над конечным положением Робота. Составляя алгоритм, мы должны обеспечить выполнение инварианта до цикла, а также после каждого выполнения тела цикла, и схему решения задачи можно записать так:
В этом алгоритме еще не детализированы Фрагмент А и Фрагмент Б . В Фрагменте Б мы будем увеличивать счетчик, когда Робот попадает под первую левую клетку очередного препятствия. При таком подходе инвариант будет автоматически выполняться по окончании цикла. Но еще нужно обеспечить выполнение инварианта перед циклом. Это будем делать в Фрагменте Б. В начальном положении Робота над ним либо нет препятствия, либо есть. Поэтому в соответствии с выбранным нами инвариантом в счетчик нужно поместить либо 0, либо 1. Значит, Фрагмент А может выглядеть так: . счетчик := 0. если сверху стена . . то счетчик := 1. все Обеспечим соблюдение инварианта после очередного выполнения тела цикла. Согласно выбранной нами общей стратегии, внутри цикла надо переместить Робота на шаг вправо. При этом положение Робота изменится, а значение счетчика останется прежним, то есть инвариант может временно нарушиться. Число препятствий в пройденной части полосы изменится в случае, если после сделанного шага Робот окажется под первой (левой) клеткой нового препятствия (до шага сверху было свободно, а после шага — занято). Фрагмент Б распадается на две части: . . выбор . . . при сверху стена: |Фрагмент Б1 . . . при сверху свободно:|Фрагмент Б2 . . все Фрагмент Б1 состоит в перемещении Робота на шаг вправо с сохранением инварианта, при условии, что до шага сверху было занято.В таком случае число препятствий в пройденной части полосы после шага измениться не может. То есть надо просто выполнить команду вправо. А Фрагмент Б2 состоит в перемещении Робота на шаг вправо (с сохранением инварианта), при условии, что до шага сверху было свободно. Число препятствий может увеличиться на 1, если после шага Робот окажется под первой клеткой нового препятствия, то есть если сверху окажется занято: . . . . вправо . . . . если сверху стена .. ... то счетчик := счетчик+ 1. . . . все . . все Теперь можно взглянуть на алгоритм целиком и на результат его работы в конкретном примере:
Как мы видим, Робот по окончании алгоритма находится в конце коридора у правой стены, и число препятствий равно 5. При составлении алгоритма мы не анализировали особые случаи условий задачи, а сформулировали инвариант и написали алгоритм так, чтобы он соблюдался до цикла и после каждого очередного выполнения цикла. Таким образом, мы не только составили алгоритм, но и доказали его правильность. Здесь уместно сделать ряд замечаний. Наша цель сугубо практическая — писать несложные программы быстро и без ошибок. При применении изложенной выше методики на практике не следует впадать в крайности и формулировать инварианты для очевидных циклов. Если промежуточные утверждения, инварианты циклов и прочее помогают писать программу, то их следует применять. Напротив, если же они только загромождают текст программы и ничего не проясняют, то надо обходиться без них. Однако при малейших сомнениях в правильности программы следует взглянуть на нее с формальных позиций.
Метод проектирования цикла с помощью инварианта является частным случаем метода итераций (дословно — повторений). Метод итераций состоит в циклическом выполнении некоторых действий до тех пор, пока не достигнут нужный результат. В приведенном выше примере Робот шагал вправо (и кое-что вычислял), пока справа было свободно. У метода итераций в общем виде имеется ряд условий. Мы должны быть уверены, что нужный результат будет достигнут. Так, изображенный на рисунке следователь уверен, что в конце концов он выйдет на похитителя алмазов, допрашивая преступников одного за другим4.
Кроме того, для одной и той же задачи могут быть написаны совершенно разные алгоритмы, приводящие к решению. Например, пусть на поле Робота произвольным образом расположены стены. Клетку будем называть угловой, если сверху и справа от нее есть стены. Требуется написать программу, которая переводит Робота из произвольной клетки в угловую. Эту задачу можно решать по такой схеме: нц пока сверху свободно или справа свободно . | <Фрагмент> кц Цель Фрагмента 1 — переместить Робота в какое-то новое, вообще говоря, более удачное положение. Замечательно то, что совершенно независимо от того, каков Фрагмент 1, в случае завершения цикла задача будет решена, то есть будет выполнено отрицание условия продолжения цикла: не(сверху свободно или справо свободно). Это oтрицание может быть переписано как (сверху стена и справа стена). Так что задача свелась к поиску подходящего Фрагмента. Попробуем такой вид Фрагмента : . если сверху свободно то вверх все . если справа свободно то вправо все Докажите, что рано или поздно Робот дойдет до угловой клетки. Эту задачу оставим в качестве упражнения. Заметим, что существует по крайней мере еще один существенно отличающийся Фрагмент, решающий данную задачу. Алгоритмы решений будут существенно разными, в том смысле, что траектория движения Робота и его конечное положение при выполнении этих алгоритмов могут оказаться различными. Другим, не менее интересным, методом программирования является рекурсия.
В общем случае рекурсией называется ситуация, когда какой-то алгоритм прямо или через другие алгоритмы вызывает себя в качестве вспомогательного. Сам алгоритм при этом называется рекурсивным. Для примера рассмотрим рекуррентное соотношение, задающее последовательность Фибоначчи. Вычисление п-го элемента этой последовательности можно записать в виде следующего алгоритма: алг цел Ф(арг цел n) . дано n>0 . надо | знач = п-й член | последовательности Фибоначчи нач . выбор . . при n = 1: знач := 1. . при n = 2: знач := 1. . иначе . . . знач:=Ф(n-1)+Ф(n-2) . все кон В отличие от написанных ранее алгоритмов здесь в качестве вспомогательного вызывается сам алгоритм Ф (с другими аргументами). Таким образом, алгоритм Ф является рекурсивным. Как известно, на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызовах алгоритмов в памяти ЭВМ “накапливаются” приостановленные алгоритмы. При рекурсивных вызовах одного и того же алгоритма Ф ЭВМ работает точно так же, т.е. при каждом вызове Ф отводит ему в памяти новое место. По завершении алгоритма он стирается из памяти, и ЭВМ возвращается к предыдущему алгоритму Ф. Приведенный алгоритм написан прямо по рекуррентному соотношению и выглядит очень просто, но работает этот алгоритм неэкономно. Ф (7), например, вычисляется по этому алгоритму как Ф (6) + Ф (5). Ф (6), в свою очередь, вычисляется как Ф (5) + Ф (4). Таким образом, Ф (5) в процессе вычисления Ф (7) будет вычисляться два раза, Ф (4) — три, Ф (3) — пять и т.д. Так, при вычислении Ф (45) ЭВМ выполнит свыше миллиарда операций сложения! Для сравнения заметим, что при вычислении 45-го члена последовательности Фибоначчи с помощью цикла выполняется всего лишь 45 операций сложения.
Поэтому, хотя составить рекурсивный алгоритм обычно проще нерекурсивного, пользоваться рекурсией надо осторожно. Рекурсивные алгоритмы естественно возникают в тех случаях, когда исходную задачу удается свести к точно такой же задаче, но с другими аргументами или в другой обстановке. При этом в ряде случаев составление нерекурсивного алгоритма может оказаться крайне сложным, почти невозможным. Вот один такой пример. На поле Робота стен нет, число клеток, в которые Робот может попасть из исходного положения, двигаясь только по незакрашенным клеткам, конечно. Требуется закрасить все клетки, в которые Робот мог попасть из исходного положения по незакрашенным клеткам, при этом после закрашивания Робот должен вернуться в исходное положение.
Если исходная клетка не закрашена, то этот алгоритм четыре раза вызывает себя в качестве вспомогательного. Каждый вызов происходит в новой обстановке: исходная клетка уже закрашена, а Робот находится в новом положении.
Упражнение. Опишите порядок закраски клеток при выполнении алгоритма закрасить поле в трех ситуациях:
Кроме Робота, в стандартный набор исполнителей “КуМира” входит Чертежник. Рассмотрим следующую задачу:
изобразить с помощью Чертежника график функции
(параболу) Во-первых, нарисовать весь график нельзя — он бесконечен. Поэтому будем рисовать только часть графика, например, от х = 0 до х = 2. Во-вторых, Чертежник не умеет рисовать ничего, кроме отрезков, а график функции у = х2 — это кривая. Поэтому параболу придется заменить ломаной. Если вершины ломаной лежат на параболе и звенья ломаной очень короткие, то ломаная зрительно почти не отличается от параболы. В общем случае с помощью Чертежника
можно нарисовать параболу на некотором участке
(от а до b) в виде ломаной из некоторого
числа звеньев n. Рисовать ломаную будем слева
направо, начиная от точки Используем вещественную величину х для запоминания х-координаты очередной вершины ломаной. Разобьем отрезок от а до b на n равных частей длины d = (b – a)/n. При рисовании очередного звена ломаной величину х надо увеличивать на d.
С помощью Чертежника можно рисовать не только математически заданныекривые, но и сложные, так называемые фрактальные, или самоподобные, структуры, встречающиеся в природе. Нарисуем, используя рекурсивный алгоритм, “фрактальную” елочку.
Упражнение. Ответьте на вопрос: с какой “ветки” начинает движение перо Чертежника при выполнении алгоритма Елочка? 1 Известно, что первый счастливчик, выигравший право открыть вклад Фибоначчи, закрыл его 11 января того же года и суммарно получил 100 тысяч рублей (только премию). Второй счастливчик решил не брать сразу 100 тысяч рублей, а подождать, пока вклад подрастет. После чего забыл о существовании вклада и вспомнил о нем только после того, как на его зарплатный счет была переведена сумма, накопившаяся за 36 месяцев. А вот третий счастливчик написал на языке “КуМир” программу, которая подсказала ему оптимальное поведение при условии, что в течение трех лет банковская ставка будет составлять полтора процента в месяц.2 Кушниренко А.Г., Лебедев Г.В. 12 лекций о том, для чего нужен школьный курс информатики и как его преподавать. // Методическое пособие. М.: Лаборатория базовых знаний, 2000.3 Эта задача неоднократно давалась первокурсникам мехмата МГУ на семинарах в начальном курсе программирования, и обычно только несколько решений на группу оказывались верными и, как правило, громоздкими, с отдельным рассмотрением случаев прилегания/неприлегания препятствий к стенам.4 Метод итераций похож на игру в гольф, когда спортсмен пытается загнать в лунку мяч за минимальное число ударов.
Ан. Ге. Кушниренко ;
| |||||||||||||||||||||
|
|
