Функция. Способы задания функций.
Функция является заданной, иначе говоря, известной, если для каждого значения возможного числа аргументов можно узнать соответствующее значение функции. Наиболее распространенные три способа задания функции: табличный, графический, аналитический, существуют еще словесный и рекурсивный способы.
1. Табличный способ наиболее широко распространен (таблицы логарифмов, квадратных корней), основное его достоинство – возможность получения числового значения функции, недостатки заключаются в том, что таблица может быть трудно читаема и иногда не содержит промежуточных значений аргумента.
Аргумент х принимает заданные в таблице значения, а у определяется соответственно этому аргументу х.
2. Графический способ заключается в проведении линии (графика), у которой абсциссы изображают значения аргумента, а ординаты – соответствующие значения функции. Часто для наглядности масштабы на осях принимают разными.
Например: для нахождения по графику у, которому соответствует х = 2,5 необходимо провести перпендикуляр к оси х на отметке 2,5. Отметку можно довольно точно сделать с помощью линейки. Тогда найдем, что при х = 2,5 у равно 7,5, однако если нам необходимо найти значение у при х равном 2,76, то графический способ задания функции не будет достаточно точным, т.к. линейка не дает возможности для столь точного замера.
Достоинства этого способа задания функций заключаются в легкости и целостности восприятия, в непрерывности изменения аргумента; недостатком является уменьшение степени точности и сложность получения точных значений.
3. Аналитический способ состоит в задании функции одной или несколькими формулами. Основным достоинством этого способа является высокая точность определения функции от интересующего аргумента, а недостатком является затрата времени на проведение дополнительных математических операций.
Функцию можно задать с помощью математической формулы y=x 2 , тогда если х равно 2, то у равно 4, возводим х в квадрат.
4. Словесный способ состоит в задании функции обычным языком, т.е. словами. При этом необходимо дать входные, выходные значения и соответствие между ними.
Словесно можно задать функцию (задачу), принимающуюся в виде натурального аргумента х с соответствующим значением суммы цифр, из которых состоит значение у. Поясняем: если х равно 4, то у равно 4, а если х равно 358, то у равен сумме 3 + 5 + 8, т. е 16. Далее аналогично.
5. Рекурсивный способ состоит в задании функции через саму себя, при этом значения функции определяются через другие ее же значения. Такой способ задания функции используется в задании множеств и рядов.
При разложении числа Эйлера задается функцией:
Ее сокращение приведено ниже:
При прямом расчёте возникает бесконечная рекурсия, но можно доказать, что значение f(n) при возрастании n стремится к единице (поэтому, несмотря на бесконечность ряда, значение числа Эйлера конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо f(n) единицу.
Источник
Конспект урока «Рекуррентное задание числовых последовательностей» (9 класс)
Выбранный для просмотра документ Открытый урок Рекуррентное задание числовой последовательности.docx
ТЕМА: Рекуррентное задание числовых последовательностей
Цель урока : познакомить учащихся с рекуррентным способом задания числовой последовательности на примере чисел Фибоначчи и разобрать задачи на преобразование одного задания последовательности в другое.
Воспитательная : продолжить формировать алгоритмическую культуру мышления учащихся на основе дискретного понимания функции.
Развивающая : продолжить развитие навыков и умений работы с формулами задания функции.
Обучающая : научить отличать аналитический способ задания функции от рекуррентного, переводить одно задание функции в другое.
Учебник, компьютер (проектор).
Учащиеся получат представление рекуррентных соотношениях.
Узнают о способе перехода от аналитического задания к рекуррентному.
Научатся использовать рекуррентные формулы для вычисления значений последовательности.
Проверка домашнего задания.
Актуализация темы «Способы задания функции»
Изучение нового материала (работа с презентацией).
Определение рекуррентного соотношения.
Различия аналитического и рекуррентного способа задания.
Определение последовательности Фибоначчи
Онтологическая интерпретация чисел Фибоначчи.
Свойства последовательности Фибоначчи.
Решение заданий из учебника
Приветствие, проверка присутствующих. Объявление темы урока, объяснение хода урока.
2. Проверка домашнего задания: № 16.6, 15.41.
3. Актуализация темы «Способы задания функции»
( Презентация ) Вспомнить в процессе беседы с учащимися какие бывают способы задания функции: аналитический, словесный, табличный, кусочный. Обосновать на базе дискретной природы числовых последовательностей возможность установления связи текущего члена последовательности с предыдущим.
4. Изложение нового материала.
1. Определение рекуррентного соотношения
Опр. ( презентация ) Говорят, что последовательность задана рекуррентным соотношением, если указана формула, в одной части которой находится только n — ый член последовательности, а в другой — буквенное выражение, содержащее предыдущие члены последовательности, в котором аргумент не участвует в вычислениях значения функции.
2. Различия аналитического и рекуррентного способа задания .
Различие состоит в том, что при аналитическом способе вычисления n — го члена в буквенном выражении имеется аргумент, с помощью которого можно сразу получить результат, не зная при этом значений остальных членов последовательности. При рекуррентном способе вычисления n — го члена обязательно надо знать значения предыдущих членов, начиная с первого. При этом в формуле рекуррентного соотношения аргумент присутствует только как индекс нумерации и в вычислениях не используется. Образно говоря, функция натурального аргумента задана зависимостью от начального и получаемого значения той же функции как в «принципе домино».
3. Определение последовательности Фибоначчи
Опр. ( презентация ) Последовательностью Фибоначчи называется числовая последовательность, у которой заданы изначально первый и второй члены, а n — ый член вычисляется как сумма ( n —1)- го и ( n —2)- го членов.
4. Онтологическая интерпретация чисел Фибоначчи.
На Западе впервые эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что: изначально есть новорожденная пара кроликов (самец и самка), со второго месяца после своего рождения кролики начинают спариваться и каждый месяц производить новую пару кроликов, кролики никогда не умирают. Сколько пар кроликов будет через год? ( презентация )
В начале первого месяца есть только одна новорожденная пара (1).
В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1)
В конце второго месяца первая пара рождает новую пару и опять спаривается (2)
В конце третьего месяца первая пара рождает еще одну новую пару и спаривается, вторая пара только спаривается (3)
В конце четвертого месяца первая пара рождает еще одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5)
5. Свойства последовательности Фибоначчи .
Если числа Фибоначчи заданы следующим образом:
тогда справедливы следующие свойства ( презентация ):
5. Решение заданий из учебника
Решение учителем № 15.37, 15.31, 15.20 (а, б), 15.32, 15.21.
Решение учащимися № 15.37, 15.31, 15.20, 15.32, 15.21 (а, б).
Заключительный опрос по изученному материалу:
1) Приведите примеры рекуррентного соотношения
2) Приведите пример последовательности Фибоначчи
3) Запишите рекуррентно арифметическую прогрессию
Источник
Рекуррентный способ задания функции
а) Терминологическое введение
По сути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.
Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:
б) Примеры рекурсивного задания функций
| 1. | f(0)=0 f(n)= f(n-1)+1 |
| 2. | f(0)=1 f(n)= n*f(n-1) |
Последовательная подстановка дает – f(n)=1*2*3*…*n = n!
Для полноты сведений приведем формулу Стирлинга для приближенного вычисления факториала для больших n:
| 3. | f(0)=1 f(1)=1 f(n)= f(n-1)+ f(n-2), n>=2 |
Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически
| 4. | f(0)=1 f(n)= f(n-1)+ f(n-2)+…+1 = f(i)+1 |
Для получения функции в явном виде рассмотрим ее последовательные значения: f(0)=1, f(1)=2, f(2)=4, f(3)=8, что позволяет предположить, что f(n)= , точное доказательство выполняется по индукции.
| 5. | f(0)=1 f(n)= 2*f(n-1) |
Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – f(n)= , как и в примере 4, что проверяется элементарной подстановкой.
| 6. | f(0)=1 f(1)=2 f(n)= f(n-1)*f(n-2) |
В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:
Обозначив через Fn — n-ое число Фибоначчи, имеем: f(n)= .
Рекурсивная реализация алгоритмов
Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом. Эта возможность позволяет напрямую реализовывать вычисление рекурсивно определенных функций. Отметим, что в силу тезиса Черча–Тьюринга аппарат рекурсивных функций Черча равномощен машине Тьюринга, и, следовательно, любой рекурсивный алгоритм может быть реализован итерационно.
F(n);
If n=0 or n=1 (проверка возможности прямого вычисления)
Then
F
Рис 8.1 Дерево рекурсии при вычислении факториала – F(5)
Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений – фрагмент дерева рекурсий для чисел Фибоначчи представлен на рис 8.2:
Рис 8.2 Фрагмент дерева рекурсии при вычислении чисел Фибоначчи – F(5)
Анализ трудоемкости механизма вызова процедуры
Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров этот механизм реализован через программный стек. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в программный стек специальными командами процессора. Дополнительно сохраняются зна-чения необходимых регистров и адрес возврата в вызывающую процедуру. Схематично этот механизм иллюстрирован на рис 8.3:
Рис 8.2 Механизм вызова процедуры с использованием программного стека
Для подсчета трудоемкости вызова будем считать операции помещения слова в стек и выталкивания из стека элементарными операциями в формальной системе. Тогда при вызове процедуры или функции в стек помещается адрес возврата, состояние необходимых регистров процессора, адреса возвращаемых значений и передаваемые параметры. После этого выполняется переход по адресу на вызываемую процедуру, которая извлекает переданные фактические параметры, выполняет вычисления, помещает их по указанным в стеке адресам, и при завершении работы восстанавливает регистры, выталкивает из стека адрес возврата и осуществляет переход по этому адресу.
Обозначив через:
m — количество передаваемых фактических параметров,
k — количество возвращаемых процедурой значений,
r — количество сохраняемых в стеке регистров,
имеем:
fвызова = m+k+r+1+m+k+r+1 = 2*(m+k+r+1) элементарных операций на один вызов и возврат.
Анализ трудоемкости рекурсивных алгоритмов в части трудоемкости самого рекурсивного вызова можно выполнять разными способами в зависимости от того, как формируется итоговая сумма элементарных операций – рассмотрением в отдельности цепочки рекурсивных вызовов и возвратов, или совокупно по вершинам дерева рекурсивных вызовов.
Анализ трудоемкости алгоритма вычисления факториала
Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров – r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно – в итоге:
Отметим, что n – параметр алгоритма, а не количество слов на входе.
Источник
