Санкт-Петербургский государственный технологический институт
(технический университет)
Кафедра: систем автоматизирован- Факультет: 4
ного проектирования и управления Курс: 2
Группа: 4803
Учебная дисциплина: теория алгоритмов
Отчет по лабораторным работам
Выполнила:
Карцева А.Ю.
Проверил:
Плонский В.Ю.
Санкт-Петербург
2012 г.
1.
Определите результат каждого выражения:
(define a 3) //a=3
(define b (+ a 1)) //b=4
(+ a b (* a b)) // 19
(= a b) // false
(if (and (> b a) (< b (* a b))) // 4
b
a)
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25)) //16
(+ 2 (if (> b a) b a)) // 6
(* (cond ((> a b) a) // 16
((< a b) b)
(else -1))
(+ a 1))
2.
Переведите выражение в префиксную форму и вычислите его значение:
Текст программы:
(/ (+ 5 4 (- 2 (- 3 (+ 6 4/5)))) (* 3 (- 6 2) (- 2 7)))
Ответ:
-37/150
3.
Определите процедуру, которая принимает в качестве аргументов три числа и возвращает сумму квадратов двух больших из них.
Текст программы:
(define (square a b c) (cond ((< c (and b a)) (+ (* a a) (* b b)))
((< a (and b c)) (+ (* b b) (* c c)))
((< b (and c a)) (+ (* a a) (* c c)))))
Тестирование:
x=3 у=9 z= 8
ответ: 145
x=1 y= 3 z=5
ответ: 34
4.
Определите процедуру, которая принимает в качестве аргументов два числа и возвращает сумму первого и абсолютное значение второго.
Замечание: отдельная процедура вычисления модуля (abs) не должна использоваться.
Замечание: используйте свойство модели вычисления, согласно которому оператор может быть составным выражением.
Текст программы:
#lang racket
(define (sum x y) (+ x (cond ((>= y 0) y) ((< y 0) (- y)))))
Тестирование:
x=6 y=-9
ответ: 15
x=0 y=-155
ответ:155
5.
Процедура good-enough? при вычислении вычисления квадратных корней, неэффективна для поиска квадратных корней очень маленьких чисел. Альтернативный подход состоит в том, чтобы следить, как от одной итерации к другой изменяется guess, и остановиться, когда изменение оказывается небольшой долей значения приближения. Разработайте процедуру вычисления квадратного корня, которая использует такой вариант проверки на завершение.
Текст программы:
#lang racket
(define (sqrt x)
(sqrt_iter 1.0 x))
(define (sqrt_iter quess x)
(if (goodenough? quess x)
(improve quess x)
(sqrt_iter (improve quess x) x)))
(define(improve quess x)
(average quess (/ x quess)))
(define (average x y)
(/ (+ x y) 2))
(define (goodenough? quess x)
(< (abs(- (improve quess x) quess))
0.00001))
(define (abs x)
(cond ((< x 0) (- x))
(else x)))
Тестирование:
| X | Погрешность | Результат |
| 0.001 | 0.001 | 0.03162278245070105 |
| 0.001 | 0.01 | 0.03274526934448864 |
| 0.001 | 0.1 | 0.06772532736082602 |
| 0.1 | 0.001 | 0.31622776651756745 |
| 0.1 | 0.01 | 0.316245562280389 |
6.
Перепишите определение процедуры расчета факториала new-factorial (использующую линейно итеративный процесс), чтобы в ней применялась блочная структура.
Текст программы:
#lang racket
(define (new-factorial n)
(define (fact_iter prod counter max_count)
(if(> counter max_count)
prod
(fact_iter(* counter prod) (+ counter 1)
max_count)))
(fact_iter 1 1 n))
Тестирование:
N=8
Ответ: 40320
N=4
Ответ:120
7.
Функция Аккермана определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:
Таблица значений функции Аккермана для различных параметров n и m:
| n \ m | m | ||||||
| hyper(2, m, 3) - 3 | |||||||
| hyper(2, m, 4) - 3 | ||||||
| 265536 − 3 | 
| hyper(2, m, 5) - 3 | |||||
| 
| hyper(2, m, 6) - 3 | |||||
| A(4, A(5, 3)) | hyper(2, m, 7) - 3 | |||||
| A(4, A(5, 4)) | hyper(2, m, 8) - 3 | |||||
| n | n + 1 | n + 2 | 2n + 3 | 2n + 3 − 3 | 
| 
| hyper(2, m, n+3) - 3 |
Создайте процедуру для расчета функции Аккермана. Последовательно увеличивая значение m, определите (где это возможно) максимальное значение n, при котором время работы процедуры не превышает одной минуты для применяемой вычислительной системы. Результаты (m, n, время работы, значение) сведите в таблицу.
Текст программы:
#lang racket
(define (AFunc m n)
(cond
((= m 0) (+ n 1))
((and (> m 0) (= n 0)) (AFunc (- m 1) 1))
((and (> m 0) (> n 0)) (AFunc (- m 1) (AFunc m (- n 1))))))
Тестирование:
| m | n | t | Результат |
8.
Приведенная на рисунке схема называется треугольником Паскаля.
Все числа по краям треугольника равны 1, а каждое число внутри треугольника равно сумме двух чисел над ним. Элементы треугольника Паскаля называются биномиальными коэффициентами, поскольку n -й ряд состоит из коэффициентов термов при разложении (x + y)n.
Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощью рекурсивного процесса.
Текст программы:
#lang racket
(define (binc n k)
(cond
((< n 0) (print "Oшибка! n должен быть не меньше 0"))
((< k 0) (print "Oшибка! k должен быть не меньше 0"))
((= k 0) 1)
((= k n) 1)
(else (+ (binc (- n 1) (- k 1)) (binc (- n 1) k)))
)
)
Тестирование.
| n | k | binc |
9.
Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением sin x ≈x при малых x и употребить тригонометрическое тождество для уменьшения значения аргумента sin:
В задаче предполагается, что угол достаточно мал, если он не больше 0.1 радиана.
Напишите процедуру sine, вычисляющую синус угла указанным способом (при необходимости определите вспомогательные процедуры). Какой порядок роста в терминах количества шагов для процесса, порождаемого процедурой sine при вычислении sine(a).
Текст программы:
(define (cube x) (* x x x))
(define (sine x)
(if (> x 0.1)
(print "Oшибка х должен быть не более 0.1")
(- x (* 4(cube (/ x 3))))))
Тестирование:
| x | Результат | |
| 0.1 | 0.09985185185185186 | |
| 0.05 | 0.04998148148148148 | |
| 0.01 | 0.009999851851851852 | |
| 0.2 | "Oшибка х должен быть не более 0.1" | |
10.
Используя последовательное возведение в квадрат можно сократить число шагов для вычисления степени числа. Например, b8 можно вычислить за три умножения:
b2 = b ・ b
b4 = b2 ・ b2
b8 = b4 ・ b4
Этот метод хорошо работает для степеней, которые сами являются степенями двойки. В общем случае при вычислении степеней можно получить преимущество от последовательного возведения в квадрат, если воспользуемся правилом:
bn = (bn/2)2, если n четно;
bn = b・bn−1, если n нечетно.
Используя предикат, проверяющий целое число на четность (even?), реализуйте этот метод с помощью процедуры. Укажите степень роста процесса, порождаемого процедурой.
Текст программы:
#lang racket
(define (degree b n)
(if (> n 1) (if (even? n)
(sqrt (degree b (/ n 2)))
(* b (degree b (- n 1))))
(if (= n 1) b 1)))
(define (even? n)
(cond ((> (cos (* n pi)) 0) #t)
((< (cos (* n pi)) 0)#f)))
(define (sqrt b) (* b b))
Тестирование.
> (degree 5 5)
11.
Используя процедуру sum, выражающую общую схему суммирования последовательности, вычислите приближение к числу π.
Текст программы:
#lang racket
(define (sum_pi a b)
(if (> a b)
(+ (/ 1.0 (* a (+ a 2))) (sum_pi (+ a 4) b))))
(define pi_ (* 8(sum_pi 1 10000)))
Ответ: 3.141392653591793
12.
Правило Симпсона — более точный метод численного интегрирования, чем представленный выше.
С помощью правила Симпсона интеграл функции f между a и b приближенно вычисляется в виде
где h = (b − a)/n, для какого-то четного целого числа n, а yk = f(a + kh). Увеличение n повышает точность приближенного вычисления. Определите процедуру, которая принимает в качестве аргументов f, a, b и n, и возвращает значение интеграла, вычисленное по правилу Симпсона. С помощью этой процедуры проинтегрируйте cube между 0 и 1 (для вариантов n = 100 и n = 1000) и сравните результаты с процедурой integral, разработанной Вами ранее.
Текст программы:
#lang racket
(define (integral f a b n)
(define h (/ (- b a) n))
(define (add_h x) (+ x h h))
(define (sum f a next b)
(if (= a b)
(+ (f a) (* 4 (f (+ a h))) (f (next a)) (sum f (next a) next b))))
(* (sum f a add_h b) (/ h 3)))
(define (cube x)
(* x x x))
Тестирование:
a=0 b=1 n=100
Ответ: ¼
a=0 b=1 n=1000
Ответ: ¼
Результаты Integral, разработанной ранее:
a= 0 b=1 n=0.01
Ответ: 0.24998750000000042
a= 0 b= 1 n=0.001
Ответ: 0.249999875000001
13.
Определена процедура:
(define (f g k) (g k))
Тогда вычисление
(f sqrt 2)
даст результат: 1.4142135623730951
Замечание: в этом вызове используется встроенная процедура sqrt.
Не определяя процедуру расчета площади круга, напишите вызов процедуры f, который вычислит площадь круга с радиусом 5.
Замечание: в этом задании необходимо использовать особую форму lambda.
Программа:
> (f (lambda (R) (* pi R R)) 5)
78.53981633974483
14:
Основываясь на введенных Вами селекторах numer, denom и конструкторе make-rat, добавьте в виде процедур арифметические операции над рациональными числами: вычитание (sub-rat), деление (div-rat) и проверку на равенство (equal-rat?). Используя введенную ранее процедуру расчета наибольшего общего делителя gcd, модифицируйте конструктор make-rat таким образом, чтобы он сокращал числитель и знаменатель.
Текст программы:
#lang racket
(define (make-rat n d)
(cons (/ n (gcd n d)) (/ d (gcd n d))))
(define (numer x)
(car x))
(define (denom x)
(cdr x))
(define (gcd a b)
(if (= b 0) a
(gcd b (remainder a b))))
(define (sub-rat a b)
(make-rat (- (* (numer a)(denom b)) (* (numer b)(denom a))) (* (denom a)(denom b))))
(define (div-rat a b)
(make-rat (* (numer a)(denom b)) (* (numer b)(denom a))))
(define (equal-rat? a b)
(if (and (= (numer(make-rat (numer a)(denom a)))(numer(make-rat (numer b)(denom b))))
(= (denom(make-rat (numer a)(denom a)))(denom(make-rat (numer b)(denom b)))))
(display "true")
(display "false")))
(define (print-rat x)
(display(numer x))
(display "/")
(display(denom x)))
Тестирование:
(print-rat(sub-rat (make-rat 3 7) (make-rat 4 5)))
Ответ: -13/35
15.
Определены x и y как два списка:
(define x (list 1 2 3))
(define y (list 4 5 6))
Определите и объясните результат работы интерпретатора в ответ на следующие выражения:
(cons x y)
(list x y)
Программа:
(cons x y)// '((1 2 3) 4 5 6)
(list x y) // '((1 2 3) (4 5 6))
Функция cons cтроит новый список из переданных ей в качестве аргументов головы и хвоста:
(Cons голова хвост) – Таким образом, в нашем примере (1 2 3) голова, а 4 5 6 –хвост;
List – функция, которая возвращает в качестве своего значения список из значений аргументов.
16.
Определите процедуру last-pair, которая возвращает список, содержащий только последний элемент данного (непустого) списка. Пример вызова процедуры last-pair:
(last-pair (list 23 72 149 34))
Результат: (34)
Текст программы:
#lang racket
(define (last-pair a)
(if (null? (cdr a))
a
(last-pair(cdr a))))
Тестирование:
(last-pair (list 1 2 3 4))
Ответ: '(4)
17.
Не пользуясь системной процедурой reverse, определите процедуру reverse-new, которая принимает список как аргумент и возвращает список, состоящий из тех же элементов в обратном порядке. Пример вызова процедуры reverse-new:
(reverse-new (list 1 4 9 16 25))
Результат: (25 16 9 4 1)
Программа:
(define (reverse-new l)
(let next ([r null][l l])
(if (null? l)
r
(next (cons (car l) r) (cdr l)))))
Тестирование:
| (reverse-new (list 'a 'b 'c 'd 'e) | '(e d c b a) |
| (reverse-new (list 1 2 3 4 5) | (5 4 3 2 1) |
| (reverse-new (list 44 67 9 10) | (10 9 67 44) |
18.
Вычислите выражение:
(list 1 (list 2 (list 3 4)))
Изобразите результат в виде стрелочной диаграммы, а также его интерпретацию в виде дерева.
Программа.
> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))
Список в виде стрелочной диаграммы.
Результат в виде дерева.
19.
Укажите комбинации car и cdr, которые извлекают 7 из следующих списков:
(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))
Программа:
(define z(list 1 3 (list 5 7) 9))
(define z(list (list 7)))
(define z(list 1 (list 2 (list 3 (list 4 (list 5 (list 6 (list 7))))))))
Тестирование:
(car (cdr (car (cddr z))))
(car (car z))
(car (car(cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr z)))))))))))))
20.
Вычислите и объясните значения следующих выражений:
(list 'a 'b 'c)
(list (list 'sapr))
(cdr '((x1 x2) (y1 y2)))
(cadr '((x1 x2) (y1 y2)))
(car ''abracadabra)
(cdr ''abracadabra)
| (list 'a 'b 'c) | '(a b c) Значением выражения является список, содержащий константы a, b, c. |
| (list (list 'sapr)) | '((sapr)) Значение выражения является список, содержащий вложенный список, содержащий константу sapr. |
| (cdr '((x1 x2) (y1 y2))) | '((y1 y2)) Функция cdr возвращает второй элемент точечной пары (или же хвост списка). |
| (cadr '((x1 x2) (y1 y2))) | '(y1 y2) Функция cadr является комбинацией функций car и cdr, сначала вычисляет второй элемент точечной пары, затем возвращает первый элемент в полученном списке. |
| (car ''abracadabra) | 'quote Функция car возвращает первый элемент списка, в данном случае quote. |
| (cdr ''abracadabra) | '(abracadabra) Функция cdr возвращает хвост списка, в данном случае abracadabra. |