Решение упражнения 1.15 из SICP

29 August, 2007 (19:46) | Решения упражнений

При вычислении sine процедура p вызывается с аргументом sine от угла деленного на три. Это повторяется до тех пор, пока угол не станет меньше 0.1 по модулю. То есть, если x – начальный угол, то количество вызовов процедуры p (обозначим его n) будет удовлетворять следующему двойному неравенству:

x / 3n ≤ 0.1 ≤ x / 3n-1.

При x = 12.15 нетрудно видеть, что

  • при n=4 получаем 12.15/34 = 12.15/81 > 0.1,
  • при n=5 получаем 12.15/35 = 12.15/243 < 0.1.

Таким образом при вычислении (sine 12.15) процедура p вызывается 5 раз.

Перейдем к оценкам порядка роста количества шагов и используемой памяти для процедуры sine как функции от угла α. На каждой итерации происходит рекурсивный вызов функции sine с аргументом, деленным на три. То есть через n итераций аргумент уменьшится в 3n раз, а стало быть, так как процесс останавливается тогда, когда аргумент становится меньше 0.1 по модулю, из выведенного ранее неравенства

α / 3n ≤ 0.1

получаем

n ≥ log3(10α).

Таким образом число шагов растет логарифмически с ростом угла (Θ(log α)).

Также логарифмически (Θ(log α)) растет и объем памяти, что легко объясняетася тем, что память растет пропорционально числу шагов.

Comments

Comment from Алексей
Date: January 17, 2009, 11:50 pm

Если n = 5, то процедура вызывается 6 раз т.к нужно еще учесть первый вызов.

Comment from serg
Date: March 26, 2009, 10:39 pm

Можно ли “встроить” в программу счётчик, который бы считал, сколько раз была вызвана процедура (sine x) при, скажем, x=10?

Comment from vovka
Date: October 26, 2010, 9:34 pm

я написал некоторый вариант с счетчиком http://v-serov.livejournal.com/10756.html

Comment from kermzyxer
Date: February 7, 2011, 11:50 pm

> Можно ли “встроить” в программу счётчик, который бы считал, сколько раз была вызвана процедура (sine x) при, скажем, x=10?
Для этого есть трассирвка.
Выглядит это как-то так:

> (require racket/trace)
> (trace sine)
> (sine 12.15)
>(sine 12.15)
> (sine 4.05)
> >(sine 1.3499999999999999)
> > (sine 0.44999999999999996)
> > >(sine 0.15)
> > > (sine 0.049999999999999996)
< < < 0.049999999999999996
< < <0.1495
< < 0.4351345505
< <0.9758465331678772
< -0.7895631144708228
<-0.39980345741334
-0.39980345741334

Write a comment