Теоретические сведения

Ответы

1. {-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}. 4. и x кратно 4}. 5. -курорты Черноморского побережья. 6. Ø, { a } 7. Ø, { a },{ b },{ c },{ a,b },{ a,c },{ b,c },{ a,b,c } 9. Ø 10. а) истинно; б) ложно; в) ложно 11. а) 2; б) 4; в) 1. 13. д)Ø; е) {1,2,3, a,b } 14. а) истинно; б) истинно; в) ложно. 18. а) ;

б) ; в) ;

г)

Раздел 3. Алгоритмы и рекурсия

Алгоритм, подобно многим другим базовым понятиям современной математики, не имеет строгого определения. Алгоритмом можно назвать совокупность инструкций о том, как решить некоторую задачу. Само слово «алгоритм» происходит от algoritmi – имени (в латинском написании) арабского математика IX в. аль-Хорезми.

Множество руководств, прилагаемых ко всевозможным устройствам, являются примерами алгоритмов. Любая компьютерная программа также представляет собой алгоритм. Школьные методы умножения «столбиком» и деления «уголком» многозначных десятичных чисел, метод исключения неизвестных при решении системы линейных уравнений, правило дифференцирования сложной функции – примеры вычислительных алгоритмов.

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

- детерминированность (алгоритм должен всегда выдавать один и тот же результат на одних и тех же исходных данных);

- доступность (алгоритм должен содержать только те команды, которые входят в набор команд исполнителя);

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

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

Рассмотрим подробнее рекурсивные функции, которые в своем определении содержат себя. Непосредственное задание функции при помощи формулы, как правило, является предпочтительным. Однако, иногда функцию бывает удобно или даже необходимо задавать при помощи так называемого «рекурсивного метода».

Из принципа индукции следует:

если функция задана для некоторого данного начального значения (обычно 0 или 1), и когда функция задана для некоторого значения , она задана также для значения , то функция будет определена для всех целых чисел, больших .

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

Рассмотрим несколько примеров рекурсивных функций.

1. Функция , определенная на множестве неотрицательных целых чисел, допускает также и рекурсивное определение .

2. Факториал , ,

его рекурсивное определение , .

3. Числа Фибоначчи 1; 1; 2; 3; 5; 8; 13; 21; 34; 55 и т.д. - последовательность чисел, в которой каждый следующий элемент равен сумме двух предыдущих .

4. Рассмотрим рекурсивный алгоритм «Ханойские башни». Согласно старой легенде, в задаче о Ханойской башне фигурируют три стержня и набор дисков разного диаметра. Диски нанизаны на один из стержней в порядке убывания их диаметра, диск наибольшего диаметра находится в самом низу. Задача состоит в том, чтобы переместить все диски на другой стержень с сохранением порядка. При этом диски можно перемещать со стержня на стержень по одному за раз, и диск большего диаметра нельзя помещать над диском меньшего диаметра.

Легенда гласит, что на один из трех бриллиантовых стержней нанизано 64 золотых диска. Некий монах перемещает диски со скоростью одно движение за секунду. Когда монах выполнит эту миссию, наступит конец света. Как долго продлится этот процесс?

Функцию для вычисления количества движений (и, следовательно, количества секунд), необходимых для переноса дисков с одного стержня на другой можно задать рекуррентной формулой .

Попробуем задать эту функцию непосредственно. Вычислим несколько первых значений : , , , , и т.д.

Если к каждому элементу последовательности 1, 3, 7, 15, 31,… прибавить единицу, то получим 2, 4, 8, 16, 32,… Поэтому, можно предположить, что . Докажем это по индукции:

- очевидно, для утверждение справедливо,

- предположим, что оно справедливо для , т.е. ,

нужно показать, что утверждение справедливо для . Действительно .

Следовательно, предположение верно.

Итак, в данном примере был осуществлен переход от рекурсивного описания функции к непосредственному. Такая процедура называется исключением рекурсии.

Ниже приведены примеры исключения рекурсии и примеры перехода от аналитического задания функции к рекурсивному.

Дата добавления: 2014-12-27