Задача 76229

Тема:    [ Неопределено ]

Сложность: 2+ Классы:

Условие

(Э. Дейкстра) Функция 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
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.33