ФИЛП практика (Мет пособие)

21

(BITLENGTH 7) --> 3 (BITLENGTH 8) --> 4

25) Функция PRECISION [n]. Если <n> - положительное целое, (PRECISION n) принимает <n> за значение точности и возвращает предыдущее значение точности. Если <n> равен нулю, (PRECISION n) принимает значение точности за бесконечность и возвращает предыдущее значение. Если <n> отсутствует или не является ни нулем, ни положительным целым, PRECISION n) возвращает текущее значение точности без его изменения.

Если значение точности принято равным положительному целому <n>, то новое дробное число, сгенерированное числовыми функциями, автоматически округляется, если для размещения меньшей из величин его числителя и знаменателя требуется больше, чем <n> слов памяти (слово памяти состоит из 16 бит). Такое дробное число заменяется аппроксимацией, причем такой, которая требует для размещения наименьшей из величин числителя и знаменателя не более <n> слов.

Точность плавающего слеша, равная 1, соответствует единичной точности плавающей точки; точность плавающего слеша, равная 2, соответствует двойной точности плавающей точки, и т.д. Точность плавающего слеша, равная <n>, также обеспечивает почти 10*n десятичных знаков точности. Первоначальное значение точности предполагается равным 1.

(PRECISION 0) --> 1 (PRECISION 5) --> 0 (PRECISION) --> 5 (PRECISION 1) --> 5

26) Функция UNDERFLOW [n]. Часто в процессе вычислений с аппроксимацией требуются такие числа, которые по абсолютной величине меньше, чем некоторое число с плавающей точкой, стремящееся к нулю

(ситуация "underflow"). Если <n> - положительное целое, (UNDERFLOW n)

полагает значение, на котором возникает ситуация "underflow", равным 65536^- n и возвращает предыдущее значение "underflow". Если <n> - ноль, (UNDERFLOW n) предотвращает возникновение "underflow" и возвращает предыдущее значение. Если <n> отсутствует или не является ни 0, ни положительным целым, (UNDERFLOW n) возвращает текущее значение "underflow" без его изменения. Первоначально "underflow" принимается равным

7.

(UNDERFLOW 0) --> 7 (UNDERFLOW 5) --> 0

22

(UNDERFLOW) --> 5 (UNDERFLOW 7) --> 5

Виды рекурсии

СЛОЖНАЯ РЕКУРСИЯ

1.Параллельная рекурсия: (defun f (g … (f …) … (f…)…))

В этом случае тело определения функции f содержит вызов некоторой функции g, аргументом которой являются вызовы функции f.

2.Взаимная рекурсия:

(defun f… (g…)) (defun g… (f…))

Проблема – когда окончить работу. 3. Рекурсия более высокого порядка. (defun f… (f… (f… (f…))))

В ней аргументом рекурсивного вызова f является вызов f.

ПРОСТАЯ РЕКУРСИЯ

П.р. – рекурсивный вызов встречается в некоторой ветви вычислений только 1 раз.

(defun copy(spisok)

(cond ((null spisok) nil)

(t (cons (car spiok) (copy (cdr spisok)))))

Здесь рекурсия распространяется в сторону хвоста списка. (defun member1 (a sp)

(cond ((null sp) nil) ((eql (car sp) a) t)

(t (member1 a (cdr sp)))))

В простом списке заменить все отрицательные числа нулями: (defun repl(list1)

(cond ((null list1) nil)

(t (cons (cond ((minusp (car list1)) 0) (t (car list1))

(repl (cdr list1))))))

Из списка удалить заданный элемент: (defun f1 (lst a)

(cond ((null list) nil)

((eql a (car lst)) (f1 (cdr lst) a))

(t (cons (car lst) (f1 (cdr lst1) a))))

Можно выделить 3 ветви: терминальная, в которой удаляется элемент и формирование результата. Так можно найти глубину рекурсии, но не всегда. Для функции найти и заменить изменится 2ая ветвь:

(defun repl (old new sp)

23

(cond ((null sp) nil)

((eql old (car sp)) (cons new (repl old new (cdr sp))) (t (cons (car sp) (repl old new (cdr sp))))))

ПАРАЛЛЕЛЬНАЯ РЕКУРСИЯ

Рекурсия называется параллельной, если она встречается одновременно в нескольких аргументах функции. Аналогия: идущие друг за другом циклы. Пример: копирование списков на всех уровнях. 3 случая: пустой, атом, произвольный список:

(defun copy (s)

(cond ((null s) nil) ((atom s) s)

(t (cons (copy (car s)) (copy (cdr s))))))

Здесь объединены рекурсивные вызовы для головы и для хвоста. Пример: изменение порядка следования на всех уровнях: (defun revers (sp)

(cond ((null sp) nil) ((atom sp) sp)

((null (cdr sp)) (cons (revers (car sp)) nil))

(t (append (revers (cdr sp)) (cons (revers (car sp)) nil)))

)

)

Данная функция обращает порядок следования головы списка и присоединяет к ней спереди обращенный хвост.

ВЗАИМНАЯ РЕКУРСИЯ

Рекурсия называется взаимной, если несколько функций вызывают друг друга. Пример: реверсирование списка:

(defun rev1 (s)

(cond ((atom s) s)

(t (myrepl s nil))

)

)

(defun myrepl (sx sy) (cond ((null sx) nil)

(t (myrepl (cdr sx) (cons (rev1 (car sx)) sy)))

)

)

24

ВЛОЖЕННЫЕ ЦИКЛЫ

Вложенные циклы организовываются при помощи 2х или более функций, вызов которых применяется в качестве аргумента рекурсивного вызова. Функция сортировки: для начала определим функцию insert, которая вставляет элемент e в упорядоченный по возрастанию список:

(defun Insert (e s)

(cond ((null s) (cons e s))

((< e (car s)) (cons e s))

(t (cons (car s) (Insert e (cdr s))))))

(defun Sort (s)

(cond ((null s) nil)

(t (Insert (car s) (Sort (cdr s))))))

РЕКУРСИЯ ВЫСОКОГО ПОРЯДКА

В зависимости от того, на каком уровне находится рекурсивный вызов, можно определить порядок рекурсии. Ранее рассматривались функции с 0ым порядком.

Пример: приведение списка к одному уровню: (defun one_l (s)

(m_eq s nil)) (defun m_eq (s1 s2)

(cond ((null s1) s2)

((atom s1) (cons s1 s2))

(t (m_eq (car s1) (m_eq (cdr s1) s2)))))

Пример:

(defun reverse2 (s) (cond ((null s) s)

((null (cdr s)) s)

(t (cons (car (reverse2 (cdr s))) (reverse2 (cons (car s) (reverse2 (cdr (reverse2 (cdr s))))))))

)

)

Аргументом cons является рекурсивный вызов, причем аргументом этой функции является reverse2. Образование списка из 5 элементов требуется 149 вызовов, из 15 – 74409. Увеличивается глубина стека.

25

Задания к лабораторным работам по языку программирования ЛИСП

Подгруппа разбивается на 7 или меньше бригад. Каждая бригада должна выполнить по две задачи из каждой секции по 7 задач (по выбору преподавателя). 50-ю задачу выполняют все, каждая бригада пишет свою игру – по выбору студентов.

Задания на использование базовых функций:

1.Удалить первый и последний элемент списка.

2.В простом списке чисел заменить все отрицательные числа нулями.

3.Из простого списка чисел удалить все нулевые элементы

4.Продублировать все вхождения атома X в данный список.

5.Подсчитать число вхождений атома Х в простой список.

6.Реверсировать простой список (без использования дополнительного списка). 7*. Дан простой список чисел, отсортировать в нем все положительные (Пр. (-4

34 -1 0 6 2) Æ (-4 2 3 -1 0 4 6)).

Задания на изучение числовых функций:

8.Выделить первую цифру натурального N.

9.Получить все делители натурального N.

10.Подсчитать число и сумму цифр целого N.

11.Найти все общие делители натуральных M и N.

12.Найти наибольший общий делитель чисел из заданного списка. 13*. Получить все простые числа от N до M.

14.Посчитать сумму арифметической прогрессии с параметрами a0, d, n (a(i)=a(i-1)+d) без использования формулы суммы арифметической прогрессии.

Задания на работу со списками:

15.Даны два списка вида (a1,a2,…) и (b1,b2,…). Получить список (a1,b1,a2,b2…). Если исходные списки разной длины, то остаток более длинного отбросить.

16.Даны натуральные m, n и некоторый простой список. Удалить из списка элементы с номерами с m-го по n-й.

17.Из произвольного списка удалить все элементы, не являющиеся числом

27

38.Найти сумму всех чисел из заданного сложного списка.

39.Найти произведение всех ненулевых чисел из заданного сложного списка.

40.Вычислить среднее арифметическое отрицательных чисел произвольного списка.

41*. Представить целое N в виде суммы квадратов двух целых чисел.

42.Представить целое N в виде суммы квадратов 3-х натуральных чисел.

43.Представить целое N в виде суммы квадратов 4-х натуральных чисел.

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

Задания на закрепление знаний функций Lisp

45.Найти максимальную глубину вложенности произвольного списка.

46.Используя управляющую конструкцию DO, вычислить среднее арифметическое чисел 0.1+0.25+…+15.1.

47.Организовать диалог программы с пользователем.

48.Вычислить статистические характеристики вводимых пользователем чисел.

49.Разработать программу преобразования математических выражений в префиксную форму.

50.Написать игру, которая должна включать в себя диалоговую работу с пользователем, датчик случайных чисел и сохранение статистики в файл.

28

Часть 2

Лабораторная работа №1.

1.Цель работы: Целью работы является изучение системы TurboProlog фирмы Borland, приобретение практических навыков составления, отладки и выполнения простейшей программы в системе программирования Турбо-Пролог.

2.Краткие теоретические сведения.

Объекты данных в Прологе называются термами. Терм может быть: константой, переменной, структурой (составной терм).

Числа в Турбо-Прологе записываются точно так же, как и в других языках программирования.

Константы относятся к одному из 6 стандартных типов данных (доменов):

Переменная - имя, начинающееся с большой (прописной) буквы или знака подчеркивания. Когда значение переменной неважно, то в качестве имени переменной используется знак подчеркивания. Такая переменная называется анонимной.

Структуры (сложные термы) - это объекты, которые состоят из нескольких компонент. Структура записывается с помощью указания ее

29

функтора и компонент. Компоненты заключаются в круглые скобки и разделяются запятыми. Число компонент в структуре называется арностью структуры.

Пример структуры: data_r(12,mart,1962). Здесь data_r – функтор; 12, mart, 1962 – компоненты. Арность приведенной структуры равна трем.

Структура программы.

Программа на Турбо-Прологе состоит из нескольких разделов, каждому из которых предшествует ключевое слово. Типичная структура программы представлена ниже:

/* комментарии */ domains

<описание типов данных> database

<описание предикатов динамической базы данных> predicates

<описание предикатов> clauses

<утверждения> goal

<целевое утверждение> В программе не обязательно наличие всех разделов. Обычно в

программе должны быть, по крайней мере, разделы predicates и clauses.

Раздел Domains.

Существует 4 способа объявления типов данных (доменов):

1.name =d , где name – имена объектов стандартного типа, d – один из типов (char, symbol, integer, real, string)

2.list = element*, где list – список элементов element, element –

элемент, описанный в разделе domains или один из стандартных типов, * - список.

3.num1=f1 (d11, …, d1M); f2 (d21, …, d2N) Тип num1 включает сложные объекты, которые объявляются путем установления функтора и описаний всех входящих в него компонент. collection = book (author, title); record (artist, album, type). Один оператор раздела domains описывает только один уровень дерева; books = book (title, author (name, surname)) – неверно.

4.file = name1; name2; … Используется для обращения к файлам по символическим именам. В разделе domains может быть только один оператор этого типа. Символические имена файлов, если их несколько, задаются в качестве альтернативы.

Раздел Predicates.

Предикат (отношение) в общем случае - это структура вида: prednames(komp1,komp2,...),

где predname - имя предиката,

komp1,... - типы компонентов, описанных в разделе domains или стандартные типы.

30

Например: domains

fio=string

den,god=integer

mes=symbol predicates

anketa(fio,den,mes,god)

Если в предикатах используются только стандартные типы данных, то раздел domains может отсутствовать:

predicates anketa(string,integer,symbol,integer)

Предикат может состоять только из одного имени, напр., predicates

result

Допускается многократное объявление предиката с одним и тем же именем. Альтернатива необязательно должна иметь одинаковое число компонентов.

Раздел Clauses.

В разделе clauses размещаются предложения (утверждения). Предложение представляет собой факт или правило, соответствующее одному из объявленных предикатов.

Факт - простейший вид утверждения, которое устанавливает отношение между объектами. Пример факта:

anketa(“Иванов”,5,august,1950).

Этот факт содержит атом anketa, который является именем предиката, и в скобках после него - список термов, соответствующих компонентам этого предиката. Факт всегда заканчивается точкой. Факты содержат утверждения, которые всегда являются, безусловно, верными.

Правила отражают некую логическую зависимость некого предиката от других предикатов.

Правило состоит из заголовка и тела, соединенных символом :- (if). Заголовок правила – некий предикат, возможно содержащий переменные. Тело правила (хвостовые цели) – список предикатов, разделённых запятыми. Заголовок if подцель1, подцель2, …, подцельN. Правило в общем случае гласит, что предикат, составляющий заголовок правила, будет истинным, если истинны все подцели, входящие в его тело, т.е. “,” – имеет смысл конъюнкций. И заголовок, и подцель могут содержать переменные. Одноимённые переменные имеют смысл только в рамках одного правила, т.е. областью действия переменной в Пролог является утверждение (как факт правила или цель).