Структура и интерпретация компьютерных программ
В этом разделе приведены решения упражнений, взятых из книги "Structure and Interpretation of Computer Programs" авторов Abelson Harold, Sussman Gerald Jay, Sussman Julie. Для решения используется Scala.
Глава 1. Построение абстракций с помощью процедур
1.1 Элементы программирования
1.1.1 Выражения - 1.1.6 Условные выражения и предикаты
1.1.1 Выражения
Выражения рода (- 1000 334), образуемые путем заключения списка выражений в скобки
с целью обозначить применение функции к аргументам, называются комбинациями (combinations).
Самый левый элемент в списке называется оператором (operator), а остальные элементы — операндами (operands).
Значение комбинации вычисляется путем применения процедуры, задаваемой оператором, к аргументам (arguments), которые
являются значениями операндов.
Соглашение, по которому оператор ставится слева от операндов, известно как префиксная нотация (prefix notation).
Префиксная нотация естественным образом расширяется, позволяя комбинациям вкладываться (nest) друг в друга, то есть
допускает комбинации, элементы которых сами являются комбинациями: (+ (* 3 5) (- 10 6)).
Правила форматирования, при которых всякая длинная комбинация записывается так, чтобы ее операнды выравнивались вертикально, называются красивая печать (pretty printing). Получающиеся отступы ясно показывают структуру выражения.
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))Интерпретатор считывает выражение с терминала, вычисляет его и печатает результат. Этот способ работы иногда называют циклом чтение-вычисление-печать (read-eval-print loop).
1.1.2. Имена и окружение
Одна из важнейших характеристик языка программирования — какие в нем существуют средства использования имен для указания на вычислительные объекты. Мы говорим, что имя обозначает переменную (variable), чьим значением (value) является объект.
В Scala мы даем вещам имена с помощью слова val.
Предложение val size 2 заставляет интерпретатор связать значение 2 с именем size.
Ясно, что раз интерпретатор способен ассоциировать значения с символами и затем вспоминать их, то он должен иметь некоторого рода память, сохраняющую пары имя-объект. Эта память называется окружением (environment) (а точнее, глобальным окружением (global environment)).
1.1.3. Вычисление комбинаций
Чтобы вычислить комбинацию, требуется:
- Вычислить все подвыражения комбинации.
- Применить процедуру, которая является значением самого левого подвыражения (оператора) к аргументам — значениям остальных подвыражений (операндов).
Заметим, что на первом шаге для того, чтобы провести процесс вычисления для комбинации, нужно сначала проделать процесс вычисления для каждого элемента комбинации. Таким образом, правило вычисления рекурсивно (recursive) по своей природе; это означает, что в качестве одного из своих шагов оно включает применение того же самого правила.
Форма правила вычисления «распространить значения наверх» является примером общего типа процессов, известного как накопление по дереву (tree accumulation).
Заметим, что многократное применение первого шага приводит нас к такой точке, где нужно вычислять уже не комбинации, а элементарные выражения, а именно числовые константы, встроенные операторы или другие имена. С этими случаями мы справляемся, положив, что:
- значением числовых констант являются те числа, которые они называют;
- значением встроенных операторов являются последовательности машинных команд, которые выполняют соответствующие операции; и
- значением остальных имен являются те объекты, с которыми эти имена связаны в окружении.
Заметим, что рассмотренное нами правило вычисления не обрабатывает определений.
Например, вычисление val x 3 не означает применение val к двум аргументам, один из которых значение символа x,
а другой равен 3, поскольку смысл val как раз и состоит в том, чтобы связать x со значением.
(Таким образом, val x 3 — не комбинация.)
Такие исключения из вышеописанного правила вычисления называются особыми формами (special forms).
1.1.4. Составные процедуры
- Числа и арифметические операции представляют собой элементарные данные и процедуры.
- Вложение комбинаций дает возможность комбинировать операции.
- Определения, которые связывают имена со значениями, дают ограниченные возможности абстракции.
Определение процедур (procedure definitions) — метод абстракции, с помощью которого составной операции можно дать имя и затем ссылаться на нее как на единое целое.
Например, определение "возведения в квадрат": def square(x: Int): Int = x * x
Здесь мы имеем составную процедуру (compound procedure), которой дали имя square.
Эта процедура представляет операцию умножения чего-либо само на себя.
Общая форма определения процедуры такова: (define (<имя> <формальные-параметры>) <тело>).
<Имя> — это тот символ, с которым нужно связать в окружении определение процедуры.
<Формальные-параметры> — это имена, которые в теле процедуры используются для отсылки
к соответствующим аргументам процедуры.
<Тело> — это выражение, которое вычислит результат применения процедуры,
когда формальные параметры будут заменены аргументами, к которым процедура будет применяться.
<Имя> и <формальные-параметры> заключены в скобки, как это было бы при вызове определяемой процедуры.
1.1.5. Подстановочная модель применения процедуры
Для составных процедур процесс вычисления протекает так:
- Чтобы применить составную процедуру к аргументам, требуется вычислить тело процедуры, заменив каждый формальный параметр соответствующим аргументом.
Следующий процесс называется подстановочной моделью (substitution model) применения процедуры.
-
(f 5), гдеdef f(a: Int): Int = sumOfSquares(a + 1, a * 2)))def sumOfSquares(x: Int, y: Int): Int = square(x) + square(y)def square(x: Int): Int = x * x
sumOfSquares(a + 1, a * 2)- восстанавливаем телоfsumOfSquares(5 + 1, 5 * 2)- заменяем формальный параметрaна аргумент5sumOfSquares(6, 10)- вычисляем аргументыsquare(6) + square(10)- восстанавливаем телоsumOfSquares6 * 6 + 10 * 10- восстанавливаем телоsquare
Аппликативный и нормальный порядки вычисления
В соответствии с описанием из раздела 1.1.3, интерпретатор сначала вычисляет оператор и операнды, а затем применяет получившуюся процедуру к получившимся аргументам. Но это не единственный способ осуществлять вычисления. Другая модель вычисления не вычисляет аргументы, пока не понадобится их значение. Вместо этого она подставляет на место параметров выражения-операнды, пока не получит выражение, в котором присутствуют только элементарные операторы, и лишь затем вычисляет его.
Процесс выглядит так:
(sum-of-squares (+ 5 1) (* 5 2))(+ (square (+ 5 1)) (square (* 5 2)))(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
за которыми последуют редукции:
(+ (* 6 6) (* 10 10))(+ 36 100)136
Это дает тот же результат, что и предыдущая модель вычислений, но процесс его получения отличается.
В частности, вычисление (+ 5 1) и (* 5 2) выполняется здесь по два раза,
в соответствии с редукцией выражения (* x x), где x заменяется, соответственно, на (+ 5 1) и (* 5 2).
Альтернативный метод «полная подстановка, затем редукция» известен под названием нормальный порядок вычислений (normal-order evaluation), в противоположность методу «вычисление аргументов, затем применение процедуры», которое называется аппликативным порядком вычислений (applicative-order evaluation).
1.1.6. Условные выражения и предикаты
Такая конструкция называется разбором случаев (case analysis).
def abs(x: Int): Int =
if x > 0 then x
else if x == 0 then 0
else -xОбщая форма условного выражения такова:
if <p1> then <e1>
else if <p2> then <e2>
...
else if <pn> then <en>
else <e>Она состоит из символов if, else if, else, за которыми следуют пары выражений (<pi> <ei>), называемых ветвями (clauses).
В каждой из этих пар первое выражение — предикат (predicate), то есть выражение,
значение которого интерпретируется как истина или ложь.
Условные выражения вычисляются так: сначала вычисляется предикат <p1>.
Если его значением является ложь, вычисляется <p2>. Если значение <p2> также ложь, вычисляется <p3>.
Этот процесс продолжается до тех пор, пока не найдется предикат, значением которого будет истина,
и в этом случае интерпретатор возвращает значение соответствующего выражения-следствия (consequent expression)
в качестве значения всего условного выражения.
Если ни один из <pi> ни окажется истинным, значение условного выражения равно <e>.
Упражнение 1.1
Ниже приведена последовательность выражений. Какой результат напечатает интерпретатор в ответ на каждое из них? Предполагается, что выражения вводятся в том же порядке, в каком они написаны.
10
// res0: Int = 10
(5 + 3 + 4)
// res1: Int = 12)
(9 - 1)
// res2: Int = 8)
(6 / 2)
// res3: Int = 3)
((2 * 4) + (4 - 6))
// res4: Int = 6)
val a = 3
// a: Int = 3
val b = a + 1
// b: Int = 4
(a + b + (a * b))
// res5: Int = 19)
(a == b)
// res6: Boolean = false)
if (b > a) && (b < (a * b)) then b else a
// res7: Int = 4
if a == 4 then 6
else if b == 4 then 6 + 7 + a
else 25
// res8: Int = 16
2 + (if b > a then b else a)
// res9: Int = 6
((if a > b then a else if a < b then b else -1) * (a + 1))
// res10: Int = 16Упражнение 1.2
Переведите следующее выражение в префиксную форму: \(\frac{5 + 4 + (2 - (3 - (6 + \frac{4}{5})))}{3(6 - 2)(2 - 7)}\)
Выражение в префиксной форме выглядит так:
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))Упражнение 1.3
Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумму квадратов двух больших из них.
def square(x: Int): Int = x * x
def sumOfSquares(x: Int, y: Int): Int = square(x) + square(y)
def f(a: Int, b: Int, c: Int): Int =
if a <= b && a <= c then sumOfSquares(b, c)
else if b <= c then sumOfSquares(a, c)
else sumOfSquares(a, b)
f(5, 3, 4)
// res11: Int = 41Упражнение 1.4
Заметим, что наша модель вычислений разрешает существование комбинаций, операторы которых — составные выражения. С помощью этого наблюдения опишите, как работает следующая процедура:
(define (a-plus-abs-b a b) ((if (> b 0) + -) a b))
Процедура a-plus-abs-b работает так:
- если
bбольше0, то выполняется процедура(+ a b) - в ином случае, выполняется процедура
(- a b)
Эта процедура складывает a и модуль числа b.
Упражнение 1.5
Бен Битобор придумал тест для проверки интерпретатора на то, с каким порядком вычислений он работает, аппликативным или нормальным. Бен определяет такие две процедуры:
(define (p) (p))(define (test x y) (if (= x 0) 0 y))Затем он вычисляет выражение
(test 0 (p))Какое поведение увидит Бен, если интерпретатор использует аппликативный порядок вычислений? Какое поведение он увидит, если интерпретатор использует нормальный порядок?
При аппликативном порядке вычисления результат (test 0 (p)) не будет получен,
потому что невозможно вычислить второй аргумент.
При нормально порядке вычисления результат (test 0 (p)) будет равен 0, потому что аргументы не вычисляются
и (test 0 (p)) разложится до:
if (= 0 0)
0
y, что в свою очередь вернет 0.
1.1.7 Пример: вычисление квадратного корня методом Ньютона
- Описание метода Ньютона
- Описание метода нахождения квадратного корня
- Описание метода нахождения кубического корня
Упражнение 1.6
Лиза П. Хакер не понимает, почему
ifдолжна быть особой формой. «Почему нельзя просто определить ее как обычную процедуру с помощью cond?» — спрашивает она. Лизина подруга Ева Лу Атор утверждает, что, разумеется, можно, и определяет новую версиюif:(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))Ева показывает Лизе новую программу:
(new-if (= 2 3) 0 5) 5 (new-if (= 1 1) 0 5) 0Обрадованная Лиза переписывает через
new-ifпрограмму вычисления квадратного корня:(define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))Что получится, когда Лиза попытается использовать эту процедуру для вычисления квадратных корней?
При аппликативном порядке будут пытаться вычисляться все аргументы процедуры sqrt-iter, в том числе и последний,
который использует sqrt-iter, а значит процедура войдет в бесконечную рекурсию.
Упражнение 1.7
Проверкаgood-enough?, которую мы использовали для вычисления квадратных корней, будет довольно неэффективна для поиска квадратных корней от очень маленьких чисел. Кроме того, в настоящих компьютерах арифметические операции почти всегда вычисляются с ограниченной точностью. Поэтому наш тест оказывается неадекватным и для очень больших чисел. Альтернативный подход к реализацииgood-enough?состоит в том, чтобы следить, как от одной итерации к другой изменяетсяguess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение. Верно ли, что на больших и маленьких числах она работает лучше?
Можно предложить следующую реализацию:
def goodEnough(guess: Double, next: Double): Boolean =
math.abs(guess - next) < 0.001
def average(x: Double, y: Double): Double = (x + y) / 2
def improve(guess: Double, x: Double): Double =
average(guess, x / guess)
def sqrtIter(guess: Double, x: Double): Double =
val next = improve(guess, x)
if goodEnough(guess, next) then guess
else sqrtIter(next, x)
def sqrt(x: Double): Double = sqrtIter(1.0, x)
sqrt(2.0)
// res12: Double = 1.4142156862745097
sqrt(1000000)
// res13: Double = 1000.0001533016629Упражнение 1.8
Метод Ньютона для кубических корней основан на том, что если
yявляется приближением к кубическому корню изx, то мы можем получить лучшее приближение по формуле \(\frac{\frac{x}{y^2} + 2y}{3}\).С помощью этой формулы напишите процедуру вычисления кубического корня, подобную процедуре для квадратного корня.
Процедура вычисления кубического корня:
def square(x: Double): Double = x * x
def goodEnough(guess: Double, next: Double): Boolean =
math.abs(guess - next) < 0.001
def improve(guess: Double, x: Double): Double =
((x / square(guess)) + 2 * guess) / 3
def cubeIter(guess: Double, x: Double): Double =
val next = improve(guess, x)
if goodEnough(guess, next) then next
else cubeIter(next, x)
def cubeOf(x: Double): Double = cubeIter(1.0, x)
cubeOf(2.0)
// res15: Double = 1.2599210500177698
cubeOf(1000000)
// res16: Double = 100.000000000053131.1.8. Процедуры как абстракции типа «черный ящик»
Определение sqrtIter рекурсивно (recursive); это означает, что процедура определяется в терминах самой себя.
Заметим, что задача вычисления квадратных корней естественным образом разбивается на подзадачи:
как понять, что очередное приближение нас устраивает,
как улучшить очередное приближение, и так далее.
Каждая из этих задач решается с помощью отдельной процедуры.
Вся программа sqrt может рассматриваться как пучок процедур, отражающий декомпозицию задачи на подзадачи.
Важность декомпозиционной стратегии не просто в том, что задача разделяется на части.
Существенно то, что каждая процедура выполняет точно определенную задачу, которая может быть использована
при определении других процедур.
Например, когда мы определяем процедуру goodenough? с помощью square,
мы можем рассматривать процедуру square как «черный ящик».
В этот момент нас не интересует, как она вычисляет свой результат, — важно
только то, что она способна вычислить квадрат.
Действительно, пока мы рассматриваем процедуру good-enough?, square — не совсем процедура,
но скорее абстракция процедуры, так называемая процедурная абстракция (procedural abstraction).
Локальные имена
У формального параметра особая роль в определении процедуры: не имеет значения, какое у этого параметра имя. Такое имя называется связанной переменной (bound variable), и мы будем говорить, что определение процедуры связывает (binds) свои формальные параметры. Значение процедуры не изменяется, если во всем ее определении параметры последовательным образом переименованы. Если переменная не связана, мы говорим, что она свободна (free). Множество выражений, для которых связывание определяет имя, называется областью действия (scope) этого имени. В определении процедуры связанные переменные, объявленные как формальные параметры процедуры, имеют своей областью действия тело процедуры.
Внутренние определения и блочная структура
Для того чтобы локализовать подпроцедуры, спрятав их внутри sqrt, так,
чтобы sqrt могла сосуществовать с другими последовательными приближениями,
при том что у каждой из них была бы своя собственная процедура good-enough?,
мы разрешаем процедуре иметь внутренние определения, локальные для этой процедуры.
Например, при решении задачи вычисления квадратного корня мы можем написать:
def sqrt(x: Double): Double =
def goodEnough(guess: Double, next: Double): Boolean = math.abs(guess - next) < 0.001
def average(a: Double, b: Double): Double = (a + b) / 2
def improve(guess: Double): Double = average(guess, x / guess)
def sqrtIter(guess: Double): Double =
val next = improve(guess)
if goodEnough(guess, next) then guess
else sqrtIter(next)
sqrtIter(1.0)
sqrt(2.0)
// res17: Double = 1.4142156862745097
sqrt(1000000)
// res18: Double = 1000.0001533016629Такое вложение определений, называемое блочной структурой (block structure), дает
правильное решение для простейшей задачи упаковки имен.
Помимо того, что мы можем вложить определения вспомогательных процедур внутрь главной, мы можем их упростить.
Поскольку переменная x связана в определении sqrt, процедуры good-enough?, improve и sqrt-iter,
которые определены внутри sqrt, находятся в области действия x.
Таким образом, нет нужды явно передавать x в каждую из этих процедур.
Вместо этого мы можем сделать x свободной переменной во внутренних определениях, как это показано ниже.
Тогда x получит свое значение от аргумента, с которым вызвана объемлющая их процедура sqrt.
Такой порядок называется лексической сферой действия (lexical scoping) переменных.
1.2. Процедуры и порождаемые ими процессы
1.2.1. Линейные рекурсия и итерация
Возьмем первый процесс вычисления факториала:
def factorial(n: Int): Int =
if n == 1 then 1
else n * factorial(n - 1)
factorial(6) // 720 Подстановочная модель:
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720Подстановочная модель показывает сначала серию расширений, а затем сжатие. Расширение происходит по мере того, как процесс строит цепочку отложенных операций (deferred operations), в данном случае цепочку умножений. Сжатие происходит тогда, когда выполняются эти отложенные операции. Такой тип процесса, который характеризуется цепочкой отложенных операций, называется рекурсивным процессом (recursive process). Выполнение этого процесса требует, чтобы интерпретатор запоминал, какие операции ему нужно выполнить впоследствии. При вычислении n! длина цепочки отложенных умножений, а следовательно, и объем информации, который требуется, чтобы ее сохранить, растет линейно с ростом n (пропорционален n), как и число шагов. Такой процесс называется линейно рекурсивным процессом (linear recursive process).
Напротив, второй процесс не растет и не сжимается.
def factorial(n: Int): Int =
factIter(1, 1, n)
def factIter(product: Int, counter: Int, maxCount: Int): Int =
if counter > maxCount then product
else factIter(counter * product, counter + 1, maxCount)
factorial(6) // 720Подстановочная модель:
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720На каждом шаге при любом значении n необходимо помнить лишь текущие значения переменных product, counter и
max-count. Такой процесс мы называем итеративным (iterative process).
В общем случае, итеративный процесс — это такой процесс, состояние которого можно описать конечным числом переменных состояния (state variables) плюс заранее заданное правило, определяющее, как эти переменные состояния изменяются от шага к шагу, и плюс (возможно) тест на завершение, который определяет условия, при которых процесс должен закончить работу. При вычислении n! число шагов линейно растет с ростом n. Такой процесс называется линейно итеративным процессом (linear iterative process).
Упражнение 1.9
Каждая из следующих двух процедур определяет способ сложения двух положительных целых чисел с помощью процедур
inc, которая добавляет к своему аргументу 1, иdec, которая отнимает от своего аргумента 1.(define (+ a b) (if (= a 0) b (inc (+ (dec a) b))))(define (+ a b) (if (= a 0) b (+ (dec a) (inc b))))Используя подстановочную модель, проиллюстрируйте процесс, порождаемый каждой из этих процедур, вычислив
(+ 4 5). Являются ли эти процессы итеративными или рекурсивными?
Первая функция является рекурсивной и иллюстрируется следующим образом:
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9Вторая функция - итеративная (при каждом шаге достаточно помнить только два значения - a и b).
Иллюстрация:
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9Упражнение 1.10
Следующая процедура вычисляет математическую функцию, называемую функцией Аккермана.
(define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1))))))Каковы значения следующих выражений?
(A 1 10)(A 2 4)(A 3 3)
Функцию Аккермана можно определить так:
def functionAckermann(x: Int, y: Int): Int =
if y == 0 then 0
else if x == 0 then 2 * y
else if y == 1 then 2
else functionAckermann(x - 1, functionAckermann(x, y - 1))
functionAckermann(1, 10)
// res19: Int = 1024
functionAckermann(2, 4)
// res20: Int = 65536
functionAckermann(3, 3)
// res21: Int = 65536Рассмотрим следующие процедуры, где
A— процедура, определенная выше:
(define (f n) (A 0 n))(define (g n) (A 1 n))(define (h n) (A 2 n))Дайте краткие математические определения функций, вычисляемых процедурами
f,gиhдля положительных целых значенийn.
Для малых x функция Аккермана равносильна следующим функциям:
f <=> 2*ng <=> 2^nh <=> 2^2^...^2 (n раз)
1.2.2. Древовидная рекурсия
Существует еще одна часто встречающаяся схема вычислений, называемая древовидная рекурсия (tree recursion). В качестве примера рассмотрим вычисление последовательности чисел Фибоначчи, в которой каждое число является суммой двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Общее правило для чисел Фибоначчи можно сформулировать так:
Можно немедленно преобразовать это определение в процедуру:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))Упражнение 1.11
Функция
fопределяется правилом:f(n) = n, еслиn < 3, иf(n) = f(n − 1) + f(n − 2) + f(n − 3), еслиn ≥ 3.Напишите процедуру, вычисляющую
fс помощью рекурсивного процесса.Напишите процедуру, вычисляющую
fс помощью итеративного процесса.
Рекурсивный процесс:
def recursion(n: Int): Int =
if n < 3 then n
else recursion(n - 1) + recursion(n - 2) + recursion(n - 3)Итеративный процесс:
def iteration(n: Int): Int =
def loop(a: Int, b: Int, c: Int, count: Int): Int =
if count == 0 then c
else loop(a + b + c, a, b, count - 1)
loop(2, 1, 0, n)Упражнение 1.12
Приведенная ниже таблица называется треугольником Паскаля (Pascal’s triangle):
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . .
Все числа по краям треугольника равны
1, а каждое число внутри треугольника равно сумме двух чисел над ним.Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощью рекурсивного процесса.
def pascalsTriangle(n: Int, k: Int): Int =
if n == 0 || k == n || k == 0 then 1
else pascalsTriangle(n - 1, k - 1) + pascalsTriangle(n - 1, k)
pascalsTriangle(4, 2)
// res22: Int = 6Упражнение 1.13
Докажите, что Fib(n) есть целое число, ближайшее к \(\frac{\varphi^{n}}{\sqrt{5}}\), где \(\varphi = \frac{1 + \sqrt{5}}{2}\).
Указание: пусть \(\psi = \frac{1 - \sqrt{5}}{2}\). С помощью определения чисел Фибоначчи и индукции докажите, что Fib(n) = \(\frac{\varphi^{n} - \psi^{n}}{\sqrt{5}} \).
Доказательство:
-
Заметим, что \(\varphi^{2} = \varphi^{1} + 1\):
- \(\varphi^{2} = \frac{(1 + \sqrt{5})^{2}}{4} = \frac{6 + 2\sqrt{5}}{4} = 1 + \frac{2 + 2\sqrt{5}}{4} = 1 + \varphi\)
-
а также, что \(\psi^{2} = \psi^{1} + 1\):
- \(\psi^{2} = \frac{(1 - \sqrt{5})^{2}}{4} = \frac{6 - 2\sqrt{5}}{4} = 1 + \frac{2 - 2\sqrt{5}}{4} = 1 + \psi\)
- n == 0, тогда \(Fib(0) = \frac{\varphi^{0} − \psi^{0}}{\sqrt{5}} = \frac{1 − 1}{\sqrt{5}} = 0\) - верно.
-
n > 0,
- Fib(n) =
- Fib(n - 1) + Fib(n - 2) =
- \(\frac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\varphi^{n-2} - \psi^{n-2}}{\sqrt{5}} = \)
- \(\frac{(\varphi^{n-1} + \varphi^{n-2}) - (\psi^{n-1} + \psi^{n-2})}{\sqrt{5}} = \)
- \(\frac{(\varphi^{n-2}(1 + \varphi)) - (\psi^{n-2}(1 + \psi))}{\sqrt{5}} = \)
- \(\frac{\varphi^{n-2}*\varphi^{2} - \psi^{n-2}*\psi^{2}}{\sqrt{5}} = \)
- \(\frac{\varphi^{n} - \psi^{n}}{\sqrt{5}} \)
1.2.3. Порядки роста
Предшествующие примеры показывают, что процессы могут значительно различаться по количеству вычислительных ресурсов, которые они потребляют. Удобным способом описания этих различий является понятие порядка роста (order of growth), которое дает общую оценку ресурсов, необходимых процессу при увеличении его входных данных.
Пусть n — параметр, измеряющий размер задачи, и пусть R(n) — количество ресурсов, необходимых процессу для решения задачи размера n.
Мы говорим, что R(n) имеет порядок роста Θ(f(n)), что записывается R(n) = Θ(f(n)) и произносится «тета от f(n)», если существуют положительные постоянные \(k_1\) и \(k_2\), независимые от n, такие, что \(k_1 \times f(n) \leq R(n) \leq k_2 \times f(n)\) для всякого достаточно большого n. (Другими словами, значение R(n) заключено между \(k_1 \times f(n)\) и \(k_2 \times f(n)\).)
Упражнение 1.14
Нарисуйте дерево, иллюстрирующее процесс, который порождается процедурой
count-changeиз раздела 1.2.2 при размене11центов.def countChange(amount: Int): Int = def firstDenomination(kindOfCoins: Int): Int = if kindOfCoins == 1 then 1 else if kindOfCoins == 2 then 5 else if kindOfCoins == 3 then 10 else if kindOfCoins == 4 then 25 else 50 def cc(amount: Int, kindOfCoins: Int): Int = if amount == 0 then 1 else if amount < 0 || kindOfCoins == 0 then 0 else cc(amount, kindOfCoins - 1) + cc(amount - firstDenomination(kindOfCoins), kindOfCoins) cc(amount, 5) countChange(100) // 292Каковы порядки роста памяти и числа шагов, используемых этим процессом при увеличении суммы, которую требуется разменять?
Поддерево cc 6 1:
-
cc 6 1-
cc 6 00
-
cc 5 1-
cc 5 00
-
cc 4 1-
cc 4 00
-
cc 3 1-
cc 3 00
-
cc 2 1-
cc 2 00
-
cc 1 1-
cc 1 00
-
cc 0 11
-
-
-
-
-
-
Дерево count-change 11:
-
cc 11 5-
cc 11 4-
cc 11 3-
cc 11 2-
cc 11 1-
cc 11 00
-
cc 10 1-
cc 10 00
-
cc 9 1-
cc 9 00
-
cc 8 1-
cc 8 00
-
cc 7 1-
cc 7 00
- Поддерево
cc 6 1
-
-
-
-
-
-
cc 6 2- Поддерево
cc 6 1 -
cc 1 2-
cc 1 1-
cc 1 00
-
cc 0 11
-
-
cc -4 20
-
- Поддерево
-
-
cc 1 3-
cc 1 2-
cc 1 1-
cc 1 00
-
cc 0 11
-
-
cc -4 20
-
-
cc -9 30
-
-
-
cc -14 40
-
-
cc -39 50
-
Порядки роста памяти и числа шагов равны \(\Theta (n^2)\).
Упражнение 1.15
Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением
sin x ≈ xпри малыхxи употребить тригонометрическое тождество \(sin(x) = 3sin(\frac{x}{3}) - 4sin^{3}(\frac{x}{3})\) для уменьшения значения аргументаsin. (В этом упражнении будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.)Эта идея используется в следующих процедурах:
(define (cube x) (* x x x)) (define (p x) (- (* 3 x) (* 4 (cube x)))) (define (sine angle) (if (not (> (abs angle) 0.1)) angle (p (sine (/ angle 3.0)))))а. Сколько раз вызывается процедура
pпри вычислении(sine 12.15)?б. Каковы порядки роста в терминах количества шагов и используемой памяти (как функция
a) для процесса, порождаемого процедуройsineпри вычислении(sine a)?
На Scala эта программа будет выглядеть так:
def cube(x: Double): Double = x * x * x
def p(x: Double): Double =
3 * x - 4 * cube(x)
def sine(angle: Double): Double =
if math.abs(angle) <= 0.1 then angle
else p(sine(angle / 3.0))
sine(12.15)
// res23: Double = -0.39980345741334а) Процедура p будет вызываться roundUp(12.15 / 3) = 5 раз.
б) Количество шагов будет равняться 2 * roundUp(a / 3), столько же будет использование памяти.
1.2.4. Возведение в степень
Метод возведения в степень с логарифмической сложностью:
def isEven(n: Int): Boolean = n % 2 == 0
def square(n: Int): Int = n * n
def fastExpt(b: Int, n: Int): Int =
if n == 0 then 1
else if isEven(n) then square(fastExpt(b, n / 2))
else b * fastExpt(b, n - 1)Упражнение 1.16
Напишите процедуру, которая развивается в виде итеративного процесса и реализует возведение в степень за логарифмическое число шагов, какfast-expt. (Указание: используя наблюдение, что \((b^{n/2})^{2} = (b^{2})^{n/2} \), храните, помимо значения степениnи основанияb, дополнительную переменную состоянияa, и определите переход между состояниями так, чтобы произведение \((ab)^{n}\) от шага к шагу не менялось. Вначале значениеaберется равным1, а ответ получается как значениеaв момент окончания процесса. В общем случае метод определения инварианта (invariant quantity), который не изменяется при переходе между шагами, является мощным способом размышления о построении итеративных алгоритмов.)
На Scala эта программа будет выглядеть так:
def power(b: Long, n: Long): BigInt =
@scala.annotation.tailrec
def loop(base: BigInt, power: Long, acc: BigInt): BigInt =
if power == 0 then acc
else if power % 2 == 0 then loop(base * base, power / 2, acc)
else loop(base, power - 1, base * acc)
loop(b, n, 1)
power(2, 10)
// res24: BigInt = 1024Упражнение 1.17
Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении. Подобным же образом можно производить умножение с помощью повторяющегося сложения. Следующая процедура умножения (в которой предполагается, что наш язык способен только складывать, но не умножать) аналогична процедуре
expt:(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))Этот алгоритм затрачивает количество шагов, линейно пропорциональное
b. Предположим теперь, что, наряду со сложением, у нас есть операцииdouble, которая удваивает целое число, иhalve, которая делит (четное) число на2. Используя их, напишите процедуру, аналогичнуюfast-expt, которая затрачивает логарифмическое число шагов.
На Scala эта программа будет выглядеть так:
def double(n: Long): Long = n << 1
def halve(n: Long): Long = n >> 1
def fastMul(a: Long, b: Long): Long =
if b == 0 then 0L
else if b % 2 == 0 then double(fastMul(a, halve(b)))
else a + fastMul(a, b - 1)
fastMul(22, 10)
// res25: Long = 220LУпражнение 1.18
Используя результаты упражнений 1.16 и 1.17, разработайте процедуру, которая порождает итеративный процесс для умножения двух чисел с помощью сложения, удвоения и деления пополам, и затрачивает логарифмическое число шагов.
На Scala эта программа будет выглядеть так:
def double(n: Long): Long = n << 1
def halve(n: Long): Long = n >> 1
def fastMul(a: Long, b: Long): Long =
@scala.annotation.tailrec
def loop(base: Long, times: Long, acc: Long): Long =
if times == 0 then acc
else if times % 2 == 0 then loop(double(base), halve(times), acc)
else loop(base, times - 1, base + acc)
loop(a, b, 0)
fastMul(22, 10)
// res27: Long = 220LУпражнение 1.19
Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов. Вспомните трансформацию переменных состояния \(a\) и \(b\) процесса \(fib-iter\) из раздела 1.2.2: \(a ← a + b\) и \(b ← a\). Назовем эту трансформацию \(T\) и заметим, что \(n\)-кратное применение \(T\), начиная с \(1\) и \(0\), дает нам пару \(Fib(n + 1)\) и \(Fib(n)\). Другими словами, числа Фибоначчи получаются путем применения \(T^{n}\), \(n\)-ой степени трансформации \(T\), к паре \((1,0)\). Теперь рассмотрим \(T\) как частный случай \(p = 0\), \(q = 1\) в семействе трансформаций \(T_{pq}\), где \(T_{pq}\) преобразует пару \((a,b)\) по правилу \(a ← bq + aq + ap\), \(b ← bp + aq\).
Покажите, что двукратное применение трансформации \(T_{pq}\) равносильно однократному применению трансформации \(T_{p′q′}\) того же типа, и вычислите \(p′\) и \(q′\) через \(p\) и \(q\). Это дает нам прямой способ возводить такие трансформации в квадрат, и таким образом, мы можем вычислить \(T^{n}\) с помощью последовательного возведения в квадрат, как в процедуре \(fast-expt\). Используя все эти идеи, завершите следующую процедуру, которая дает результат за логарифмическое число шагов:
(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b <??> ; вычислить p’ <??> ; вычислить q’ (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))
Применим трансформацию два раза:
- \(a_{2} ← b_{1}q + a_{1}q + a_{1}p ← (b_{0}p + a_{0}q)q + (b_{0}q + a_{0}p + a_{0}q)(q + p) ← b_{0}(2pq + q^{2}) + a_{0}(q^{2} + (p + q)^{2})\)
- \(b_{2} ← b_{1}p + a_{1}q ← (b_{0}p + a_{0}q)p + (b_{0}q + a_{0}p + a_{0}q)q ← b_{0}(p^{2} + q^{2}) + a_{0}(2pq + q^{2})\)
Представим, что \(p′ = p^{2} + q^{2}\) и \(q′ = 2pq + q^{2}\). Тогда
- \(a_{2} ← b_{0}q′ + a_{0}(p′ + q′)\)
- \(b_{2} ← b_{0}p′ + a_{0}q′\)
Это означает, что \((T_{pq})^{2} = T_{p′q′}\)
Что позволяет реализовать программу так:
def fastFib(n: Int): BigInt =
@scala.annotation.tailrec
def loop(a: BigInt, b: BigInt, p: BigInt, q: BigInt, count: Int): BigInt =
if count == 0 then b
else if count % 2 == 0 then
loop(a, b, p * p + q * q, 2 * p * q + q * q, count / 2)
else loop(b * q + a * (p + q), b * p + a * q, p, q, count - 1)
loop(1, 0, 0, 1, n)
fastFib(30)
// res28: BigInt = 8320401.2.5. Нахождение наибольшего общего делителя
Вычисление НОД с помощью алгоритма Евклида:
@annotation.tailrec
def gcd(a: Int, b: Int): Int =
if b == 0 then a else gcd(b, a % b)
gcd(4851, 3003) // 231 Упражнение 1.20
Процесс, порождаемый процедурой, разумеется, зависит от того, по каким правилам работает интерпретатор. В качестве примера рассмотрим итеративную процедуру gcd, приведенную выше. Предположим, что мы вычисляем эту процедуру с помощью нормального порядка, описанного в разделе 1.1.5. (Правило нормального порядка вычислений для if описано в упражнении 1.5.) Используя подстановочную модель для нормального порядка, проиллюстрируйте процесс, порождаемый при вычислении (gcd 206 40) и укажите, какие операции вычисления остатка действительно выполняются. Сколько операций remainder выполняется на самом деле при вычислении (gcd 206 40) в нормальном порядке? При вычислении в аппликативном порядке?
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))Нормальный порядок:
gcd 206 40
if (= 40 0)
206
(gcd 40 (remainder 206 40))
gcd 40 (remainder 206 40)
if (= (remainder 206 40) 0) // +1
40
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
gcd (remainder 206 40) (remainder 40 (remainder 206 40))
if (= (remainder 40 (remainder 206 40)) 0) // +2
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
Пусть a = (remainder 40 (remainder 206 40)), b = (remainder (remainder 206 40) a)
gcd a b
if (= b 0) // +4
a
(gcd b c)
, где c = reminder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
gcd b c
if (= c 0) // +7
2
(gcd c (reminder b c))
2Итого, 14 вычислений при нормальном порядке.
Аппликативный порядок:
if (= 40 0)
206
(gcd 40 (remainder 206 40))
gcd 40 (remainder 206 40) // +1
gcd 40 6
if (= 6 0)
40
(gcd 6 (remainder 40 6))
gcd 6 (remainder 40 6) // +1
gcd 6 4
if (= 4 0)
6
(gcd 4 (remainder 6 4))
gcd 4 (remainder 6 4) // +1
gcd 4 2
if (= 2 0)
4
(gcd 2 (remainder 4 2))
gcd 2 (remainder 4 2) // +1
gcd 2 0
if (= 0 0)
2
(gcd 0 (remainder 2 0))
2 Итого, всего 5 вычислений при аппликативном порядке.
1.2.6. Пример: проверка на простоту
Упражнение 1.21
С помощью процедуры smallest-divisor найдите наименьший делитель следующих чисел: 199, 1999, 19999.
Решение на Scala:
def divides(a: Long, b: Long): Boolean = a % b == 0
def findDivisor(n: Long, d: Long): Long =
if d * d > n then n
else if divides(n, d) then d
else findDivisor(n, d + 1)
def smallestDivisor(n: Long): Long = findDivisor(n, 2)
smallestDivisor(199)
// res29: Long = 199L
smallestDivisor(1999)
// res30: Long = 1999L
smallestDivisor(19999)
// res31: Long = 7LУпражнение 1.22
Большая часть реализаций Лиспа содержат элементарную процедуру runtime, которая возвращает целое число, показывающее, как долго работала система (например, в миллисекундах). Следующая процедура timed-prime-test, будучи вызвана с целым числом n, печатает n и проверяет, простое ли оно. Если n простое, процедура печатает три звездочки и количество времени, затраченное на проверку.
(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time))Используя эту процедуру, напишите процедуру search-for-primes, которая проверяет на простоту все нечетные числа в заданном диапазоне.
С помощью этой процедуры найдите наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000.
Посмотрите, сколько времени затрачивается на каждое простое число. Поскольку алгоритм проверки имеет порядок роста Θ(√n), Вам следовало бы ожидать, что проверка на простоту чисел, близких к 10 000, занимает в √10 раз больше времени, чем для чисел, близких к 1000.
Подтверждают ли это Ваши замеры времени?
Хорошо ли поддерживают предсказание √n данные для 100 000 и 1 000 000?
Совместим ли Ваш результат с предположением, что программы на Вашей машине затрачивают на выполнение задач время, пропорциональное числу шагов?
На Scala эта программа будет выглядеть так:
import java.time.Instant
def divides(a: Long, b: Long): Boolean = a % b == 0
def findDivisor(n: Long, d: Long): Long =
if d * d > n then n
else if divides(n, d) then d
else findDivisor(n, d + 1)
def smallestDivisor(n: Long): Long = findDivisor(n, 2)
def isPrime(n: Long): Boolean = smallestDivisor(n) == n
def reportPrime(elapsedTime: Long): Unit =
println(" *** ")
println(s"${elapsedTime} ms")
def startPrimeTest(n: Long, startTime: Long): Option[Long] =
if isPrime(n) then
println(s"n = $n")
reportPrime(Instant.now().toEpochMilli - startTime)
Some(n)
else None
def timedPrimeTest(n: Long): Option[Long] =
startPrimeTest(n, Instant.now().toEpochMilli())
def searchForPrimes(start: Long, end: Long): Seq[Long] =
(start to end).flatMap(timedPrimeTest)
searchForPrimes(1000, 1000 + 1000) // Vector(1009, 1013, 1019, ...)
searchForPrimes(10000, 10000 + 1000) // Vector(10007, 10009, 10037, ...)
searchForPrimes(100000, 100000 + 1000) // Vector(100003, 100019, 100043, ...)
searchForPrimes(1000000, 1000000 + 1000) // Vector(1000003, 1000033, 1000037, ...)Упражнение 1.23
Процедура smallest-divisor в начале этого раздела проводит множество лишних проверок: после того, как она проверяет, делится ли число на 2, нет никакого смысла проверять делимость на другие четные числа. Таким образом, вместо последовательности 2, 3, 4, 5, 6..., используемой для test-divisor, было бы лучше использовать 2, 3, 5, 7, 9....
Чтобы реализовать такое улучшение, напишите процедуру next, которая имеет результатом 3, если получает 2 как аргумент, а иначе возвращает свой аргумент плюс 2. Используйте (next test-divisor) вместо (+ test-divisor 1) в smallest-divisor.
Используя процедуру timed-prime-test с модифицированной версией smallest-divisor, запустите тест для каждого из 12 простых чисел, найденных в упражнении 1.22. Поскольку эта модификация снижает количество шагов проверки вдвое, Вы должны ожидать двукратного ускорения проверки. Подтверждаются ли эти ожидания? Если нет, то каково наблюдаемое соотношение скоростей двух алгоритмов, и как Вы объясните то, что оно отличается от 2?
На Scala эта программа будет выглядеть так:
def divides(a: Long, b: Long): Boolean = a % b == 0
def next(a: Long): Long =
if a == 2 then 3 else a + 2
def findDivisor(n: Long, d: Long): Long =
if d * d > n then n
else if divides(n, d) then d
else findDivisor(n, next(d))
def smallestDivisor(n: Long): Long = findDivisor(n, 2)
def isPrime(n: Long): Boolean = smallestDivisor(n) == n
Seq(1009, 1013, 1019, 10007, 10009, 10037, 100003, 100019, 100043, 1000003,
1000033, 1000037).forall(isPrime)
// res33: Boolean = true Упражнение 1.24
Модифицируйте процедуру timed-prime-test из упражнения 1.22 так, чтобы она использовала fast-prime? (метод Ферма) и проверьте каждое из 12 простых чисел, найденных в этом упражнении. Исходя из того, что у теста Ферма порядок роста Θ(log n), то какого соотношения времени Вы бы ожидали между проверкой на простоту поблизости от 1 000 000 и поблизости от 1000. Подтверждают ли это Ваши данные? Можете ли Вы объяснить наблюдаемое несоответствие, если оно есть?
На Scala эта программа будет выглядеть так:
import java.time.Instant
import scala.util.Random
@annotation.tailrec
def isProbablyPrime(p: Long, max_test: Int): Boolean =
(max_test <= 0) || {
(BigInt(Random.nextLong(p)).modPow(p - 1, p) == 1) &&
isProbablyPrime(p, max_test - 1)
}
def reportPrime(elapsedTime: Long): Unit =
println(" *** ")
println(s"${elapsedTime} ms")
def startPrimeTest(n: Long, startTime: Long): Option[Long] =
if isProbablyPrime(n, 10) then
println(s"n = $n")
reportPrime(Instant.now().toEpochMilli - startTime)
Some(n)
else None
def timedPrimeTest(n: Long): Option[Long] =
startPrimeTest(n, Instant.now().toEpochMilli())Упражнение 1.25
Лиза П. Хакер жалуется, что при написании expmod мы делаем много лишней работы. В конце концов, говорит она, раз мы уже знаем, как вычислять степени, можно просто написать
(define (expmod base exp m) (remainder (fast-expt base exp) m))Права ли она? Стала бы эта процедура столь же хорошо работать при проверке простых чисел? Объясните.
Стала бы работать медленнее по причине того, что много времени (и памяти) уходило бы на вычисление "больших" чисел.
Упражнение 1.26
У Хьюго Дума большие трудности в упражнении 1.24. Процедура fast-prime? у него работает медленнее, чем prime?. Хьюго просит помощи у своей знакомой Евы Лу Атор. Вместе изучая код Хьюго, они обнаруживают, что тот переписал процедуру expmod с явным использованием умножения вместо того, чтобы вызывать square:
(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m))))Хьюго говорит: «Я не вижу здесь никакой разницы». «Зато я вижу, — отвечает Ева. — Переписав процедуру таким образом, ты превратил процесс порядка Θ(log n) в процесс порядка Θ(n)». Объясните
Потому что при использовании процедуры square аргумент процедуры (expmod base (/ exp 2) m) вычислялся только 1 раз, а в версии Хьюго - эта же процедура вычисляется два раза (каждый множитель по разу).
Проблемы можно было бы избежать, определив переменную для (expmod base (/ exp 2) m):
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
define a (expmod base (/ exp 2) m)
(remainder (* a a)
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))Упражнение 1.27
Покажите, что числа Кармайкла, перечисленные в сноске 47, действительно «обманывают» тест Ферма: напишите процедуру, которая берет целое число \(n\) и проверяет, правда ли \(a^{n}\) равняется \(a\) по модулю \(n\) для всех \(a < n\), и проверьте эту процедуру на этих числах Кармайкла.
На Scala эта программа будет выглядеть так:
def expmod(base: Long, exp: Long, m: Long): Long =
if exp == 0 then 1
else if exp % 2 == 0 then
val a = expmod(base, exp / 2, m)
a * a % m
else
val a = base * expmod(base, exp - 1, m)
a % m
def fermatTest(n: Long): Boolean =
(2L until n).forall(a => expmod(a, n, n) == a)
fermatTest(561) // true
fermatTest(1105) // true
fermatTest(1729) // true
fermatTest(2465) // true
fermatTest(2821) // true
fermatTest(6601) // true Упражнение 1.28
Один из вариантов теста Ферма, который невозможно обмануть, называется тест Миллера–Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980). Он основан на альтернативной формулировке Малой теоремы Ферма, которая состоит в том, что если \(n\) — простое число, а \(a\) — произвольное положительное целое число, меньшее \(n\), то \(a\) в \(n − 1\)-ой степени равняется \(1\) по модулю \(n\).
Проверяя простоту числа \(n\) методом Миллера–Рабина, мы берем случайное число \(a < n\) и возводим его в \(n − 1\)-ю степень по модулю \(n\) с помощью процедуры \(expmod\). Однако когда в процедуре
expmodмы проводим возведение в квадрат, мы проверяем, не нашли ли мы «нетривиальный квадратный корень из \(1\) по модулю \(n\)», то есть число, не равное \(1\) или \(n − 1\), квадрат которого по модулю \(n\) равен \(1\). Можно доказать, что если такой нетривиальный квадратный корень из \(1\) существует, то \(n\) - не простое число. Можно, кроме того, доказать, что если \(n\) — нечетное число, не являющееся простым, то по крайней мере для половины чисел \(a < n\) вычисление \(a^{n−1}\) с помощью такой процедуры обнаружит нетривиальный квадратный корень из \(1\) по модулю \(n\) (вот почему тест Миллера–Рабина невозможно обмануть).Модифицируйте процедуру \(expmod\) так, чтобы она сигнализировала обнаружение нетривиального квадратного корня из \(1\), и используйте ее для реализации теста Миллера–Рабина с помощью процедуры, аналогичной \(fermat-test\). Проверьте свою процедуру на нескольких известных Вам простых и составных числах. Подсказка: удобный способ заставить \(expmod\) подавать особый сигнал — заставить ее возвращать \(0\).
На Scala эта программа будет выглядеть так:
import scala.util.Random
def square(x: Long): Long = x * x
def expmod(base: Long, exp: Long, m: Long): Long =
if exp == 0 then 1
else if exp % 2 == 0 then
val candidate = expmod(base, exp / 2, m)
val root = square(candidate) % m
if root == 1 && candidate != 1 && candidate != m - 1 then 0
else root
else (base * expmod(base, exp - 1, m)) % m
def fermatTest(n: Long): Boolean =
def tryIt(a: Long): Boolean =
expmod(a, n - 1, n) == 1
tryIt(Random.nextLong(n - 1) + 1)
def fastIsPrime(n: Long, times: Int): Boolean =
(times <= 0) || (fermatTest(n) && fastIsPrime(n, times - 1))
fastIsPrime(19, 100) // true
fastIsPrime(199, 100) // true
fastIsPrime(1999, 100) // true
fastIsPrime(561, 100) // false
fastIsPrime(1105, 100) // false
fastIsPrime(1729, 100) // false
fastIsPrime(2465, 100) // false
fastIsPrime(2821, 100) // false
fastIsPrime(6601, 100) // false1.3. Формулирование абстракций с помощью процедур высших порядков
Процедура, принимающая другие процедуры как аргументы либо возвращающая их как значения, называется процедурой высшего порядка (higher-order procedure).
1.3.1. Процедуры в качестве аргументов
Определим процедуру суммирования, принимающую другие процедуры в качестве аргументов.
def cube(a: Double): Double = a * a * a
def sum(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
if a > b then 0.0
else term(a) + sum(term, next(a), next, b)
def integral(f: Double => Double, a: Double, b: Double, dx: Double): Double =
def addDx(x: Double): Double = x + dx
sum(f, a + dx / 2, addDx, b) * dx
integral(cube, 0.0, 1.0, 0.01) // 0.24998750000000042
integral(cube, 0.0, 1.0, 0.001) // 0.249999875000001Упражнение 1.29
Правило Симпсона — более точный метод численного интегрирования, чем представленный выше. С помощью правила Симпсона интеграл функции \(f\) между \(a\) и \(b\) приближенно вычисляется в виде \(\frac{h}{3} * [y_{0} + 4y_{1} + 2y_{2} + 4y_{3} + 2y_{4} + ... + 2y_{n-2} + 4y_{n-1} + y_{n}]\) , где \(h = \frac{b - a}{n}\), для какого-то четного целого числа \(n\), а \(y_{k} = f(a + kh)\). (Увеличение \(n\) повышает точность приближенного вычисления.) Определите процедуру, которая принимает в качестве аргументов \(f\), \(a\), \(b\) и \(n\), и возвращает значение интеграла, вычисленное по правилу Симпсона. С помощью этой процедуры проинтегрируйте \(cube\) между \(0\) и \(1\) (с \(n = 100\) и \(n = 1000\)) и сравните результаты с процедурой \(integral\), приведенной выше.
Решение на Scala:
def simpsonRule(f: Double => Double, a: Double, b: Double, n: Int): Double =
val h = (b - a) / n
def y(k: Int): Double =
val co = if k == 0 || k == n then 1 else if k % 2 == 0 then 2 else 4
co * f(a + k * h)
(0 to n).foldLeft(0.0)((acc, k) => acc + y(k)) * h / 3
simpsonRule(cube, 0.0, 1.0, 100) // 0.25000000000000006
simpsonRule(cube, 0.0, 1.0, 1000) // 0.25000000000000006Упражнение 1.30
Процедура
sumпорождает линейную рекурсию. Ее можно переписать так, чтобы суммирование выполнялось итеративно. Покажите, как сделать это, заполнив пропущенные выражения в следующем определении:(define (sum term a next b) (define (iter a result) (if <??> <??> (iter <??> <??>))) (iter <??> <??>))
Решение на Scala:
def cube(a: Double): Double = a * a * a
def sum(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
def iter(a: Double, result: Double): Double =
if a > b then result
else iter(next(a), result + term(a))
iter(a, 0.0)
def integral(f: Double => Double, a: Double, b: Double, dx: Double): Double =
def addDx(x: Double): Double = x + dx
sum(f, a + dx / 2, addDx, b) * dx
integral(cube, 0.0, 1.0, 0.01) // 0.24998750000000042
integral(cube, 0.0, 1.0, 0.001) // 0.24999987500000073Упражнение 1.31
а. Процедура \(sum\) — всего лишь простейшая из обширного множества подобных абстракций, которые можно выразить через процедуры высших порядков. Напишите аналогичную процедуру под названием \(product\), которая вычисляет произведение значений функции в точках на указанном интервале. Покажите, как с помощью этой процедуры определить \(factorial\). Кроме того, при помощи \(product\) вычислите приближенное значение \(\pi\) по формуле: \(\frac{\pi}{4} = \frac{2}{3} * \frac{4}{3} * \frac{4}{5} * \frac{6}{5} * \frac{6}{7} * \frac{8}{7} * ...\)
б. Если Ваша процедура \(product\) порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный.
Решение на Scala:
val identity: Double => Double = x => x
val nextNum: Double => Double = x => x + 1
val square: Double => Double = x => x * x
val piFraction: Double => Double = k =>
(2 * k) * (2 * k + 2) / square(2 * k + 1)
def productRec(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
if a > b then 1.0
else term(a) * productRec(term, next(a), next, b)
def factorialRec(n: Int): Int =
productRec(identity, 1, nextNum, n).toInt
factorialRec(10) // 3628800
def calculatePiRec(n: Int): Double =
4 * productRec(piFraction, 1, nextNum, n)
calculatePiRec(1000) // 3.142377365093882
def productIter(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
def iter(a: Double, result: Double): Double =
if a > b then result
else iter(next(a), result * term(a))
iter(a, 1.0)
def factorialIter(n: Int): Int =
productIter(identity, 1, nextNum, n).toInt
factorialIter(10) // 3628800
def calculatePiIter(n: Int): Double =
4 * productIter(piFraction, 1, nextNum, n)
calculatePiIter(1000) // 3.1423773650938855Упражнение 1.32
а. Покажите, что sum и product (упражнение 1.31) являются частными случаями еще более общего понятия, называемого накопление (accumulation), которое комбинирует множество термов с помощью некоторой общей функции накопления (accumulate combiner null-value term a next b)
Accumulate принимает в качестве аргументов те же описания термов и диапазона, что и sum с product, а еще процедуру combiner (двух аргументов), которая указывает, как нужно присоединить текущий терм к результату накопления предыдущих, и null-value, базовое значение, которое нужно использовать, когда термы закончатся. Напишите accumulate и покажите, как и sum, и product можно определить в виде простых вызовов accumulate.
б. Если Ваша процедура accumulate порождает рекурсивный процесс, перепишите ее так, чтобы она порождала итеративный. Если она порождает итеративный процесс, перепишите ее так, чтобы она порождала рекурсивный
Решение на Scala:
def accumulateRec(
combiner: (Double, Double) => Double,
nullValue: Double,
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
if a > b then nullValue
else
combiner(
term(a),
accumulateRec(combiner, nullValue, term, next(a), next, b)
)
def productRec(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
accumulateRec(_ * _, 1.0, term, a, next, b)
def accumulateIter(
combiner: (Double, Double) => Double,
nullValue: Double,
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
def iter(a: Double, result: Double): Double =
if a > b then result
else iter(next(a), combiner(result, term(a)))
iter(a, nullValue)
def productIter(
term: Double => Double,
a: Double,
next: Double => Double,
b: Double
): Double =
accumulateIter(_ * _, 1.0, term, a, next, b)Упражнение 1.33
Можно получить еще более общую версию accumulate (упражнение 1.32), если ввести понятие фильтра (filter) на комбинируемые термы. То есть комбинировать только те термы, порожденные из значений диапазона, которые удовлетворяют указанному условию.
Получающаяся абстракция filtered-accumulate получает те же аргументы, что и accumulate, плюс дополнительный одноаргументный предикат, который определяет фильтр. Запишите filtered-accumulate в виде процедуры. Покажите, как с помощью filtered-accumulate выразить следующее:
а. сумму квадратов простых чисел в интервале от a до b (в предположении, что процедура prime? уже написана);
б. произведение всех положительных целых чисел меньше n, которые просты по отношению к n (то есть всех таких положительных целых чисел i < n, что НОД(i, n) = 1).
Решение на Scala:
def filteredAccumulateRec(
combiner: (Double, Double) => Double,
nullValue: Double,
term: Double => Double,
a: Double,
next: Double => Double,
b: Double,
filter: Double => Boolean
): Double =
if a > b then nullValue
else
val nextA = term(a)
lazy val res =
filteredAccumulateRec(combiner, nullValue, term, next(a), next, b, filter)
if filter(nextA) then combiner(nextA, res)
else res
def filteredAccumulateIter(
combiner: (Double, Double) => Double,
nullValue: Double,
term: Double => Double,
a: Double,
next: Double => Double,
b: Double,
filter: Double => Boolean
): Double =
def iter(a: Double, result: Double): Double =
if a > b then result
else
val nextA = term(a)
val nextResult =
if filter(nextA) then combiner(result, nextA)
else result
iter(next(a), nextResult)
iter(a, nullValue)
def filteredAccumulate(
combiner: (Int, Int) => Int,
nullValue: Int,
term: Int => Int,
a: Int,
next: Int => Int,
b: Int,
filter: Int => Boolean
): Int = ???
def isPrime(n: Int): Boolean = ???
def sumPrimeSquares(a: Int, b: Int): Int =
filteredAccumulate(
combiner = (x, y) => x + y,
nullValue = 0,
term = x => x * x,
a = a,
next = x => x + 1,
b = b,
filter = isPrime
)
def gcd(a: Int, b: Int): Int = ???
def productPrimesLessThanN(n: Int): Int =
filteredAccumulate(
combiner = (x, y) => x * y,
nullValue = 1,
term = x => x,
a = 1,
next = x => x + 1,
b = n - 1,
filter = i => gcd(i, n) == 1
)1.3.2. Построение процедур с помощью lambda
Введем особую форму lambda, которая создает процедуры. С использованием lambda мы можем записать:
- (lambda (x) (+ x 4))
- (lambda (x) (/ 1.0 (* x (+ x 2))))
Упражнение 1.34
Допустим, мы определили процедуру
(define (f g) (g 2))Тогда мы имеем
(f square) 4(f (lambda (z) (* z (+ z 1)))) 6Что случится, если мы (извращенно) попросим интерпретатор вычислить комбинацию (f f)? Объясните.
1.3.3. Процедуры как обобщенные методы
Нахождение корней уравнений методом половинного деления
Метод половинного деления (half-interval method) — это простой, но мощный способ нахождения корней уравнения f(x) = 0, где f — непрерывная функция. Идея состоит в том, что если нам даны такие точки a и b, что f(a) < 0 < f(b), то функция f должна иметь по крайней мере один ноль на отрезке между a и b. Чтобы найти его, возьмем x, равное среднему между a и b, и вычислим f(x). Если f(x) > 0, то f должна иметь ноль на отрезке между a и x. Если f(x) < 0, то f должна иметь ноль на отрезке между x и b. Продолжая таким образом, мы сможем находить все более узкие интервалы, на которых f должна иметь ноль. Когда мы дойдем до точки, где этот интервал достаточно мал, процесс останавливается. Поскольку интервал неопределенности уменьшается вдвое на каждом шаге процесса, число требуемых шагов растет как Θ(log(L/T)), где L есть длина исходного интервала, а T есть допуск ошибки (то есть размер интервала, который мы считаем «достаточно малым»). Вот процедура, которая реализует эту стратегию:
def average(a: Double, b: Double): Double =
(a + b) / 2
val tolerance = 0.00001
def doesCloseEnough(a: Double, b: Double): Boolean =
math.abs(a - b) < tolerance
def search(f: Double => Double, negPoint: Double, posPoint: Double): Double =
val midpoint = average(negPoint, posPoint)
if doesCloseEnough(negPoint, posPoint) then midpoint
else
val testValue = f(midpoint)
if testValue > 0 then search(f, negPoint, midpoint)
else if testValue < 0 then search(f, midpoint, posPoint)
else midpoint
search(identity, -1, 1) // 0.0Мы предполагаем, что вначале нам дается функция f и две точки, в одной из которых значение функции отрицательно, в другой положительно. Сначала мы вычисляем среднее между двумя краями интервала. Затем мы проверяем, не является ли интервал уже достаточно малым, и если да, сразу возвращаем среднюю точку как ответ. Если нет, мы вычисляем значение f в средней точке. Если это значение положительно, мы продолжаем процесс с интервалом от исходной отрицательной точки до средней точки. Если значение в средней точке отрицательно, мы продолжаем процесс с интервалом от средней точки до исходной положительной точки. Наконец, существует возможность, что значение в средней точке в точности равно 0, и тогда средняя точка и есть тот корень, который мы ищем.
Нахождение неподвижных точек функций
Число x называется неподвижной точкой (fixed point) функции f, если оно удовлетворяет уравнению f(x) = x. Для некоторых функций f можно найти неподвижную точку, начав с какого-то значения и применяя f многократно: f(x), f(f(x)), f(f(f(x))), ... — пока значение не перестанет сильно изменяться. С помощью этой идеи мы можем составить процедуру fixed-point, которая в качестве аргументов принимает функцию и начальное значение и производит приближение к неподвижной точке функции. Мы многократно применяем функцию, пока не найдем два последовательных значения, разница между которыми меньше некоторой заданной чувствительности:
val tolerance = 0.00001
def fixedPoint(f: Double => Double, firstGuess: Double): Double =
def doesCloseEnough(a: Double, b: Double): Boolean =
math.abs(a - b) < tolerance
def tryGuess(guess: Double): Double =
val next = f(guess)
if doesCloseEnough(next, guess) then next
else tryGuess(next)
tryGuess(firstGuess)Упражнение 1.35
Покажите, что золотое сечение \(\varphi\) (раздел 1.2.2) есть неподвижная точка трансформации \(x → 1 + \frac{1}{x}\), и используйте этот факт для вычисления \(\varphi\) с помощью процедуры \(fixed-point\).
\(\varphi^{2} = \varphi + 1 => \varphi = 1 + \frac{1}{\varphi}\)
Решение на Scala:
fixedPoint(x => 1 + (1.0 / x), 1.0) // 1.6180327868852458Упражнение 1.36
Измените процедуру \(fixed-point\) так, чтобы она печатала последовательность приближений, которые порождает, с помощью примитивов \(newline\) и \(display\), показанных в упражнении 1.22. Затем найдите решение уравнения \(x^{x} = 1000\) путем поиска неподвижной точки \(x → \frac{log(1000)}{log(x)}\). (Используйте встроенную процедуру \(Scheme log\), которая вычисляет натуральные логарифмы.) Посчитайте, сколько шагов это занимает при использовании торможения усреднением и без него. (Учтите, что нельзя начинать \(fixed-point\) со значения \(1\), поскольку это вызовет деление на \(log(1) = 0\).)
Решение на Scala:
def average(a: Double, b: Double): Double = (a + b) / 2
val tolerance = 0.00001
def fixedPoint(f: Double => Double, firstGuess: Double): Double =
def doesCloseEnough(a: Double, b: Double): Boolean =
math.abs(a - b) < tolerance
def tryGuess(guess: Double): Double =
val next = f(guess)
println(next)
if doesCloseEnough(next, guess) then next
else tryGuess(next)
tryGuess(firstGuess)
fixedPoint(x => math.log(1000) / math.log(x), 10.0)
fixedPoint(x => average(x, math.log(1000) / math.log(x)), 10.0)В первом случае мы получаем такое приближение (33 итерации):
res0: Double = 4.555532257016376
// 2.9999999999999996
// 6.2877098228681545
// 3.7570797902002955
// 5.218748919675316
// 4.1807977460633134
// 4.828902657081293
// 4.386936895811029
// 4.671722808746095
// 4.481109436117821
// 4.605567315585735
// 4.522955348093164
// 4.577201597629606
// 4.541325786357399
// 4.564940905198754
// 4.549347961475409
// 4.5596228442307565
// 4.552843114094703
// 4.55731263660315
// 4.554364381825887
// 4.556308401465587
// 4.555026226620339
// 4.55587174038325
// 4.555314115211184
// 4.555681847896976
// 4.555439330395129
// 4.555599264136406
// 4.555493789937456
// 4.555563347820309
// 4.555517475527901
// 4.555547727376273
// 4.555527776815261
// 4.555540933824255
// 4.555532257016376Во втором - 9:
res1: Double = 4.555536206185039
// 6.5
// 5.095215099176933
// 4.668760681281611
// 4.57585730576714
// 4.559030116711325
// 4.55613168520593
// 4.555637206157649
// 4.55555298754564
// 4.555538647701617
// 4.555536206185039Упражнение 1.37
а. Бесконечная цепная дробь (\(continued fraction\)) есть выражение вида \(f = N_{1} / (D_{1} + N_{2} / (D_{2} + N_{3} /(D_{3} + ...)))\) В качестве примера можно показать, что расширение бесконечной цепной дроби при всех \(N_{i}\) и \(D_{i}\), равных \(1\), дает \(\frac{1}{\varphi}\), где \(\varphi\) — золотое сечение (описанное в разделе 1.2.2). Один из способов вычислить цепную дробь состоит в том, чтобы после заданного количества термов оборвать вычисление. Такой обрыв — так называемая конечная цепная дробь (\(finite continued fraction\)) из \(k\) элементов, — имеет вид \(f = N_{1} / (D_{1} + N_{2} / (D_{2} + N_{3} / (D_{3} + ... + N_{k} / D_{k})))\). Предположим, что \(n\) и \(d\) — процедуры одного аргумента (номера элемента \(i\)), возвращающие \(N_{i}\) и \(D_{i}\) элементов цепной дроби. Определите процедуру \(cont-frac\) так, чтобы вычисление \((cont-frac n d k)\) давало значение \(k\)-элементной конечной цепной дроби. Проверьте свою процедуру, вычисляя приближения к \(\frac{1}{\varphi}\) с помощью
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)для последовательных значений \(k\).
Насколько большим пришлось сделать \(k\), чтобы получить приближение, верное с точностью 4 цифры после запятой?
б. Если Ваша процедура \(cont-frac\) порождает рекурсивный процесс, напишите вариант, который порождает итеративный процесс. Если она порождает итеративный процесс, напишите вариант, порождающий рекурсивный процесс.
Для k == 11 точность составляет 4 знака.
Решение на Scala:
Рекурсивный процесс:
def contFracRec(n: Int => Double, d: Int => Double, k: Int): Double =
def loop(i: Int): Double =
if i == k then n(i) / d(i)
else n(i) / (d(i) + loop(i + 1))
loop(1)
contFracRec(_ => 1.0, _ => 1.0, 11)
// res51: Double = 0.6180555555555556Итеративный процесс:
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
def loop(i: Int, result: Double): Double =
if i == 0 then result
else loop(i - 1, n(i) / (d(i) + result))
loop(k, 0.0)
contFracIter(_ => 1.0, _ => 1.0, 11)
// res53: Double = 0.6180555555555556Упражнение 1.38
В 1737 году швейцарский математик Леонард Эйлер опубликовал статью De functionibus Continuis, которая содержала расширение цепной дроби для
e−2, гдеe— основание натуральных логарифмов. В этой дроби все \(N_{i}\) равны1, а \(D_{i}\) последовательно равны1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...Напишите программу, использующую Вашу процедуру
cont-fracиз упражнения 1.37 для вычисленияeна основании формулы Эйлера
Решение на Scala:
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
def loop(i: Int, result: Double): Double =
if i == 0 then result
else loop(i - 1, n(i) / (d(i) + result))
loop(k, 0.0)
val n: Int => Double = _ => 1.0
val d: Int => Double = i =>
if i % 3 == 2 then (i / 3 + 1) * 2
else 1.0
contFracIter(n, d, 1000)
// res55: Double = 0.7182818284590453Упражнение 1.39
Представление тангенса в виде цепной дроби было опубликовано в 1770 году немецким математиком Й.Х. Ламбертом:
tg x = x / (1 − x² / (3 − x² / (5 − ...)))где
xдан в радианах.Определите процедуру
(tan-cf x k), которая вычисляет приближение к тангенсу на основе формулы Ламберта.Kуказывает количество термов, которые требуется вычислить, как в упражнении 1.37.
Решение на Scala:
def contFracIter(n: Int => Double, d: Int => Double, k: Int): Double =
def loop(i: Int, result: Double): Double =
if i == 0 then result
else loop(i - 1, n(i) / (d(i) + result))
loop(k, 0.0)
def n(x: Double)(i: Int): Double =
if i == 1 then x
else -x * x
val d: Int => Double = i => 2 * (i - 1) + 1
def tanCf(x: Double, k: Int): Double =
contFracIter(n(x), d, k)
tanCf(1.0, 100)
// res57: Double = 1.5574077246549021.3.4. Процедуры как возвращаемые значения
Метод Ньютона описан в соответствующем разделе
В общем случае языки программирования накладывают ограничения на способы, с помощью которых можно манипулировать элементами вычисления. Говорят, что элементы, на которые накладывается наименьшее число ограничений, имеют статус элементов вычисления первого класса (first-class) или полноправных. Вот некоторые из их «прав и привилегий»:
- Их можно называть с помощью переменных.
- Их можно передавать в процедуры в качестве аргументов.
- Их можно возвращать из процедур в виде результата.
- Их можно включать в структуры данных.
Упражнение 1.40
Определите процедуруcubic, которую можно было бы использовать совместно с процедуройnewtons-methodв выражениях вида(newtons-method (cubic a b c) 1)для приближенного вычисления нулей кубических уравнений \(x^{3} + ax^{2} + bx + c\).
Решение на Scala:
def square(x: Double): Double = x * x
def cube(x: Double): Double = x * x * x
def cubic(a: Double, b: Double, c: Double): Double => Double = x =>
cube(x) + a * square(x) + b * x + cУпражнение 1.41
Определите процедуру double, которая принимает как аргумент процедуру с одним аргументом и возвращает процедуру, которая применяет исходную процедуру дважды. Например, если процедура inc добавляет к своему аргументу 1, то (double inc) должна быть процедурой, которая добавляет 2.
Скажите, какое значение возвращает (((double (double double)) inc) 5)
Решение на Scala:
val inc: Int => Int = _ + 1
def double[T](f: T => T): T => T = x => f(f(x))
// (((double (double double)) inc) 5)
val f: (Int => Int) => (Int => Int) = double(double(double))
f(inc)(5) // 21Упражнение 1.42
Пусть f и g — две одноаргументные функции. По определению, композиция (composition) f и g есть функция x → f(g(x)). Определите процедуру compose которая реализует композицию. Например, если inc — процедура, добавляющая к своему аргументу 1,
((compose square inc) 6) 49
Решение на Scala:
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))
val square: Int => Int = x => x * x
val inc: Int => Int = x => x + 1
compose(square, inc)(6) // 49Упражнение 1.43
Если
fесть численная функция, аn— положительное целое число, то мы можем построитьn-кратное применениеf, которое определяется как функция, значение которой в точкеxравноf(f(... (f(x)) ...)). Например, еслиfесть функцияx → x + 1, тоn-кратным применениемfбудет функцияx → x + n. Еслиfесть операция возведения в квадрат, тоn-кратное применениеfесть функция, которая возводит свой аргумент в \(2^{n}\)-ю степень.Напишите процедуру, которая принимает в качестве ввода процедуру, вычисляющую
f, и положительное целоеn, и возвращает процедуру, вычисляющуюn-кратное применениеf.Требуется, чтобы Вашу процедуру можно было использовать в таких контекстах:
((repeated square 2) 5) 625Подсказка: может оказаться удобно использовать
composeиз упражнения 1.42
Решение на Scala:
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))
def repeated[A](f: A => A, n: Int): A => A =
if n == 1 then f
else repeated(compose(f, f), n - 1)
val square: Int => Int = x => x * x
repeated(square, 2)(5) // 625Упражнение 1.44
Идея сглаживания (smoothing a function) играет важную роль в обработке сигналов. Если
f— функция, аdx— некоторое малое число, то сглаженная версияfесть функция, значение которой в точкеxесть среднее междуf(x − dx),f(x)иf(x + dx). Напишите процедуруsmooth, которая в качестве ввода принимает процедуру, вычисляющуюf, и возвращает процедуру, вычисляющую сглаженную версиюf.Иногда бывает удобно проводить повторное сглаживание (то есть сглаживать сглаженную функцию и т.д.), получая
n-кратно сглаженную функцию (n-fold smoothed function). Покажите, как породитьn-кратно сглаженную функцию с помощьюsmoothиrepeatedиз упражнения 1.43.
Решение на Scala:
val dx: Double = 1e-6
def smooth(f: Double => Double): Double => Double =
x => (f(x - dx) + f(x) + f(x + dx)) / 3
def nFoldSmoothedFunction(f: Double => Double, n: Int): Double => Double =
repeated(smooth, n)(f)Упражнение 1.45
В разделе 1.3.3 мы видели, что попытка вычисления квадратных корней путем наивного поиска неподвижной точки \(y → \frac{x}{y}\) не сходится, и что это можно исправить путем торможения усреднением. Тот же самый метод работает для нахождения кубического корня как неподвижной точки \(y → \frac{x}{y^{2}}\), заторможенной усреднением. К сожалению, этот процесс не работает для корней четвертой степени — однажды примененного торможения усреднением недостаточно, чтобы заставить сходиться процесс поиска неподвижной точки \(y → \frac{x}{y^{3}}\). С другой стороны, если мы применим торможение усреднением дважды (т.е. применим торможение усреднением к результату торможения усреднением от \(y → \frac{x}{y^{3}}\)), то поиск неподвижной точки начнет сходиться. Проделайте эксперименты, чтобы понять, сколько торможений усреднением нужно, чтобы вычислить кореньn-ой степени как неподвижную точку на основе многократного торможения усреднением функции \(y → \frac{x}{y^{n-1}}\). Используя свои результаты для написания простой процедуры вычисления корнейn-ой степени с помощью процедурfixed-point,average-dampиrepeatedиз упражнения 1.43. Считайте, что все арифметические операции, какие Вам понадобятся, присутствуют в языке как примитивы.
Судя по наблюдениям, для вычисления корней n-ой степени достаточно log(n) + 1 торможений.
Решение на Scala:
def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))
def repeated[A](f: A => A, n: Int): A => A =
if n == 1 then f
else repeated(compose(f, f), n - 1)
def average(a: Double, b: Double): Double = (a + b) / 2
def averageDamp(f: Double => Double): Double => Double =
x => average(x, f(x))
val tolerance = 1e-5
def fixedPoint(f: Double => Double, firstGuess: Double): Double =
def doesCloseEnough(a: Double, b: Double): Boolean =
math.abs(a - b) < tolerance
def tryGuess(guess: Double): Double =
val next = f(guess)
if doesCloseEnough(next, guess) then next
else tryGuess(next)
tryGuess(firstGuess)
def nFoldAverageFunction(f: Double => Double, n: Int): Double => Double =
repeated(averageDamp, n)(f)
def nRoot(x: Double, n: Int): Double =
val f: Double => Double = y => (x / math.pow(y, n - 1))
fixedPoint(nFoldAverageFunction(f, math.log(n).toInt + 1), 1.0)
nRoot(math.pow(2, 100), 100)
// res66: Double = 2.0079006560360497Упражнение 1.46
Некоторые из вычислительных методов, описанных в этой главе, являются примерами чрезвычайно общей вычислительной стратегии, называемой пошаговое улучшение (iterative improvement). Пошаговое улучшение состоит в следующем: чтобы что-то вычислить, нужно взять какое-то начальное значение, проверить, достаточно ли оно хорошо, чтобы служить ответом, и если нет, то улучшить это значение и продолжить процесс с новым значением.
Напишите процедуру
iterative-improve, которая принимает в качестве аргументов две процедуры: проверку, достаточно ли хорошо значение, и метод улучшения значения.Iterative-improveдолжна возвращать процедуру, которая принимает начальное значение в качестве аргумента и улучшает его, пока оно не станет достаточно хорошим.Перепишите процедуру
sqrtиз раздела 1.1.7 и процедуруfixed-pointиз раздела 1.3.3 в терминахiterative-improve.
Решение на Scala:
def iterativeImprove(
doesCloseEnough: (Double, Double) => Boolean,
next: Double => Double
): Double => Double = firstGuess =>
def tryGuess(guess: Double): Double =
val nextGuess = next(guess)
if doesCloseEnough(nextGuess, guess) then nextGuess
else tryGuess(nextGuess)
tryGuess(firstGuess)
def doesCloseEnough(a: Double, b: Double): Boolean =
math.abs(a - b) < 1e-5
def average(x: Double, y: Double): Double = (x + y) / 2
def sqrt(x: Double): Double =
iterativeImprove(doesCloseEnough, y => average(y, x / y))(1.0)
def fixedPoint(f: Double => Double, firstGuess: Double): Double =
iterativeImprove(doesCloseEnough, f)(firstGuess)Ссылки: