ЛКШ

случайно наткнулся (просили помочь со вступительными заданиями).
я просто в шоке, что сейчас знают и умеют решать(задания внизу страницы) продвинутые школьники)

вот такое, например:

Задание B-T2
Найдите ошибку в решении задачи и приведите верное решение.
Требуется подсчитать, сколько существует правильных скобочных последовательностей из N пар
круглых скобок.
Обозначим искомое количество через CN . Ясно, что C1 = 1.
Рассмотрим выражение из N пар скобок. Если первой слева открывающейся скобке соответствует
k-я слева закрывающаяся, и k < N , то выражение имеет вид: AB, где A — правильная скобочная
последовательность из k пар скобок, а B — правильная скобочная последовательность из N − k пар
скобок. Таких скобочных последовательностей — Ck CN −k , при этом k может принимать значение от 1
до N − 1.
Если же первой открывающейся скобке соответствует N -я закрывающаяся, то выражение имеет
вид (. . .), где вместо многоточия расположена правильная скобочная последовательность из N − 1
пары скобок. Количество таких последовательностей равно CN −1 .
Отсюда получаем формулу:
CN = (C1 CN −1 + C2 CN −2 + . . . + CN −1 C1 ) + CN −1


Я бы сходу такое, точно, не придумал.. +совершенно не понимаю, где здесь может быть ошибка((

lisp - это магия

текст заметки

я сначала ее написал, а потом уже подумал, что стоит отдельный блог под кодинг выделить.. вотЪ

sicp ex 2.13

немного по короче, чем везде, где я видел:
если интервалы заданы как

(make-center-percent c1 (* p1 100))
(make-center-percent c2 (* p2 100))

, то произведение

[c1(1-p1);c1(1+p1)]*[c2(1-p2);c2(1+p2)] =
 [c1*c2*(1-(p1+p2)+p1*p2);c1*c2*(1+(p1+p2)+p1*p2)] ~=
 [c1*c2*(1-(p1+p2));c1*c2*(1+(p1+p2))]

Т.о. p* ~= p1+p2, а c* = c1*c2.
Где результат равен

(make-center-percent c* (* p* 100))

sicp ex 1.19

sicp - Structure and Organisation of Computer Programms
буду писать здесь всякие замечания по поводу заданий из этой книги

(define (fib3 n)
(define (iter a b p q count)
(cond ((= count 0) b)
((even? count)
(iter a
  b
  (+ (square p) (square q))
  (* q (+ (* 2 p) q))
  (/ count 2)))
(else (iter (+ (* b q) (* a q) (* a p))
       (+ (* b p) (* a q))
       p
       q
       (- count 1)))))
(iter 1 0 0 1 n))

интересно, что время вычисления этим способом по сравнению с итеративным, хоть и меньше раз в 15, но растет с той же скоростью. Т.е. на самом деле логарифмическое время получить не удалось(оно скорее квадратичное)
мои результаты:

n  , итеративный процесс , "логарифмический", отношение
1e5, 1.559               , .080              , 19.5
1e6, 129.96              , 8.39              , 16.1
2e6, 508.92              , 35.23             , 14.5

для подсчетов использовал (runtime)

P.S. это на MIT Scheme