В статье рассматривается 5 простых задач и предлагаются детали их реализации.
Автор: Потапенко В.А.
Написал: artish   Дата: 2008-09-09 19:33
Комментарии: (2)   Рейтинг:
Простые задачи (5 задач)


1. Задача: Длина списка
Написать функцию LEN , которая возвращает длину списка,
переданного функции в качестве параметра.

Пример:
( LEN ’(A B C)) вернет 3
( LEN NIL) вернет 0

Определения:
Длина пустого списка равна 0,
Длина списка L равна 1 + длина списка (cdr L)

Идея решения:

Организовать рекурсию по длине списка – аргумента.

Детали реализации:

 
(defun LEN (list)
(cond ((eq list nil) 0)
(t (+ 1 (LEN (cdr list))))
)
)
 


2. Задача: Обращение списка
Написать функцию REV, которая берет список в качестве
аргумента и возвращает обращенный список в качестве
результата.

Пример:
(REV NIL) вернет NIL
(REV ’(A B C)) вернет (C B A)
(REV ’(A B (C) D (T))) вернет ((T) D (C) B A)

Идея решения:
Одно из возможных решений основывается на методе
накапливающего параметра.

Детали реализации:
 
(defun REV (list h-arg)
(cond ((eq list nil) h-arg)
(t (REV (cdr list) (cons (car list) h-arg)))
)
)
 

Запускать эту функцию необходимо следующим образом:
(REV <некоторый список> NIL)


3. Задача: В один уровень
Написать функцию IN-ONE-LEVEL , которая выстраивает атомы в многоуровневом
списке в один уровень.

Пример:
(IN-ONE-LEVEL ’(A B C)) вернет (A B C)
(IN-ONE-LEVEL ’(A (B) C)) вернет (A B C)
(IN-ONE-LEVEL ’(A (B (C)))) вернет (A B C)

Идея решения:
Одно из решений заключается в конструировании правильного результата,
однако, решить задачу можно и с помощью накапливающего параметра.

Детали реализации:
 
(defun in-one-level (x)
(cond
((null x) nil)
((atom x) (cons x nil))
(t (append~ (in-one-level (car x))
(in-one-level (cdr x))))
)
)
(defun append~ (x y)
(cond
((null x) y)
((atom x) (cons x y))
(t (cons (car x) (append~ (cdr x) y)))
)
)
 


4. Задача: Факториал
Написать функцию Факториал, которая по аргументу n возвращает число n!

Пример:
(Факториал 0) вернет 1
(Факториал 3) вернет 6
(Факториал 6) вернет 720

Определения:


Идея решения:
Задача может быть решена с помощью простой рекурсии.

Детали реализации:
 
(defun Факториал (n)
(cond
((= n 0)1)
(t (* n (Факториал (- n 1))))
)
)
 


5. Задача: Числа Фибоначчи
Написать функцию Fib, которая по аргументу n возвращает n-ое
число Фибоначчи

Пример:
Fib(0) вернет 1
Fib(1) вернет 1
Fib(4) вернет 5
Fib(5) вернет 8

Определения:


Идея решения:
Задача может быть решена, например, методом
накапливающего параметра, однако, можно и решить путем
параллельной рекурсии.

Детали реализации:
 
(defun Fib (n)
(cond
((= n 0)1)
((= n 1)1)
(t (+ (Fib (- n 2))(Fib (- n 1))))
)
)
 


Онлайн :

0 пользователь(ей), 30 гость(ей) :




Реклама на сайте: