Конспект лекций по программированию для начинающих. Гладков В.П. - 109 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

111
y = n!!! =
147 ... n, если n при делении на 3 даёт остаток 1,
258 ... n, если n при делении на 3 даёт остаток 2,
369 ... n, если n делится на 3.
⋅
⋅⋅ ⋅
⋅⋅⋅ ⋅
⋅⋅⋅ ⋅
⎧
⎨
⎪
⎩
⎪
11. Обобщите упражнение 10 на случай нахождения m-факториала числа n. Для
этого в приведенном выше определении замените 3 на m и добавьте недостающие
строки.
10.7. Рекуррентные формулы
10.7.1. Основные понятия
Рекуррентной называется формула, связывающая значения p+1 соседних
членов u
k
, u
k-1
, ..., u
k-p
(k>=p+1) некоторой последовательности {u
n
} (n=1, 2, ...): u
k
=
F(k,u
k-1
,...,u
k-p
). Рекуррентная формула позволяет шаг за шагом определить любой
член последовательности, если известны p первых ее членов u
1
, u
2
,..., u
p
, где p
называют порядком формулы. Рассмотрим примеры.
Пример 10.24. u
1
=u
2
=u
3
=1, для k>3 каждый следующий член
последовательности определяется формулой u
k
=u
k-1
+2·u
k-2
+3·u
k-3
. Эту формулу
называют линейной однородной формулой третьего порядка.
Пример 10.25. u
1
=u
2
=1, для k>2 каждый следующий член последовательности
определяется формулой u
k
=u
k-1
+u
k-2
. Эту формулу называют линейной однородной
формулой второго порядка. Она порождает числа Фибоначчи, каждое из которых
равно сумме двух предыдущих.
Пример 10.26. u
1
=1, u
2
=2, для k>2 каждый следующий член
последовательности определяется формулой u
k
=u
k-2
. Эту формулу называют
линейной однородной формулой второго порядка. Обратите внимание на то, что
элемент u
k-1
здесь пропущен, но этот факт не снижает порядка формул.
Пример 10.27. u
1
=1, для k>1 каждый следующий член последовательности
определяется формулой u
k
=-u
k-1
. Эту формулу называют линейной однородной
формулой первого порядка. Сравните эту формулу с формулой из примера 10.26).
Пример 10.28. u
1
=0, u
2
=1, для k>2 каждый следующий член
последовательности определяется формулой
k
u
=
k-1
2
u
k-2
u
+ cos
. Эту
формулу называют нелинейной рекуррентной формулой второго порядка.
Пример 10.29. u
1
=0.5, для k>1 каждый следующий член последовательности
определяется формулой u
k
=u
k-1
+3. Эту формулу называют линейной неоднородной
формулой первого порядка.
Пример 10.30. u
1
=1, для k>1 каждый следующий член последовательности
определяется формулой u
k
=k·u
k-1
. Эту формулу называют линейной рекуррентной
формулой первого порядка с переменными коэффициентами.
Пример 10.31. Рассмотрим задачу нахождения n-го члена рекуррентной
последовательности на примере чисел Фибоначчи. Они определяются формулой
примера 10.25. Каждое число Фибоначчи равно сумме двух предыдущих. В
частности: u
3
=u
2
+u
1
=1+1=2;
u
4
=u
3
+u
2
=1+2=3; 
                                          111

               ⎧1 ⋅ 4 ⋅ 7 ⋅ ... ⋅ n, если n при делении на 3 даёт остаток 1,
               ⎪
    y = n!!! = ⎨2 ⋅ 5 ⋅ 8 ⋅ ... ⋅ n, если n при делении на 3 даёт остаток 2,
               ⎪3 ⋅ 6 ⋅ 9 ⋅ ... ⋅ n, если n делится на 3.
               ⎩
   11. Обобщите упражнение 10 на случай нахождения m-факториала числа n. Для
этого в приведенном выше определении замените 3 на m и добавьте недостающие
строки.

                          10.7. Рекуррентные формулы

                              10.7.1. Основные понятия
    Рекуррентной называется формула, связывающая значения p+1 соседних
членов uk, uk-1, ..., uk-p (k>=p+1) некоторой последовательности {un} (n=1, 2, ...): uk =
F(k,uk-1,...,uk-p). Рекуррентная формула позволяет шаг за шагом определить любой
член последовательности, если известны p первых ее членов u1, u2,..., up, где p
называют порядком формулы. Рассмотрим примеры.
    Пример 10.24. u1=u2=u3=1, для k>3 каждый следующий член
последовательности определяется формулой uk=uk-1+2·uk-2+3·uk-3. Эту формулу
называют линейной однородной формулой третьего порядка.
    Пример 10.25. u1=u2=1, для k>2 каждый следующий член последовательности
определяется формулой uk=uk-1+uk-2. Эту формулу называют линейной однородной
формулой второго порядка. Она порождает числа Фибоначчи, каждое из которых
равно сумме двух предыдущих.
    Пример 10.26. u1=1, u2=2, для k>2 каждый следующий член
последовательности определяется формулой uk=uk-2. Эту формулу называют
линейной однородной формулой второго порядка. Обратите внимание на то, что
элемент uk-1 здесь пропущен, но этот факт не снижает порядка формул.
    Пример 10.27. u1=1, для k>1 каждый следующий член последовательности
определяется формулой uk=-uk-1. Эту формулу называют линейной однородной
формулой первого порядка. Сравните эту формулу с формулой из примера 10.26).
    Пример 10.28. u1=0, u2=1, для k>2 каждый следующий член
последовательности определяется формулой u k = u 2k - 1 + cos u k - 2 . Эту
формулу называют нелинейной рекуррентной формулой второго порядка.
   Пример 10.29. u1=0.5, для k>1 каждый следующий член последовательности
определяется формулой uk=uk-1+3. Эту формулу называют линейной неоднородной
формулой первого порядка.
   Пример 10.30. u1=1, для k>1 каждый следующий член последовательности
определяется формулой uk=k·uk-1. Эту формулу называют линейной рекуррентной
формулой первого порядка с переменными коэффициентами.
   Пример 10.31. Рассмотрим задачу нахождения n-го члена рекуррентной
последовательности на примере чисел Фибоначчи. Они определяются формулой
примера 10.25. Каждое число Фибоначчи равно сумме двух предыдущих. В
частности: u3=u2+u1=1+1=2;
            u4=u3+u2=1+2=3;

Страницы