99-lisp lisp 的99个问题 P1-10-白红宇

99-lisp lisp 的99个问题 P1-10

阅读量：2509 次

发布时间：2019-05-11

本文共 5564 字，大约阅读时间需要 18 分钟。

这里的问题来自prolog 的练习题，

具体出处不明白，源连接已经打不开了，我是从google 的cache 里抓出来的。

有兴趣的同学，哪来练练手

先贴 1-10 第7个问题没有解出来，心里明白，手里写不出来，练的不够。

L-99: Ninety-Nine Lisp Problems

Based on a Prolog problem list by werner.hett@hti.bfh.ch

Working with lists

P01 (*) Find the last box of a list.

Example:

* (my-last '(a b c d))

(D)

CL-USER> (defun last-l (l)

(if (null (cdr l)) l

(last-l (cdr l))))

LAST-L

CL-USER> (last-l '(a b c( c d )))

(C)

CL-USER> (last-l '(a b c( c d )))

((C D))

P02 (*) Find the last but one box of a list.

Example:

* (my-but-last '(a b c d))

(C D)

CL-USER> (defun my-but-l (l)

(if (= 1 (length (cdr l))) l

(my-but-l (cdr l))))

STYLE-WARNING: redefining COMMON-LISP-USER::MY-BUT-L in DEFUN

MY-BUT-L

CL-USER> my-but-l '( a b c d ( x y)))

(C D)

CL-USER> (my-but-l '( a b c d ( x y)))

(D (X Y))

CL-USER>

CL-USER>(defun my-but-l (l)

(if (null (cdr (cdr l))) l

(my-but-l (cdr l))))

CL-USER> (my-but-l '( a b c d ( x y)))

(D (X Y))

CL-USER> (my-but-l '( a b c d ))

(C D)

P03 (*) Find the K'th element of a list.

The first element in the list is number 1.

Example:

* (element-at '(a b c d e) 3)

CL-USER> (defun element-n (l n)

(if (<= n (length l)) (nth (1- n) l)

nil))

ELEMENT-N

CL-USER> (elment-n '(a b c d) 3)

CL-USER> (elment-n '(a b (c d e) d) 3)

(C D E)

CL-USER> (element-n '(a b c) 3)

NIL

CL-USER> (element-n '(a b c) 3)

CL-USER>

P04 (*) Find the number of elements of a list.

提示通过构建hash表来去重，性能一般。

(defun element-of-l (l)

(let ((h (make-hash-table )))

(loop for i in l do

(setf (gethash i h) i))

(hash-table-count h)))

ELEMENT-OF-L

CL-USER> (element-of-l '(a b c d a e f a))

CL-USER> (element-of-l '(a))

CL-USER> (element-of-l '(a b c d a e f a (s q ( s q))))

CL-USER>

; No value

CL-USER> (element-of-l '(a b c d a e f a (s q ( s q)) (s q) ))

CL-USER>

P05 (*) Reverse a list.

CL-USER> (reverse '(a b c d (e f) ))

(D C B A)

CL-USER> (reverse '(a b c d (e f) ))

((E F) D C B A)

CL-USER>

P06 (*) Find out whether a list is a palindrome.

A palindrome can be read forward or backward; e.g. (x a m a x).

(defun palidrome?(l)

(let ( (rl (reverse l))

(s nil))

(setq s (multiple-value-list ( loop for i in rl do

(mapcar #'equal rl l))))

(loop for k in s do

(if (not (eql k t) ) (return nil)))

t))

STYLE-WARNING: redefining COMMON-LISP-USER::PALIDROME? in DEFUN

PALIDROME?

CL-USER> (palidrome? '(a b c (x y) c b a))

CL-USER> (palidrome? '(aa bb cc (x y) cc bb aa))

CL-USER>

P07 (**) Flatten a nested list structure.

Transform. a list, possibly holding lists as elements into a `flat' list by replacing each list with its

elements (recursively).

Example:

* (my-flatten '(a (b (c d) e)))

(A B C D E)

Hint: Use the predefined functions list and append.

P08 (**) Eliminate consecutive duplicates of list elements.

If a list contains repeated elements they should be replaced with a single copy of the element. The order

of the elements should not be changed.

Example:

* (compress '(a a a a b c c a a d e e e e))

(A B C A D E)

CL-USER> (defun get-element (lst)

(if (null lst ) nil

(let ((rl (list(car lst) ))

(first (car lst)))

(loop for i in lst do

(if (not (equal first i ))

(progn

(setf rl (append rl (list i)))

(setf first i ))))

rl)))

STYLE-WARNING: redefining COMMON-LISP-USER::GET-ELEMENT in DEFUN

GET-ELEMENT

CL-USER> (get-element nil)

NIL

CL-USER> (get-element '(a a a a b c c a a d e e e e))

(A B C A D E)

CL-USER> (get-element '(a a a a b c c a a (x y) (x y) (x y y) d e e e e))

(A B C A (X Y) (X Y Y) D E)

CL-USER>

P09 (**) Pack consecutive duplicates of list elements into sublists.

If a list contains repeated elements they should be placed in separate sublists.

Example:

* (pack '(a a a a b c c a a d e e e e))

((A A A A) (B) (C C) (A A) (D) (E E E E))

CL-USER> (defun pack (lst)

(if (null lst)

nil

(let ((rl '())

(ra (list (car lst)))

(first (car lst)))

(loop for i in (cdr lst) do

(if (equal first i)

(setf ra (append ra (list i)))

(progn

(setf rl (append rl (list ra)))

(setf ra (append '() (list i)))

(setf first i ))))

(setf rl (append rl (list ra)))

rl)))

STYLE-WARNING: redefining COMMON-LISP-USER::PACK in DEFUN

PACK

CL-USER> (pack lst)

((A A A A) (B) (C C) (A A) (D) (E E E E))

CL-USER>

一个看起来更加lisp 的写法:

(defun pack (l)

(cond ((null l) nil)

((atom l) (list l))

((list l)

(cond

((eq (car l) (cadr l))

(cons

(append (list (car l)) (car (pack (cdr l))))

(cdr (pack (cdr l))) ))

(t (cons (list (car l)) (pack (cdr l))))

))

从效率上说，前面的循环比后面的递归写法，效率快10倍左右。

后面的递归不是尾递归实现。

P10 (*) Run-length encoding of a list.

Use the result of problem P09 to implement the so-called run-length encoding data compression method.

Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the

element E.

Example:

* (encode '(a a a a b c c a a d e e e e))

((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))

CL-USER> (defun count-element (lst)

(if (null lst) nil

(append (list (my-count (car lst))) (my-element (cdr lst)))))

STYLE-WARNING: redefining COMMON-LISP-USER::COUNT-ELEMENT in DEFUN

COUNT-ELEMENT

CL-USER> (defun my-count (lst)

(cons (length lst) (car lst)))

STYLE-WARNING: redefining COMMON-LISP-USER::MY-COUNT in DEFUN

MY-COUNT

CL-USER> (defun encode (lst)

(count-element(pack lst)))

STYLE-WARNING: redefining COMMON-LISP-USER::ENCODE in DEFUN

ENCODE

CL-USER> (encode lst)

((4 . A) (1 . B) (2 . C) (2 . A) (1 . D) (4 . E))

CL-USER> (defun my-count(lst)

(list (length lst) (car lst)))

CL-USER> (encode lst)

((4 A) (1 B) (2 C) (2 A) (1 D) (4 E))

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/133735/viewspace-750512/，如需转载，请注明出处，否则将追究法律责任。

转载于:http://blog.itpub.net/133735/viewspace-750512/

你可能感兴趣的文章

2017-03-05 CentOS中结合Nginx部署dotnet core Web应用程序

查看>>

并发与同步、信号量与管程、生产者消费者问题

查看>>

cdoj 71 I am Lord Voldemort 水题

查看>>

UVA 12898 And Or 数学暴力

查看>>

Codeforces Round #345 (Div. 2) E. Table Compression 并查集

TZC Intercommunication System

20155305乔磊2016-2017-2《Java程序设计》第一周学习总结

查看>>