Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Лабораторна робота 2 Визначення функції та рекурсія Цілі роботи- одержання теоретичних знань та пр

Работа добавлена на сайт samzan.net:


Лабораторна робота №2

Визначення функції та рекурсія

Цілі роботи:

  •  одержання теоретичних знань та практичних навичок з програмуванням на основі функцій;
  •  одержання практичних навичок щодо розробки рекурсивних функцій.

Завдання:

Скласти рекурсивну функцію для обробки списку з будь-якої кількості атомів, які складені з будь-яких знаків. Якщо у результаті обробки з атому видалені всі знаки, замінити його на атом <ПУСТО>.

Таблиця 2.1 – Варіанти завдань

№ п.п.

Спосіб обробки
  1.  

Упорядкувати цифри у кожному атомі списку (a53r2 a23r5)
  1.  

Розрахувати суму цифр у всьому списку (сума цифр списку ‘(a35f ab28 t1g) рівна 19)
  1.  

У кожному атомі списку латинські літери змінити на знак + (плюс), літери кирилиці – на знак – (мінус).

  1.  

Кожний атом списку будь-якої вкладеності замінити на кількість літер в атомі (a2е54 der5e) (2 4)
  1.  

У кожному атомі списку цифри розмістити у зворотному порядку
(a53r2 a23r5)
  1.  

Розрахувати добуток цифр у всьому списку
(добуток цифр списку ‘(a35f ab28 t1g) рівно 240)
  1.  

Замінити кожну цифру у атомах списку на перші три літери їй назви.
(a53r2 aдватриrпят)
  1.  

В кожному атомі списку замінити літери кирилиці замінити на знаки ~K~.
  1.  

У всіх атомах списку літери англійського алфавіту перетворити у прописні.
  1.  

У всіх атомах списку поміняти регістр літер англійського алфавіту на протилежний.
  1.  

У всіх атомів списку видалити знак із зазначеним номером.
  1.  

Кожний атом скласти з літер, знаку підкреслення та суми цифр
(a1b5c abc_6)

  1.  

Кожний атом списку скласти з упорядкованих цифр, знаку підкреслення та літер
  1.  

Кожний атом скласти з цифр, знаку підкреслення та літер англійського алфавіту.
  1.  

У кожному списку замінити літери англійського алфавіту на відповідний номер у алфавіті (aф6Гs4 1ф6Г194)
  1.  

Зі всіх атомів списку видалити зазначений знак
  1.  

Розрахувати суму цифр у атомах вкладених підсписків
  1.  

У всіх атомах списку видалити однакові знаки (знаки, що присутні в атомі більш одного разу).
  1.  

Кожний атом класти з суми цифр, знаку підкреслення та кодів літер.
  1.  

Кожний атом скласти з кількості цифр, знаку підкреслення, кількості літер, знаку підкреслення та кількості останніх знаків. (sa3+$4d4-r 3_3_3)
  1.  

Знаки кожного атома списку розташувати у вигляді послідовності цифр, а потім літер. Інші знаки видалити. (sa3+$4d4-r 344sad)
  1.  

Скласти список зі зазначеної кількості атомів, що складені зі зазначеної кількості знаків з використанням зазначеного знака.
  1.  

У кожному атомі видалити одиночні знаки
  1.  

У кожному атомі видалити цифри і літери, залишити тільки спеціальні знаки.

Теоретичні відомості

Визначення функції

Визначення нової функції в мові Lisp виконується за допомогою функції DEFUN, яка має наступний формат:

(DEFUN <ім’я> <лямбда-список> <тіло функції>)

Як можна побачити, визначення функції подібне визначенням лямбда-виразу, за винятком того, що визначення функції передбачає обов’язкове завдання імені, яке використовується у подальшому для виклику функції.

Лямбда-вираз є контекстною функцією і знищується після виклику. У відмінність від цього функція DEFUN зв’язує символ (ім’я  функції) з лямбда-виразом і зберігає цей зв'язок на весь сеанс роботи інтерпретатору. Для перевірки існування зв’язку символу з визначенням функції у мові Lisp служить предикатна функція FBOUNDP, а для отримання самого лямбда-виразу – функція SYMBOL-FUNCTION [7].

Наприклад, розглянемо визначення функції для розрахунку квадрату різниці двох величин:

(defun s2 (x y) (+ (- (* x x) (* 2 x y)) (* y y))),

де:

S2 – символ, що представляє ім’я функції, який функція DEFUN зв’язує з лямбда-виразом (+ (- (* x x) (* 2 x y)) (* y y));

(x y) – лямбда-список або список формальних параметрів функції.

Застосування функції:

(fboundp ‘s2)

повертає значення T (істина), а виклик функції:

(symbol-function ‘s2)

дозволяє отримати список:

(+ (- (* x x) (* 2 x y)) (* y y)).

Для розрахунку квадрату різниці чисел 2 і 3 слід записати виклик функції S2 у вигляді: (s2 2 3)

Функції – предикаты

Предикат – це функція, що визначає наявність деяких властивостей аргументу і повертає логічне значення NIL (хибне), або T (істина) [7].

У мові Lisp базовими предикатами є функції ATOM і EQ.

Функція ATOM перевіряє, якщо аргумент є атомом. В табл. 2.2 наведені низка прикладів застосування функції. Слід звернути увагу на те, що предикат ATOM сприймає пустий список як атом NIL.

Предикат EQ порівнює два символьних атома і повертає T, якщо вони ідентичні. Предикат можна використовувати тільки для символів та констант T и NIL. Функція не перевіряє логічну рівність аргументів, а тільки їх представлення у пам’яті, тому для чисел і списків можна отримати неадекватний результат. Для порівняння таких об’єктів використовуються інші функції.

Таблиця 2.2 – Приклади застосування базових предикатів ATOM и EQ

Вираз

Результат

Пояснення

(atom ‘abc)

T

ABC є символьним атомом

(atom ‘(a b c))

NIL

(A B C) є списком

(atom nil)

T

NIL є атомом

(atom ‘())

T

Пустий список може бути представлений як атом NIL, тому функція повертає T

(atom ‘(nil))

NIL

Аргумент є список, що містить один елемент

(eq ‘a ‘b)

NIL

Аргументи – різні символи

(eq ‘a (car ‘(a b c))

T

Другий аргумент – виклик функції CAR, яка повертає голову списку – атом A

(eq nil (atom ‘(a b)))

T

Другий аргумент повертає значення NIL

Крім функцій ATOM і EQ у мові Lisp передбачено ще ряд предикатів, що широко використовуються при композиції програм. Найбільш відомі функції-предикати представлені в табл. 2.3. Застосування предикатів сприяє розробці більш зрозумілих та читабельних програм і відповідає принципам функціонального програмування [7, 8].

Таблиця 2.3 - Функції – предикати у мові Lisp

Найменування

Призначення

LISTP

Перевіряє, чи є аргумент списком

CONSP

Перевірка структури списку (cons-осередку)

NULL

Перевірка пустого списку

NUMBERP

Перевіряє, чи є аргумент числовим атомом

PLUSP

Перевірка числового атома на додатне значення

MINUSP

Перевірка числового атома на від’ємне значення

ZEROP

Перевірка числового атома на нуль

BOUNDP

Перевіряє, чи існує зв'язок символу з деяким значенням

FBOUNDP

Перевірка зв’язку символу з лямбда-виразом

Псевдофункції

У функціональному програмуванні функція повинна мати властивість математичної функціональності – виконання обчислень і повернення значення. Однак в програмуванні часто застосовуються функції, що виконують додаткові дії, крім обчислення виразу, тобто мають побічний ефект. Такі функції називаються псевдофункціями [7, 8].

У мові Lisp застосовується ряд псевдофункцій, що потрібні для написання практичних програм. Найбільш широко використовуються наступні функції:

  •  SET, SETQ, SETF – функції, що встановлюють зв'язок символу з деяким значенням. Така дія аналогічна операції присвоєння. Функції повертають значення, що зв’язано, а у якості побічного ефекту зміняють внутрішній стан символу.
  •  READ – функція читання з вхідного потоку. Повертає значення, що прочитано, а у якості побічного ефекту виконує операцію читання.
  •  PRINT, PRIN1, PRINC, WRITE, FORMAT – функції запису у вихідний потік. Повертає значення, що передано в потік, а у якості побічного ефекту виконує перетворення даних і вивід.

Додаткові матеріали про ці функції можна знайти в [7].

Рекурсивні функції

Застосування рекурсивних функцій у повній мірі відповідає функціональному стилю програмування, а точніше, головному принципу – композиція програм з викликів функцій без накопичення у змінних проміжних результатів [6]. Основне призначення рекурсивних функцій – виконання циклічних операцій.

Функція є рекурсивною, якщо їй визначення містить виклик самої функції. Якщо деяка гілка програми містить один рекурсивний виклик, така рекурсія називається простою. При двох і більш рекурсивних викликах в одної гілці програми говорять про паралельну рекурсію. Якщо деяка функція F містить виклик другої функції G, а визначення функції G містить виклик функції F, то така організація функції називається взаємною рекурсією. Якщо рекурсивний виклик містить у якості фактичних параметрів рекурсивний виклик, то це – рекурсія більш високого порядку [7].

Будь-яка рекурсивна функція містить щонайменше дві гілки: рекурсивну і термінальну. Термінальна гілка повертає значення, що заздалегідь відоме при деяких умовах. Рекурсивна гілка містить рекурсивний виклик функцій з фактичними параметрами, значення яких приведе у подальшому до термінальної гілки. Це є обов’язковою умовою завершення рекурсивного процесу і, відповідно, рекурсивної функції.

У якості прикладу розглянемо функцію розрахунку довжини списку. На підставі того, що існує лише можливість отримання доступу до голови (першого елементу) і хвосту списку, кількість елементів можна полічити як суму:

L(s) = 1 + L(st), (2.1)

де:

S – список;

St – хвіст списку S

L(s) – довжина списку S

L(st) – довжина хвоста списку S, яка обчислюється по формулі 2.1

Для функції L(s) можна однозначно казати, що, якщо S – пустий список, то L(s) = 0.

Таким чином, попередні міркування можна записати на мові Lisp у наступному вигляді:

(defun LENLIST (x) ; визначення функції (x – список)

(if (NULL x)  ; якщо список пустий

0  ; кількість елементів рівно(дорівнює) 0

; (це термінальна гілка функції)

; інакше здійснюється рекурсивний виклик функції

(+ 1 (LENLIST (cdr x))) 

; LENLIST для хвоста списку, до результату

; якого додається 1

) ; заключна дужка функції IF

) ; заключна дужка визначення функції

Методичні вказівки

Загальні вказівки щодо виконання завдання

Для рішення завдання відповідно до варіанту необхідно розробити рекурсивні функції обробки списку. У якості фактичного параметру може бути використаний будь-який однорівневий список з довільної кількості атомів, кожний з яких може складатися з будь-яких припустимих знаків.

Виконання завдання варто почати з декомпозиції всієї задачі на більш дрібні підзадачі, які згодом будуть втілені в окремі прості функції. Обов'язково варто передбачити розробку функцій - предикатів, які можна використати при реалізації умов рекурсивного виклику в більш складних функціях.

Для роботи із символьними атомами їх варто перетворити в список знаків, а після відповідної обробки виконати зворотне перетворення в символ. Для цього можна застосувати функції, представлені нижче.

Розробка функцій повинна виконуватися в строгій відповідності із принципами функціонального програмування. Так, у розроблених функціях у даній лабораторній роботі повинні бути відсутні локальні та глобальні змінні, функції зв'язування, функції циклів. Визначення функцій повинні містити лише рекурсивні виклики, або виклики інших функцій.

Функції розгалужених операцій

Умовна пропозиція COND

Функція COND є основним засобом розгалуження обчислень у мові Lisp. Функція має наступний формат:

(COND (p1 a1) (p2 a2) … (pі aі) …(pn an) )

де: pi – будь-яка предикатна форма;

Ai – форма, яка обчислюється у разі, якщо предикат pi дорівнює T (істина) і повертається у якості результату функції COND.

Якщо предикат pi дорівнює NIL (хибне), відповідна форма ai не обчислюється і виконується перехід до наступного предикату. Якщо всі N предикатів хибні, функція COND повертає NIL.

Умовна пропозиція IF

Функція IF є спрощеною формою функції  COND, й використовується у випадках коли існує лише одна альтернатива. Функція має наступний формат:

(IF p a1 a2)

де: p – предикатна форма;

a1 – форма, яка обчислюється у разі, якщо предикат p дорівнює T (істина) і повертається у якості результата функції IF;

a2 – форма, яка обчислюється у разі, якщо предикат p дорівнює NIL і повертається у якості результата функції IF

Функції для роботи з ім'ям символу

Для отримання доступу до кожного знаку символа атома використовуються наступні функції перетворювання (табл. 2.4):

Таблиця 2.4 – Функції перетворення даних

Функція

Призначення

Пояснення

(string <symbol>)

перетворювання символа в рядок

symbol – символьний атом

(coerce <arg> <type>)

универсальна функція перетворювання

arg – об’єкт, що перетворюється

type – тип, до якого здійснюється перетворення

(intern <string>)

створення символа з рядка

string – рядок

(char-code <mark>

визначення ASCII-коду знака

mark – знак

(code-char <int>)

визначення знака по ASCII-коду

int – ціле число

Таблиця 2.5 – Приклади застосування функцій перетворення даних

Применение функции

Результат

(string ‘data43b)

“DATA43B”

(string ‘|daTA43b|)

“daTA43b”

(coerce “daTA43b” ‘list)

(#\d #\a #\T #\A #\4 #\3 #\b)

(coerce ‘(#\d #\a #\T #\A #\b) ‘string)

“daTAb”

(intern “daTAb”)

|daTAb|

(char-code #\3)

51

(code-char 97)

#\a

Приклад виконання завдання

Завдання: У кожному атому списку залишити лише парні цифри. Якщо у атомі не залишаються знаки, тоді слід замінити словом ПУСТО

Рішення:

Розглянемо рішення задачі взагалі. Припустимо, що маємо функцію CONVERT, яка виконує перетворення атому відповідно до завдання. Тоді, для обробки всього списку X, запишемо рекурсивну функцію MAIN, яка перетворює голову списку, а потім створює новий список за допомогою конструктора CONS. У якості фактичних параметрів використаємо перетворену голову списку й рекурсивний виклик для перетворення хвоста:

(cons (convert (car X)) (main (cdr X)))   (2.1)

Вираз (2.1) використаємо як рекурсивну гілку функції. Термінальну гілку створюємо з умов, що перетворення пустого списку є пустий список. Таким чином, функцію MAIN запишемо у вигляді:

(defun main (X)

(if ((null X) ; якщо список X пустий

 nil   ; функція повертає пустий список

(cons (convert (car X)) (main (cdr X)))

    ; інакше створюється новий список

)

)

Дія функції CONVERT представимо з наступних кроків:

  1.  перетворення атому до списку знаків;
  2.  видалення зі списку всіх знаків, крім парних цифр;
  3.  перетворення списку знаків, що залишились, до атому.

Перший крок можна реалізувати на основі функцій перетворення (табл. 2.1). Відповідна функція AtomToList має наступний вигляд:

(defun AtomToList (X) (coerce (string X) ‘list))

Аналогічно реалізуємо третій крок, однак при цьому необхідно повертати атом ПУСТО у разі, якщо список знаків пустий. Напишемо функцію ListToAtom, яка здійснює ці дії :

(defun ListToAtom (X)

(if (null x) ‘ПУСТО

(intern (coerce X ‘string)))

Реалізація другого кроку більш складна. По-перше, необхідна предикатна функція для визначення знаку, що є парною цифрою. Очевидно, що парну цифру можна визначити через ASCII код знаку. Тоді відповідну функцію напишемо таким чином:

(defun IsEven (x)

(and

(< 47 (char-code x) 58)  ; перевірка, чи є знак цифрою

(evenp (char-code x)) ; перевірка, чи є код парним числом

))

Далі розглянемо, яким чином можна перетворити список знаків, залишивши тільки парні цифри:

  1.  Якщо список пустий, тоді результатом перетворення – пустий список
  2.  Якщо список не пустий, тоді розглянемо голову списку. Якщо голова списку – парна цифра, тоді перетворюємо хвіст і створюємо новий список, включаючи голову до перетвореного списку. Інакше, функція повинна повернути перетворений хвіст.

Напишемо функцію ConvertList, що перетворює список знаків відповідно вищевказаного:

(defun ConvertList (Lst)

(cond

; список пустий, функція повертає пустий

; список (термінальна гілка)

((null Lst) nil)

; якщо голова списку – парна цифра, створюємо

; новий список з голови списку та хвоста, який

; перетворюється за допомогою рекурсивного виклику

((IsEven (car Lst)) (cons (car Lst)

(ConvertList (cdr Lst))))

; якщо голова списку не парна цифра –

; функція повертає лише перетворений хвіст

(T  (ConvertList (cdr Lst)))

))

Нарешті, запишемо функцію Convert, що складається з викликів вже розроблених функцій:

(defun Convert (X)

(ListToAtom (ConvertList (AtomToList X))))

Контрольні запитання

  1.  Визначення функції.
  2.  Визначення рекурсивної функції.
  3.  Види рекурсивних функції.
  4.  Псевдофункції.
  5.  Функції – предикати.
  6.  Умовні пропозиції у мові Lisp.

PAGE   \* MERGEFORMAT 23




1. Способность слова связываться с другими словами проявляется в словосочетании
2. Налоги следует отличать от сборов пошлин взимание которых носит не безвозмездный характер а является ус
3. СОГЛАСОВАНО Заведующий учебным отделом Ярославского филиала ЛГУ им.1
4. тема курса судебной бухгалтерии
5. його швидкодію до 10^9 операцій в секунду
6. Построение профессиональной сети как средства продвижения развивающегося медиабизнеса на примере ООО Дневник.Ру
7. 1996 N 3 от 31.10.1998 N 1272 от 21
8. по теме- И Кант- метафизика свободы
9. по теме Измерение активного сопротивления методом мостиковой схемы мостик Уитстона -Сост
10. тематических моделях Внутренние элементы системы отражаются только в полуэмпирических математическ
11. Экономико-правовое понятие собственности
12. Нивенс МакТвисп Траляля и Труляля Пес Баярд Хаммар Гусеница Абсолем Безумный Шляпник Мартовски
13. Б- 2 Назвіть хто повинен виплачувати потерпілому від нещасних випадків на підприємстві одноразову до
14. House and home in the world outlook of different cultures
15. Опытное изучение свойств материалов- назначение и виды испытаний. Повышение текучести при повторных нагружениях
16. летие На момент основания в него входили 10 государствучредителей
17. основные правила метода найденного автором; в третьей некоторые из правил морали извлеченных автором из э
18. РЕФЕРАТ УКРАЇНСЬКА ГРИВНЯ- ІСТОРІЯ ТА СЬОГОДЕННЯ Однією з ознак державності є власна грошова одини
19. темами 1 на вибір- Deutsche Welle ~ історія створення та політика медіакомпанії
20. Тематический план по дисциплине Д13-1 ~ФИЛОСОФИЯ Направление подготовки- для всех направлен

Материалы собраны группой SamZan и находятся в свободном доступе