ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 76229
Условие(Э. Дейкстра)
Функция f с натуральными аргументами
и значениями определена так:
f(0) = 0,
f(1) = 1,
f(2n) = f(n),
f(2n + 1) = f(n) + f(n + 1).
Составить программу вычисления
f(n) по
заданному n, требующую порядка
log n операций.
Решениеk := n; a := 1; b := 0; {инвариант: 0 <= k, f (n) = a * f(k) + b * f (k+1)} while k <> 0 do begin | if k mod 2 = 0 then begin | | l := k div 2; | | {k=2l, f(k)=f(l), f(k+1) = f(2l+1) = f(l) + f(l+1), | | f (n) = a*f(k) + b*f(k+1) = (a+b)*f(l) + b*f(l+1)} | | a := a + b; k := l; | end else begin | | l := k div 2; | | {k = 2l + 1, f(k) = f(l) + f(l+1), | | f(k+1) = f(2l+2) = f(l+1), | | f(n) = a*f(k) + b*f(k+1) = a*f(l) + (a+b)*f(l+1)} | | b := a + b; k := l; | end; end; {k = 0, f(n) = a * f(0) + b * f(1) = b, что и требовалось} Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке