ВУЗ:
Составители:
Рубрика:
Close(F)
End;
Begin
Init;
Run
End.
Задача 2. "Функция"
Задача была предложена на Московской олимпиаде школьников
в 1981г. и на олимпиаде первокурсников факультета ПММ в 1998г .
Ниже приводится программа, разработанная Олегом
Викторовичем Гладышевым , который сейчас обучается на 4-м
курсе факультета ПММ ВГУ.
1. Условие задачи .
Функция F(n) для целых неотрицательных n определена так:
F(0)=0, F(1)=1, F(2n) = F(n), F(2n+1)=F(n)+F(n+1).
Для данного N найти и напечатать F(n). Обязательное условие: N
столь велико , что недопустимо заводить массив из N чисел.
2. Алгоритм решения.
Основная идея алгоритма заключается в том , что при
разложении f(2n+1) на f(n) и f(n+1) мы должны вычислить 2
значения функции. Либо n, либо n+1 окажется нечетным и для его
вычисления понадобится опять вычислять 2 значения функции. А
для четного аргумента еще одно. На первый взгляд , кажется, что
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
