Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 6
Текст из файла (страница 6)
41671.41672/1.4167=1.4118(1.4168+1.4118)/2=1.41421.4142Основной процедурой будет процедура sqrt-iter, определенная отаргументов guess (приближение) и х (число, квадратный корень которогоона находит). Если текущее приближение является достаточно хорошим,то процесс вычисления заканчивается и результатом становится текущеезначение guess, иначе вычисление продолжается с улучшеннымзначением guess.(define {sqrt-iter guess x)( i f (good-enough? guess x) guess (sqrtiter (improve guess x) x))}Улучшение приближения получаем как среднее значение x/guess и guess.(define(improve guess x)(average guess(/ x guess)))где(define (average x y)(/ (+ x y) 2))Необходимо также определить допустимую погрешность вычисления,предикат good-enough?. Заметим, что имена предикатов, как правило,заканчиваются знаком «?».
Для первого варианта решения задачидопустимую погрешность можно определить как \guess2 - х\ < eps.(define (good-enough? guess x)(< (abs (- (square guess) x)) 0 . 0 0 1 ) )Однако лучше этот предикат определить как модуль разности значенийguess на предыдущем и текущем шаге. В качестве упражненияпредлагается переопределить этот предикат.Наконец, нужно определить саму процедуру sqrt.
Допустим, что мывсегда будем начинать с приближения 1.(define(sqrt x)(sqrt-iter 1.0 x))После определения всех процедур можно использовать sqrt, как обычнуюпроцедуру.(sqrt 9)(sqrt (+100 37))->->3.0000915541313811.704699917758145(sqrt (+ (sqrt 2)(sqrt 3)))(square (sqrt 1000))-> 1.7739279023207S92-> 1000.000369924366Заметим, что необходимая процедура полностью определена, несмотря нато, что не были определены никакие средства языка поддерживающиеитерационный процесс (например, операторы цикла или перехода).Процедура sqrt-iter не использует никаких специальных конструкцийкроме вызова процедуры.Рассмотрим наиболее важные моменты построения процедуры sqrt.Задача вычисления квадратного корня разбита на несколько подзадач, аименно: достаточно ли хорошее приближение найдено, как улучшитьприближение и т.д.
Каждая их подзадач реализуется отдельнойпроцедурой. Важность стратегии декомпозиции состоит не только вразбиении задачи на подзадачи. Существенно, что каждая из процедурвыполняет независимую задачу и может быть использована и в другихпроцедурах. Например, при определении процедуры good-enough? былаиспользована процедура square. При этом процедура рассматривалась как«черный ящик». То есть детали реализации процедуры скрыты, авозможности использования определяются ее интерфейсом.
Прииспользовании процедуры интересует то, что она делает, а не то, как. Вэтом смысле square представляет собой так называемую процедурнуюабстракцию.Упражнения5. Почему необходима специальная форма для if выражения? Почему егонельзя определить как обычную процедуру с помощью cor.d?(define (new-if predicate then-clause else-clause)(cond (predicate then-clause) (else elseclause)))Примеры(new-if (= 2 3) 0 5}(new-if (= 1 1) 0 5)->->50дают правильный ответ.
Что произойдет, если использовать new-if впроцедуре sqrt-iter? Объясните.(define (sqrt-iter guess x!(new-if (good-enough? guess x) guess (sqrtiter (improve guess x) x)))326. Переопределите предикат good-enough? чтобы он приводил кправильному вычислению корня для больших и малых чисел.7. Метод Ньютона для вычисления кубического корня основан на том,что, имея приближенное значение у кубического корня х, уточнениеможно получить по формуле (х /у2 + 2 у) / 3. Используя приведеннуюформулу, определите процедуру cube-root, которая вычисляеткубический корень.Внутренние определения и блочная структураИмена формальных параметров локализованы в теле процедуры.
Каквидно из рассмотренного примера, для реализации процедуры squareпотребовалось определить несколько вспомогательных процедур. Воизбежание возможной коллизии имен при разработке больших библиотекпринято локализовать вспомогательные процедуры внутри основной.Таким образом, можно переписать определение процедуры sqrt.(define (average х у) (/ ( + х у) 2 ) )(define (sqrt x)(define (good-enough? guess x)(< (abs (- square guess) x)) 0 . 0 0 1 ) )(define (improve guess x)(average guess (/ x guess)))(define (sqrt-iter guess x)(if (good-enough? guess x)guess(sqrt-iter (improve guess x) x)))(sqrt-iter 1.0 x) )Такая структура процедур называется блочной и является в основномправильным путем решения проблем.
Но его можно ещеусовершенствовать. Так как переменная х является локальной (связанной) вопределении процедуры sqrt, и процедуры good-enough?, improve иsquare-iter находятся в области видимости х, то нет необходимостипередавать х в качестве параметра каждой из процедур. Имя х можноиспользовать как глобальную (свободную) переменную во всех вложенныхопределениях. Такой подход называется лексическим связыванием.(define (sqrt x)(define (good-enough? guess)(< (abs (- square guess) x)) 0.001))(define (improve guess)(average guess (/ x guess)))(define (sqrt-iter guess)(if (good-enough? guess)guess(sqrt-iter (improve guess))))(sqrt-iter 1.0))Идея блочной структуры возникла в языке программирования Algol-60.Она поддерживается во многих языках программирования и являетсяодним из основных методов разработки больших программ.Процедуры и процессы, которые они порождаютПроцедура является шаблоном локального развития вычислительногопроцесса.
Она определяет, как текущее состояние процесса получается наоснове предыдущего состояния. Опишем наиболее типичные шаблоныпроцессов, порождаемых процедурами в Scheme.Линейная рекурсия и итерацияРассмотрим задачу вычисления факториала натурального числа n! = п (п 1) (п - 2) ... 3 2 1. Существует много различных способов вычисленияфакториала. Например, можно представить п! как п (п - 1)!. Такимобразом, добавив утверждение, что 1! = 1, можно получить следующееопределение процедуры:(define (factorial n)(if (= n 1) 1 (* n (factorial (- n 1 ) ) ) ) )Для того чтобы представить процесс, который выполняется привычислении значения (factorial 6) можно использовать одну измоделей подстановок, описанных выше. Например,(factorial 6)(* 6 (factorial 5))(* б (* 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 1))))) )(* 6 (* 5 (* 4 (* 3 2)))))(* 6 (* 5 (* 4 6))))(* 6 (* 5 24»(* 6 120)720Такой процесс представляет собой линейную рекурсиюВычисление факториала можно также описать как умножение 1 на 2 на 3 ит.д.
до п. При этом необходимо накапливать произведение и изменять34текущий счетчик от 1 до п. Получаем следующие правила для вычисленияфакториала:произведениесчетчик<- счетчик * произведение<- счетчик + 1Тогда факториал n! - это значение произведения, полученное при значениисчетчика, превысившего п.(define (factorial n)(define (iter product counter) (if(> counter n) product(iter (* counter product) (+ counter I ) ) ) )(iter l 1 ) )Вычислительный процесс, соответствующий данной процедуре, можнопредставить следующим образом.(factorial 6)(iter1 1)(iter1 2)(iter2 3)(iter6 4)(iter 24 5)(iter 120 6)(iter 720 7)720Такой процесс является линейным и итеративным.Сравним первый и второй процессы. Оба вычисляют одну и ту жематематическую функцию в одной и той же области определения. Каждыйвыполняет количество шагов, пропорциональное п. Оба процессавыполняют одну и ту же последовательность умножений и получают однуи ту же последовательность промежуточных результатов.
Рассмотримподробнее первый процесс. В нем происходит накопление цепочкиотложенных операций (в рассмотренном примере отложенныхумножений). Сжатие цепочки происходит, когда эти операции начинаютвыполняться. Тип процесса, который порождает цепочку отложенныхопераций, называется рекурсивным процессом. Выполнение процессатребует, чтобы интерпретатор хранил трассу операций, которые должныбудут выполниться позже. Для вычисления л/ длина цепочки отложенныхумножений, которую требуется хранить, пропорциональна я, как иколичество шагов вычисления. Такой процесс называется линейнымрекурсивным процессом.35На каждом шаге второго процесса нам необходимо хранить текущиезначения счетчика, произведения и конечного значения счетчика.
Такойпроцесс называем итеративным. В общем случае, итеративнымназывается процесс, состояния которого могут быть описаныфиксированным количеством переменных состояния, правилами переходаиз одного состояния в другое и правилом окончания процесса. Длявычисления n! количество шагов пропорционально я. Такой процессназывается линейным итеративным процессом.В итеративном процессе, переменные содержат полное описаниесостояния процесса в каждой точке.
Если мы прервем вычисление междусостояниями, то для возобновления вычисления интерпретаторунеобходимо задать значения трех переменных. В рекурсивном процессеприсутствует дополнительная «скрытая» информация, используемаяинтерпретатором, и не содержащаяся в переменных программы, котораяопределяет «где находится процесс» при выполнении цепочки отложенныхопераций. Чем длиннее цепочка, тем больше требуется информации.Сравнивая итерацию и рекурсию, нельзя путать рекурсивный процесс ирекурсивную процедуру. Когда мы говорим о рекурсивной процедуре, тоимеем в виду факт синтаксиса, обращение процедуры к самой себе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
