Персональная страничка
Диканева Тараса
Викторовича
Главная \ Преподавательское \ Программирование для начинающих
Введение
Выбор среды программирования
1. Линейные программы: арифметические операторы, стандартные функции и ввод/вывод в текстовом режиме
2. Логические выражения и условный оператор
3. Цикл с параметром (for)
4. Вычисления с помощью рекуррентных соотношений
5. Вложенные циклы
6. Задачи на перебор вариантов
7. Переменные-флаги
8. Переменная - счетчик событий
9. Циклы while и repeat
10. Массивы
11. Процедуры и функции
12. Двумерные массивы
13. Графика в Паскале
14. Символы, строки, текстовые файлы
15. Записи
16. Указатели

4. Вычисления с помощью рекуррентных соотношений

Предыдущий раздел:

Задание 3: Цикл for, приемы накопления суммы и произведения

Следующий раздел:

4.2. Задачи на составление рекуррентных соотношений

4.1. Рекуррентные соотношения: основные понятия

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

Будем говорить, что последовательность векторов \{\vec{x}_n\} задана рекуррентным соотношением, если задан начальный вектор \vec{x}_0=(x_0^1, \ldots, x_0^D) и функциональная зависимость последующего вектора от предыдущего

\vec{x}_{n+1}=\vec{f}(\vec{x}_n).~~~~~(1)

Вектора \vec{x}_n можно интерпретировать как наборы значений переменных. Таким образом, они характеризуют состояние вычислительного процесса. Функцию \vec{f} будем понимать как преобразование значений переменных на каждом шаге цикла.

Задача: Пусть задано рекуррентное соотношение x_{n+1}=2-x_n^2, начальное значение x_0=0. Найдите x_5.

Пример 1: Запишите рекуррентные соотношения для нахождения суммы целых чисел от 1 до m и факториала m!

Для суммы возьмем начальное значение x_0=0 и рекуррентное соотношение x_{n+1}=x_n+n. Требуемая сумма будет найдена на m-м шаге.

Аналогично для факториала: x_0=1, x_{n+1}=x_n\cdot n, требуемое значение также будет найдено на m-м шаге.

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

В приведенных примерах рекуррентные соотношения явно содержали номер шага n, чего, вообще говоря, нет в формуле (1). С практической точки зрения это не важно – в цикле for на каждом шаге можно использовать значение переменной-счетчика шагов. Однако, заботясь о математической строгости, нетрудно свести все к виду (1), сделав номер шага элементом вектора состояния вычислительного процесса. Так для вычисления факториала будем иметь:

\left\{ \begin{array}{l} x_{n+1}=x_n\cdot y_n,\\ y_{n+1}=y_n+1. \end{array} \right.

при начальных условиях x_0=1, y_0=1.

Однократное вычисление следующих значений по предыдущим посредством рекуррентных соотношений называется итерацией. А процесс вычислений с помощью рекуррентных соотношений соответственно итерированием.

Следующий раздел:

4.2. Задачи на составление рекуррентных соотношений

Предыдущий раздел:

Задание 3: Цикл for, приемы накопления суммы и произведения

Добавить комментарий

6 комментариев

  1. Игорёк 05.07.2012 в 23:13

    Что делать, если не понимаю. Что к чему здесь ? ( Сам я ещё учусь в школе, и что-то вот не понимаю, что к чему здесь.) Если пропустить тему, не потеряю многого ?

  2. Taras 06.07.2012 в 19:42

    Чего-то принципиально сложного в этой теме нет. Хотя бы идею желательно понимать. А как, совсем непонятно, о чем речь, или задачки не получаются?

  3. Игорёк 06.07.2012 в 22:38

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

  4. Игорёк 06.07.2012 в 22:38

    т.е составление алгоритма, который позволит тебе найти нужное число

  5. Taras 07.07.2012 в 12:00

    Прогрессия это как раз простой пример рекуррентного соотношения. Арифметическая

    x_{n+1}=x_n+a

    и геометрическая

    x_{n+1}=a \cdot x_n

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

  6. odinochka 21.12.2014 в 15:58

    Здравствуйте.

    А есть ли раздел с ответами решений к самостоятельным заданиям? А то даже и не знаешь правильно ли решил или нет.

Добавить комментарий