Персональная страничка
Диканева Тараса
Викторовича

Главная \ Преподавательское \ Программирование для начинающих

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

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

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

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.

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

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

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

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

  1. Игорёк

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

  2. Taras

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

  3. Игорёк

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

  4. Игорёк

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

  5. Taras

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

    x_{n+1}=x_n+a

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

    x_{n+1}=a \cdot x_n

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

  6. odinochka

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

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

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