Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Рекурсия. Итерационный и рекурсивный алгоритм вычисления факториала. Трассировка рекурсивной функции. Вычисление чисел Фибоначчи с использованием рекурсии. Опережающее объявление
Loading...
En provenance du cours de National Research University Higher School of Economics
Алгоритмизация вычислений (Algorithmic computation)
67 notes
National Research University Higher School of Economics
67 notes
À partir de la leçon
Решение задач с использованием процедур и функций
Восьмая неделя посвящена решению задач с использованием процедур и функций. Вы знакомитесь с понятием рекурсии. Также рассматривается пример разработки программы с использованием нисходящего проектирования.
Rencontrer les enseignants
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[ЗВУК]
[ЗВУК] Рекурсивная
функция — это функция, которая может вызывать сама себя,
используя другие данные, то есть в более простом случае.
В качестве примера рассмотрим два определения для факториала.
Первое определение — это факториал заданного натурального числа есть
произведение чисел от 1 до n.
Это определение можно использовать, если мы будем записывать
итерационную форму вычисления факториала, то есть использовать цикл со счетчиком.
Второе определение пригодно для рекурсии.
Здесь n!
вычисляется как 1 при n = 0 и (n − 1)!
* n при n, являющимся натуральным числом.
Это определение — более точное, поскольку оно точно определяет,
чему равен факториал 0 и факториал 1.
Мы с вами запишем две функции,
которые будут соответствовать первому и второму определению факториала.
Первая функция будет без рекурсии, то есть итерационная,
а вторая функция будет рекурсивная.
Итак, первая функция у нас вами будет итерационная.
Мы здесь используем глобальные переменные: n — это число,
факториал которого мы будем вычислять, и две переменные: f и r,
которые будут вещественного типа, для того чтобы хранить исходные данные и результат.
Итак, первая функция, которая соответствует итерационной формуле,
то есть без рекурсии, в соответствии с определением первым, выглядит так.
Передается величина n целого типа,
а результат имеет тип почему-то real.
Давайте разберемся, почему тип результата является вещественным.
Мы с вами знаем, что результат у нас является произведением
натуральных чисел, а эта величина будет расти довольно быстро.
Для того чтобы можно было вычислить факториал достаточно больших чисел,
мы берем для хранения результата более широкий тип с большим диапазоном,
в котором можно хранить факториалы больших чисел.
Итак, здесь у нас переменная, которая является результатом,
будет вещественного типа.
Теперь мы объявляем локальные переменные — это у нас i,
переменная цикла, и это у нас f, наш результат.
В начале f присваивается 1, то есть начальное значение факториала равно 1,
и затем мы считаем наше произведение, используя цикл от 1 до n и на каждом
шаге f умножаем на номер нашего сомножителя.
Результатом является f, и имени функции f1 мы присваиваем эту величину,
чтобы вернуть результат в главную программу.
Теперь рассмотрим нашу функцию, которая является рекурсивной.
Здесь у нас на входе точно так же значение n, на выходе – величина типа real,
и мы записываем наши действия в соответствии со вторым определением.
То есть мы говорим, что если n = 0, то результат наш будет равен 1,
а в противном случае мы вызываем нашу функцию с другим, меньшим,
аргументом, то есть f2 (n − 1), и полученную величину умножаем на n.
Теперь рассмотрим главную программу.
Мы с вами должны ввести исходные данные, проверяя их допустимость.
Мы с вами знаем,
что факториал у нас определен для расширенного натурального ряда.
То есть для 1 и больших ее натуральных чисел.
Мы с вами должны ввести значение числа, для которого мы будем считать факториал.
Но пользователь может ошибиться и вместо целого значения ввести вещественное.
Поэтому мы при вводе используем переменную r,
которая будет у нас способна воспринять и вещественное число тоже.
И мы будем повторять наш ввод до тех пор, пока r не будет во-первых,
положительным числом, во-вторых, целым, а в-третьих, у нас еще есть все-таки
граница, выше которой мы не можем взять наши исходные данные, потому что результат
у нас не поместится в диапазон вещественных чисел — это число 170.
И затем мы округляем r и результат помещаем в переменную n,
потому что аргумент нашей функции является целым числом,
ну и я вызову только функцию f2 и выведу полученный результат.
Теперь давайте рассмотрим подробнее, а как, собственно,
работает вот эта рекурсивная функция, которую мы с вами только что написали.
В процессе выполнения этой функции у нас есть 2 шага.
Сначала у нас в памяти компьютера разворачивается необходимое
количество копий этой функции с разными аргументами,
потому что для того чтобы вычислить, допустим, факториал 3, нам нужно
знать факториал 2; для факториала 2 нам нужен факториал 1 и так далее.
Процесс создания вот этих копий, которые мы сейчас с вами увидим,
называется прямым ходом рекурсии.
После того как прямой ход рекурсии завершен, начинается обратный ход,
когда у нас полученные значения подставляются в предыдущие вызовы функции.
Этот процесс называют обратным ходом, или по-английски backtracking.
Предположим, n = 3.
Мы с вами увидим, если посмотрим на нашу рекурсивную функцию,
что в данном случае будет происходить вычисление по ветке else.
То есть для того чтобы вычислить 3!, мы должны знать, чему равно 2!.
То есть f2 = f2(2) * 3.
При этом происходит следующий процесс.
В этой копии нашей функции процесс вычисления временно приостанавливается,
и возникает новая копия в памяти нашего компьютера, где аргумент равен 2.
И в этой копии мы также пойдем по ветке «иначе».
То есть мы с вами посчитаем наш результат, как f2(1) * 2.
Для того чтобы вычислить f2(1), компьютер порождает еще одну копию.
Там n = 1, и, для того чтобы посчитать результат,
мы вычисляем f2(0) и умножаем на 1.
Для f2(0) возникает последняя копия, в ней n = 0,
и здесь не будет рекурсивного вызова функции: 0!
= 1.
То есть результат в этой копии равен 1.
Далее эта единица подставляется как результат в предыдущий вызов
— мы теперь знаем, что f2(0) = 1, и произведение также будет равно 1.
Эту единицу снова подставляют в предыдущую копию.
f2(1) = 1, и 1 * 2 даст нам результат, равный 2.
В этой копии процесс вычислений завершен, 2 подставляется у нас в предыдущую копию,
умножается на 3, и результат у нас равен 6.
То есть когда работает рекурсивная функция, мы видим,
что нам требуется довольно много памяти для хранения всех рекурсивных вызовов.
То есть рекурсивные функции всегда требуют много памяти для своей работы.
И рассмотрим теперь следующую задачу.
Мы напишем программу для вычисления числа Фибоначчи с заданным номером.
Причем вычисления будут оформлены в форме рекурсивной функции,
а ввод номера числа и вывод результата будут у нас в главной программе.
Напоминаю формулу для чисел Фибоначчи.
Первое и второе число равны 1, а все остальные вычисляются как сумма двух
предыдущих, начиная с третьего номера, причем n должно быть натуральным.
Наша программа будет выглядеть так.
У нас есть глобальная переменная r вещественного типа и f – переменная типа
real, при помощи которой мы будем читать исходные данные.
Функция для вычисления чисел Фибоначчи, в данном случае она называется digit,
на входе имеет целое значение n, а на выходе опять
имеет величину типа real для того, чтобы мы могли обрабатывать бо́льшие числа.
Теперь мы с вами записываем тело функции, используя наше определение.
При n = 1 или 2, мы с вами имеем результат, равный 1.
Во всех остальных случаях наша функция вызывает себя рекурсивно дважды.
То есть мы вычисляем значение этой функции для величины (n − 1),
вычисляем такое же значение для (n − 2),
складываем наши величины и получаем окончательный результат.
В главной функции мы вводим значение n до тех пор,
пока оно не будет целым и положительным.
И кроме того, оно должно не превышать величину maxint.
На самом деле, если мы запустим нашу программу, то мы увидим,
что maxint — это довольно слабое ограничение, и диапазон значений,
которые мы можем вычислить, даже меньше.
Теперь мы вызываем нашу функцию и выводим результат.
Вызов функции у нас происходит прямо внутри оператора вывода.
Теперь рассмотрим такое понятие, как опережающее объявление.
Бывают такие случаи, когда у нас две подпрограммы вызывают друг друга.
Это явление носит название косвенной рекурсии.
Например, при косвенной рекурсии подпрограмма A может вызывать
подпрограмму B, а та в свою очередь вызывает подпрограмму A.
Получается некий замкнутый круг, ведь мы же с вами знаем,
что если какая-то функция вызывает другую, то та, которую вызывают,
должна быть выше в коде программы чем та, которая ее вызывает.
Но здесь они обе вызывают друг друга.
Что же делать?
Для этого у нас есть опережающее объявление.
Признаком этого объявления является слово forward.
Forward по-английски — это «вперед».
Сначала для процедуры B мы записываем заголовок и после этого записываем
ключевое слово forward.
Это слово показывает, что само тело этой процедуры будет ниже по тексту программы.
Далее мы можем записать процедуру A, из этой процедуры вызвать процедуру B.
Мы уже можем это сделать, потому что наша программа понимает,
как называется процедура B и какой у нее набор параметров.
А затем, после того как тело процедуры A завершится,
у нас уже идет собственно код процедуры B.
Снова заголовок, объявление локальных переменных,
если это нужно, и сама процедура.
Таким образом мы с вами можем организовать косвенную рекурсию.
Обращаю ваше внимание, что если у нас некоторая процедура или функция
уже объявлена, то для нее опережающее объявление уже невозможно.
Рассмотрим программу для вычисления факториала заданного числа,
в которой используются две функции.
Первая функция — без рекурсии, она называется f1,
а вторая функция называется f2 и является рекурсивной.
n является глобальной переменной,
это число, факториал которого мы хотим высчитать.
f и r являются переменными, при помощи которых мы с вами будем считать результат.
При этом r у нас с вами используется при вводе данных,
чтобы проверить, что число, которое мы вводим, является целым,
и f — это результат.
Результат имеет тип real,
так как мы с вами хотим считать факториал для довольно больших чисел.
А как мы с вами знаем, факториал — это функция, которая растет очень быстро.
Попробуем запустить нашу программу и вызвать функцию f2,
которая считает факториал при помощи рекурсивного определения.
Например, я задам n, равное 20.
И вот у нас получился факториал заданного числа.
Если я вместо функции
f2 попробую вызвать функцию f1,
которая считает факториал без рекурсии,
то есть не вызывая саму себя, и задам те же самые исходные данные.
Мы видим, что результат совпадает с предыдущим.
И также мы с вами видим,
что есть ограничение на допустимость исходных данных.
Попробуем запустить программу снова и посчитать факториал числа
170 без использования рекурсии.
Обратите внимание на время выполнения.
Теперь я попробую снова вызвать функцию, которая использует рекурсию,
и задам число 170 в качестве исходного значения.
Здесь можно заметить, что время выполнения программы несколько больше.
Хотя и не намного, но тем не менее, эта разница видна, она есть.
То есть функция, которая использует рекурсию,
всегда работает медленнее, чем та, которая обходится без рекурсии.
И та и другая функция считают результат правильно и при одинаковых
исходных данных дают одинаковый результат.
[МУЗЫКА]
[МУЗЫКА]
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
