Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Примеры вычисления последовательностей
Определение 1. Пусть переменная х принимает последовательно значения х 1, х 2, х 3, …, х n, …. Такое нумерованное множество чисел называется последовательностью. Закон образования последова-тельности задается формулой n -го члена х n. Из данного определения видно, что для задания последовательности нужно знать закон образования n- го члена последовательности, т.е. функцию, которая ставит натуральному числу n в соответствие некоторое значение f(n): x n= f(n). Определение 2. Последовательность { x n} называется сходящейся к х*, если при n → ∞ | x* - x n|→ 0. Определение 3. Последовательность { x n} называется убывающей, если при n → ∞ | x n|→ 0. Определение 4. Последовательность { x n} называется возрастающей, если при n → ∞ | x n|→ ∞. При вычислении возрастающих последовательностей должно быть задано условие, ограничивающее вычисление элементов такой последовательности. Определение 5. Пусть дана некоторая последовательность элемент-ов а1, а2, а3, …, аn, …, причём ак +1 =F(а 1, а 2, … аn, ак), ак +2 =F(а 2, а 3 ,...аn, ак, ак +1 ). Если функцию F можно определить или она задана, то последовательность а 1, а 2, а 3, …, ак, ак +1, … называется рекуррентной последовательностью. Формула n -го члена рекуррентной последовательности (рекуррентная формула) аn=F(an-k, an-k +1, аn-к +2, …, аn -1 ), где число k называется глубиной рекурсии и определяет количество предшествующих элементов, необходимых для вычисления аn. Смысл глубины рекурсии в том, что она показывает, сколько переменных необходимо для вычисления элементов последовательности. Примеры задач с использованием рекуррентных последовательностей Вычислить заданный n -й элемент последовательности. Вычислить сумму или произведение n элементов последовательности. Найти количество элементов на данном отрезке последовательности, удовлетворяющих определенному условию. Найти номер первого элемента последовательности, удовлетворя-ющего определённому условию. Пример 1. Вычислить n -й элемент арифметической прогрессии а 1 = 1, а 2 = 3, а 3 = 5 и т.д. Ход выполнения работы 1. Написание алгоритма решения задачи будет состоять из двух шагов. Выведем рекуррентную формулу. Так как разность прогрессии равна 2, то рекуррентная формула будет следующей: . Читается формула так: при i= 1 ai= 1; при i≥ 2 ai=ai- 1 + 2, т.е. каждый последующий элемент равен сумме предыдущего и 2. Определим глубину рекурсии. Поскольку каждый следующий элемент вычисляется только через один предыдущий, то глубина рекурсии равна 1. Следовательно, для вычисления элементов последовательности нужны две переменные. Однако в этом случае можно обойтись одной переменной. Для определения значения последующего элемента последовательности будем использовать рекурсивную формулу
2. Написать программу, соответствующую алгоритму: 3. Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 2. Вывести на печать первые n (n≥ 3 ) чисел Фибоначчи. Распечатать все элементы и подсчитать, сколько среди них четных чисел. Числа Фибоначчи образуются по закону: а 1 = 1, а 2=1, …, аi=ai -1 +ai -2, …. Ход выполнения работы 1. Написание алгоритма решения задачи будет состоять из двух шагов. Рекуррентная формула задается в определении чисел Фибоначчи: . Глубина рекурсии равна 2, поэтому для вычисления чисел Фибоначчи нужны три переменные. 2. Написать программу, соответствующую алгоритму:
Примечание. В алгоритме использована рекурсивная формула
3. Создать проект и реализовать данную задачу в среде Visual C++ 6.0. Последовательности в примерах 1 и 2 являются возрастающими, поэтому вычисление элементов ограничивается заданием их количества. Пример 3. Для заданных действительного x и целого n вычислить сумму .
Ход выполнения работы 1. Написание алгоритма решения задачи будет состоять из двух шагов. Формула для вычисления суммы: . Здесь i обозначает номер текущего элемента последовательности, n – количество элементов последовательности, сумму которых нужно вычислить. Глубина рекурсии в данном случае не определяется, так как данная формула не является рекуррентной. 2. Написать программу, соответствующую алгоритму6
Примечание. В алгоритме использована рекурсивная формула
3. Создать проект и реализовать данную задачу в среде Visual C++ 6.0. Пример 4. Для заданного вещественного х и малой величины eps вычислить сумму ряда .
Ход выполнения работы 1. Написание алгоритма решения задачи будет состоять из двух шагов. Рекуррентная формула выводится из предположения, что слагаемые ряда являются членами бесконечно убывающей геометрической прогрессии. Пусть . Таким образом, рекуррентная формула выглядит следующим образом: , где . Формула для берется из формулы ряда . Для нахождения формулы подставим в формулу i -1 вместо i: . Для вычисления q необходимо знать, что есть факториал числа. Факториалом числа i называют произведение последовательных натуральных чисел от 1 до i включительно, т.е. i! = 1·2·3·…·(i-1)· i. Следовательно, (2 i -1)! = 1·2·3·…·(2 i -1), а (2 i +1)! = 1·2·3·…·(2 i -1)·2 i ·(2 i +1). Вычислим . Получим рекуррентную формулу .
При записи этой формулы наиболее частой ошибкой является следующая запись этой формулы: . Эта формула не будет являться рекуррентной, так как в ней нет зависимости последующего элемента последовательности от предыдущего, следовательно, нет возможности применить стандартный алгоритм вычисления элементов и суммы этих элементов (описание см. ниже). Глубина рекурсии равна 2, т.е. для вычисления элементов последовательности требуются две переменные. Как и в примере 1, обойдемся одной переменной. Примечание. При вычислении суммы ряда решающую роль играет величина eps. Она задаётся для того, чтобы ограничивать количество вычисляемых элементов последовательности, добавляемых в сумму. При вычислении каждого элемента последовательности его модуль сравнивается с eps. Если он больше eps, то вычисления продолжаются, в противном случае вычисление элементов последовательности и добавление их в искомую сумму прекращается. Такой процесс называется вычислением суммы ряда с точностью eps. В качестве значения переменной eps можно взять 0, 001 или 0, 00001 и т.п. 2. Написать программу, соответствующую алгоритму:
3. Создать проект и реализовать данную задачу в среде Visual C++ 6.0. Пример 5. Найти наименьший номер члена последовательности, для которого выполняется условие . Вывести на экран номер и все элементы , где . Последовательность задается формулой .
Ход выполнения работы 1. Написание алгоритма решения задачи будет состоять из двух шагов. Формула для вычисления элементов последовательности: , где i – номер текущего элемента последовательности. Глубина рекурсии в данном случае равна 1, т.е. для вычисления элементов последовательности нужны две переменные. 2. Написать программу, соответствующую алгоритму:
3. Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
|