Տարիներ առաջ, երբ ես սովորում էի ԵՊՀ-ի ԻԿՄ ֆակուլտետում, երկրորդ կամ երրորդ կուրսում անցնում էինք մի անհասկանալի առարկա։ Այդ առարկայի անվանումն էր «Ֆունկցիոնալ ծրագրավորման համակարգեր» (կամ «Ծրագրավորման ֆունկցիոնալ համակարգեր»)։ Դասախոսություններին պատմում էին ինչ-որ անհասկանալի ու ախմախ բաների մասին։ Բայց գործնական դասերը, որոնք ոչ մի կապ չունեին դասախոսությունների հետ, գոնե հետաքրքիր էին նրանով, որ խնդիրներ էինք լուծում Lisp լեզվով։ Խնդրագիրք ասած բանն, իհարկե, գոյություն չուներ․ դասախոսներն ունեին սովորական թղթերի վրա տպած մի ցուցակ, որից էլ դասերին վարժություններ էինք անում։
Ստորև բերված են այդ ցուցակի խնդիրներից մի մասի լուծումներ։ Որոշ խնդիրների պահանջներ միգուցե վատ են ձևակերպված, որոշներինը՝ ակնհայտ անհեթեթություն են։ Բայց սա այն է, ինչ որ կար...
Լրացում (12.մարտ.2016)։ Ինձ հայտնի դարձավ, որ ստորև բերված խնդիրների հավաքածուն ԵՊՀ ԻԿՄ ֆակուլտետում հրատարակվել (կապ պատրաստվում է հրատարակության) առանձին խնդրագրքի տեսքով։ Այս խնդիրների ձևակերպումների բոլոր հեղինակային իրավունքները պատկանում են այդ խնդրագրքի հեղինակին կամ հեղինակային խմբին։ Նույն այդ հեղինակները որևէ առնչություն չունեն խնդիրների հետ բերված լուծումների հետ։
4. Գրել տրված \(n\) թվի ֆակտորիալը հաշվարկող ծրագիր:
Հետևելով ֆակտորիալի սահմանմանը՝ \(n!=1\cdot 2\cdot\ldots\cdot n\), կգրենք հետևյալ ֆունկցիան։
(defun factorial (n)
(if (= n 0)
1
(* n (factorial (1- n)))))
Բայց ավելի արդյունավետ կլինի գրել ֆակտորիալը հաշվող ֆունկցիայի
tail recursive տարբերակը։ Հետևյալ
factorial-b ֆունկցիայի մարմնում սահմանված է
factorial-rec ֆունկցիան, որի երկրորդ արգումենտը նախատեսված է արդյունքը կուտակելու համար։
(defun factorial-b (n)
(labels
((factorial-rec (m r)
(if (= m 1)
r
(factorial-rec (1- m) (* m r)))))
(factorial-rec n 1)))
5. Գրել Ֆիբոնաչիի հաջորդականության
N-րդ անդամը հաշվարկող ծրագիր:
Նորից հետևելով Ֆիբոնաչիի թվերի սահմանմանը, կարելի է սահմանել հետևյալ ֆունկցիան։
(defun fibonachi (N)
(if (or (= N 0) (= N 1))
1
(+ (fibonachi (- N 1)) (fibonachi (- N 2)))))
Ֆիբոնաչիի թվերի համար էլ կարելի է սահմանել tail recursive ֆունկցիա։ Ահա այն․
(defun fibonacci-b (n)
(labels
((fibonacci-rec (m a b)
(if (< m 2)
a
(fibonacci-rec (- m 1) (+ a b) a))))
(fibonacci-rec n 1 0)))
6. Գրել \(x\) բնական թիվը չգերազանցող զույգ թվերի գումարը:
(defun sum-of-evens (x)
(cond
((zerop x) 0)
((evenp x) (+ x (sum-of-evens (1- x))))
(t (sum-of-evens (1- x)))))
(defun sum-of-evens-b (x)
(labels
((sum-of-evens-rec (y s)
(cond
((zerop y) s)
((evenp y) (sum-of-evens-rec (1- y) (+ s y)))
(t (sum-of-evens-rec (1- y) s)))))
(sum-of-evens-rec x 0)))
7. Գրել \(x\) թվին չգերազանցող կենտ թվերի արտադրյալը:
(defun prod-of-odds (x)
(cond ((= x 1) 1)
((oddp x) (* x (prod-of-odds (1- x))))
(t (prod-of-odds (1- x)))))
(defun prod-of-odds-b (x)
(labels
((prod-of-odds-rec (y p)
(cond ((= y 1) p)
((oddp y) (prod-of-odds-rec (1- y) (* p y)))
(t (prod-of-odds-rec (1- y) p)))))
(prod-of-odds-rec x 1)))
8. Գրել \(x\) թվի կիսաֆակտորիալը հաշվող ֆունկցիա:
(defun semifactorial (x)
(labels
((semifac-help (k)
(if (< k 0)
1
(* (semifac-help (1- k)) (- x (* 2 k))))))
(semifac-help (1- (ceiling x 2)))))
(defun semifactorial-b (x)
(labels
((semifac-rec (k r)
(if (< k 0)
r
(semifac-rec (1- k) (* r (- x (* 2 k)))))))
(semifac-rec (1- (ceiling x 2)) 1)))
9. Lisp լեզվով սահմանել
most-divisor ֆունկցիան.
F(x)=x թվի ամենամեծ բաժանարարը, եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun most-divisor (x)
(labels
((most-div-help (a b)
(cond
((zerop b) 1)
((zerop (rem a b)) b)
(t (most-div-help a (1- b))))))
(cond
((<= x 0) 0)
((< x 3) 1)
((evenp x) (/ x 2))
(t (most-div-help x (1- x))))))
10. Lisp լեզվով սահմանել Էվիկլիդեսի ալգորիթմը:
(defun euclid(x y)
(if (= y 0)
x
(euclid y (mod x y))))
11. Օգտվելով
1+ ֆունկցիայից Lisp-ով ծրագրավորել երկու տեղանի գումարման
plus ֆունկցիան ամբողջ թվերի համար:
(defun plus (a b)
(if (zerop b)
a
(plus (1+ a) (1- b))))
12. Օգտվելով
+ ֆունկցիայից, ծրագրավորել
prod ֆունկցիան, ամբողջ թվերի համար:
(defun prod (x y)
(labels
((prod-help (b r)
(if (zerop b)
r
(prod-help (1- b) (+ x r)))))
(if (or (= y 0) (= x 0))
0
(prod-help y 0))))
13. Օգտվելով
* ֆունկցիայից, ծրագրավորել աստիճան բարձրացնելու
ex ֆունկցիան, ամբողջ թվերի համար:
(defun ex (x y)
(if (zerop y)
1
(* x (ex x (1- y)))))
14. Սահմանել հետևյալ ֆունկցիան. \(F(x)=x!+(2x)!\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex14 (x)
(if (< x 0)
0
(+ (factorial x) (factorial (* 2 x)))))
15. Սահմանել հետևյալ ֆունկցիան. \(F(x)=x!+x^y\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex15 (x y)
(if (< x 0)
0
(+ (factorial x) (expt x y))))
16. Սահմանել հետևյալ ֆունկցիան. \(F(x,y)=(xy)!\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex16 (x y)
(if (or (< x 0) (< y 0))
0
(* (factorial x) (factorial y))))
17. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x i^2\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex17 (x)
(if (< x 0)
0
(+ (* x x) (ex17 (1- x)))))
18. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x (2i)!\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex18 (x)
(if (minusp x)
0
(+ (factorial (* 2 x)) (ex18 (1- x)))))
19. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^y(xi)!\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex19 (x y)
(if (or (<= x 0) (<= y 0))
0
(+ (factorial (* x y)) (ex19 x (1- y)))))
20. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^x i^y\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex20 (x y)
(if (minusp x)
0
(+ (expt x y) (ex20 (1- x) y))))
21. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x\sqrt{i}\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex21 (x)
(if (< x 0)
0
(+ (sqrt x) (ex21 (1- x)))))
22. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\prod\limits_{i=0}^xe^i\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex22 (x)
(if (<= x 0)
1
(* (exp x) (ex22 (1- x)))))
23. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\prod\limits_{i=0}^y(x^i+i)\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex23 (x y)
(if (< y 0)
1
(* (+ (expt x y) y) (ex23 x (1- y)))))
24. Սահմանել հետևյալ ֆունկցիան. \(f(x,y,z)=\prod\limits_{i=0}^z(x^i+y^i)\), եթե \(x,y,z\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex24 (x y z)
(if (< z 0)
1
(* (+ (expt x z) (expt y z)) (ex24 x y (1- z)))))
25. Սահմանել հետևյալ ֆունկցիան. \(f(x,y,z)=\prod\limits_{i=0}^z(i^x+i^y)\), եթե \(x,y,z\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex25 (x y z)
(if (< z 0)
1
(* (+ (expt z x) (expt z y)) (ex25 x y (1- z)))))
26. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^y\log_yx\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex26 (x y)
(if (<= y 1)
0
(+ (log x y) (ex26 x (1- y)))))
27. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի բաժանարարների քանակը:
(defun count-divisors (x)
(labels
((divisors-rec (y)
(cond
((= 1 y) 1)
((zerop (rem x y)) (1+ (divisors-rec (1- y))))
(t (divisors-rec (1- y))))))
(cond
((<= x 3) 1)
((evenp x) (divisors-rec (/ x 2)))
(t (divisors-rec (1- x))))))
28. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի բաժանարարների գումարը:
(defun sum-of-divisors (x)
(labels
((sum-of-div-rec (y)
(cond
((= 1 y) 1)
((zerop (rem x y)) (+ y (sum-of-div-rec (1- y))))
(t (sum-of-div-rec (1- y))))))
(cond
((<= x 3) 1)
((evenp x) (sum-of-div-rec (/ x 2)))
(t (sum-of-div-rec (1- x))))))
29. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի պարզ լինելը:
(defun prime-p (x)
(= 1 (count-divisors x)))
30. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվից փոքր կամ հավասար պարզ թվերի քանակը:
(defun count-primes (x)
(cond
((zerop x) 0)
((prime-p x) (1+ (count-primes (1- x))))
(t (count-primes (1- x)))))
31. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի պարզ բաժանարարների քանակը:
(defun count-prime-divisors (x)
(labels
((divisors-rec (y)
(cond
((= 1 y) 1)
((and (prime-p y) (zerop (rem x y))) (1+ (divisors-rec (1- y))))
(t (divisors-rec (1- y))))))
(cond
((<= x 3) 1)
((evenp x) (divisors-rec (/ x 2)))
(t (divisors-rec (1- x))))))
32. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի կատարյալ լինելը:
(defun perfect-p (x)
(= x (sum-of-divisors x)))
33. Սահմանել \(eiler\) (?) ֆունկցիան. \(f(x)=f(0)\cdot\ldots\cdot f(x-1)+1\):
(defun f (x)
(labels
((h (y)
(if (= y 1)
1
(* (h (1- y)) (f (1- y))))))
(if (zerop x)
1
(1+ (h x)))))
34. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի զույգ լինելը:
(defun is-even (x)
(zerop (logand x 1)))
35. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի կենտ լինելը:
(defun is-odd(x)
(not (iseven x)))
36. Սահմանել
len_ անունով ֆունկցիա, որը վերադարձնում է տրված \(x\) ցուցակի երկարությունը (տարրերի քանակը) և
nil, եթե արգումենտը ցուցակ չէ:
(defun len_ (x)
(if (and (atom x) (not (null x)))
nil
(if (endp x)
0
(1+ (len_ (cdr x))))))
37. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի տարրերի գումարը:
(defun sum-1 (x)
(if (endp x)
0
(+ (car x) (sum-1 (cdr x)))))
38. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի զույգ տարրերի գումարը:
(defun sum-of-evens (x)
(if (endp x)
0
(if (evenp (car x))
(+ (car x) (sum-of-evens (cdr x)))
(sum-of-evens (cdr x)))))
39. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի զույգ տարրերի ցուցակը:
(defun list-of-evens (x)
(cond
((endp x) '())
((evenp (car x)) (cons (car x) (list-of-evens (cdr x))))
(t (list-of-evens (cdr x)))))
40. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի կենտ տարրերի գումարը:
(defun sum-of-odds (x)
(cond
((endp x) 0)
((oddp (car x)) (+ (car x) (sum-of-odds (cdr x))))
(t (sum-of-odds (cdr x)))))
41. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի կենտ տարրերի ցուցակը:
(defun list-of-odds (x)
(cond
((endp x) '())
((oddp (car x)) (cons (car x) (list-of-odds (cdr x))))
(t (list-of-odds (cdr x)))))
42. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի դրական տարրերի քանակը:
(defun count-positivs (x)
(cond
((endp x) 0)
((plusp (car x)) (1+ (count-positivs (cdr x))))
(t (count-positivs (cdr x)))))
43. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի դրական տարրերի ցուցակը:
(defun list-of-positivs (x)
(cond
((endp x) '())
((plusp (car x)) (cons (car x) (list-of-positivs (cdr x))))
(t (list-of-positivs (cdr x)))))
44. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերի քանակը:
(defun count-non-zeros (x)
(cond
((endp x) 0)
((not (zerop (car x))) (1+ (count-non-zeros (cdr x))))
(t (count-non-zeros (cdr x)))))
45. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերի ցուցակը:
(defun list-of-non-zeros (x)
(cond
((endp x) '())
((not (zerop (car x))) (cons (car x) (list-of-non-zeros (cdr x))))
(t (list-of-non-zeros (cdr x)))))
46. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ամենամեծ տարրը:
(defun maximum (x)
(if (endp (cdr x))
(car x)
(let ((m (maximum (cdr x)))
(c (car x)))
(if (> c m) c m))))
47. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ամենափոքր տարրը:
(defun minimum (x)
(if (endp (cdr x))
(car x)
(let ((m (minimum (cdr x)))
(c (car x)))
(if (< c m) c m))))
48. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) ոչ գծային ցուցակի ամենամեծ տարրը:
(defun max-list (x)
(flet ((max-2 (a b) (if (> a b) a b)))
(let ((a (car x)) (d (cdr x)))
(if (endp d)
(if (atom a) a (max-list a))
(max-2 (if (atom a) a (max-list a)) (max-list d))))))
49. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) ոչ գծային ցուցակի ամենափոքր տարրը:
(defun min-list (x)
(flet ((min-2 (a b) (if (< a b) a b)))
(let ((a (car x)) (d (cdr x)))
(if (endp d)
(if (atom a) a (min-list a))
(min-2 (if (atom a) a (min-list a)) (min-list d))))))
50. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերից ամենամեծը:
(defun max-non-zero (x)
(maximum (list-of-non-zeros x)))
51. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակում \(y\)-ից մեծ և \(z\)-ին պատիկ թվերի քանակը:
(defun ex51 (x y z)
(if (endp x)
0
(if (and (> (car x) y) (zerop (mod (car x) z)))
(1+ (ex51 (cdr x) y z))
(ex51 (cdr x) y z))))
52. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակում \(y\)-ից մեծ և \(z\)-ին պատիկ թվերի ցուցակը:
(defun ex52 (x y z)
(if (endp x)
'()
(if (and (> (car x) y) (zerop (mod (car x) z)))
(cons (car x) (ex52 (cdr x) y z))
(ex52 (cdr x) y z))))
53. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) ցուցակի ատոմների քանակը (ցուցակը կարող է լինել նաև ոչ գծային):
(defun count-atoms (x)
(cond
((endp x) 0)
((atom (car x)) (1+ (count-atoms (cdr x))))
(t (+ (count-atoms (car x)) (count-atoms (cdr x))))))
54. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ոչ գծային ցուցակի ատոմների ցուցակը:
(defun list-of-atoms (x)
(cond
((endp x) '())
((atom (car x)) (cons (car x) (list-of-atoms (cdr x))))
(t (append (list-of-atoms (car x)) (list-of-atoms (cdr x))))))
55. Սահմանել ֆունկցիա, որը վերադարձնում է տրված գծային ցուցակի \(n\)-րդ տարրը: Եթե ցուցակի երկարությունը փոքր է \(n\)-ից, ապա վերադարձնել ցուցակի երկարությունը՝ գումարած \(1\):
(defun n-th-elem (l n)
(labels
((n-th-rec (j m)
(cond
((endp j) (1+ m))
((= n m) (car j))
(t (n-th-rec (cdr j) (1+ m))))))
(n-th-rec l 0)))
56. Տարրական ֆունկցիաներով ծրագրավորել երկու ցուցակների միակցումը վերադարձնող ֆունկցիան:
(defun append-2 (x y)
(if (endp x)
y
(cons (car x) (append-2 (cdr x) y))))
57. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի վերջին տարրը:
(defun last-elem (l)
(if (endp (cdr l))
(car l)
(last-elem (cdr l))))
58. Սահմանել ֆունկցիա, որը տրված \(x\) ցուցակին աջից կցում է տրված \(y\) ատոմը:
(defun add-right (x y)
(if (endp x)
(cons y '())
(cons (car x) (add-right (cdr x) y))))
59. Սահմանել պրեդիկատ, որը ստուգում է տրված \(e\) ատոմը գոյությունը \(l\) գծային ցուցակում:
(defun contains (l e)
(cond
((endp l) nil)
((equal (car l) e) t)
(t (contains (cdr l) e))))
60. Սահմանել պրեդիկատ, որը ստուգում է տրված \(e\) տարրի գոյությունը \(l\) ոչ գծային ցուցակում:
(defun contains-nl (l e)
(if (endp l)
nil
(let ((a (car l)) (d (cdr l)))
(or (if (atom a)
(equal a e)
(contains-nl a e))
(contains-nl d e)))))
61. Սահամնել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրի դիրքը: Եթե \(e\)-ն ցուցակում բացակայում է, ապա վերադարձնել ցուցակի երկարությունը՝ գումարած \(1\):
(defun elem-pos (l e)
(labels
((elem-pos-rec (j m)
(cond
((endp j) (1+ m))
((equal (car j) e) m)
(t (elem-pos-rec (cdr j) (1+ m))))))
(elem-pos-rec l 0)))
62. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրին հաջորդող տարրը: եթե այդպիսին չկա, վերադարձնել
nil:
(defun next-elem (l e)
(cond
((or (endp l) (endp (cdr l))) nil)
((equal (car l) e) (cadr l))
(t (next-elem (cdr l) e))))
63. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրերի քանակը:
(defun count-elem (l e)
(cond
((endp l) 0)
((equal (car l) e) (1+ (count-elem (cdr l) e)))
(t (count-elem (cdr l) e))))
64. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակի շրջված ցուցակը:
(defun rev-list (l)
(labels
((rev-rec (l r)
(if (endp l)
r
(rev-rec (cdr l) (cons (car l) r)))))
(rev-rec l '())))
65. Սահմանել ֆունկցիա, որը աճման կարգով կարգավորված բնական թվերի \(l\) ցուցակում ավելացնում է \(e\) տարրը:
(defun insert-elem (l e)
(if (endp l)
(cons e '())
(if (< e (car l))
(cons e l)
(cons (car l) (insert-elem (cdr l) e)))))
66. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակը՝ կարգավորված ըստ տարրերի արժեքների աճման:
(defun insertion-sort (x)
(if (endp l)
'()
(insert-elem (insertion-sort (cdr x)) (car x))))
67. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակը՝ կարգավորված ըստ տարրերի արժեքների նվազման:
(defun sort-desc (x)
(rev-list (insertion-sort x)))
68. Սահմանել ֆունկցիա, որը հեռացնում է տրված ցուցակի վերջին տարրը:
(defun rem-last (x)
(if (or (endp x) (endp (cdr x)))
'()
(cons (car x) (rem-last (cdr x)))))
69. Սահմանել ֆունկցիա, որը հեռացնում է տրված ցուցակում առաջին զույգ թվին հաջորդող տարրը:
(defun rem-next-to-even (x)
(cond
((endp x) '())
((evenp (car x)) (cons (car x) (cddr x)))
(t (cons (car x) (rem-next-to-even (cdr x))))))
70. Սահմանել ֆունկցիա, որը տրված ցուցակում
բոլոր կենտ թվերը փոխարինում է իրենց քառակուսով:
(defun odd-to-sqr (x)
(if (endp x)
'()
(let ((a (car x)) (d (cdr x)))
(cons (if (oddp a) (* a a) a) (odd-to-sqr d)))))
71. Սահմանել ֆունկցիա, որը տրված ցուցակում
բոլոր զույգ դիրքերում կանգնած \(a\)-երը
փոխարինում է \(b\)-երով:
(defun ex71 (x a b)
(if (or (endp x) (endp (cdr x)))
'()
(cons (car x)
(cons (if (equal (cadr x) a) b (cadr x))
(ex71 (cddr x) a b)))))
72. Սահմանել ֆունկցիա, որը սիմվոլների \(x\)
գծային ցուցակում \(y\) սիմվոլի բոլոր մուտքերը
պատճենում է:
(defun ex72 (x y)
(if (endp x)
'()
(if (equal (car x) y)
(append (list y y) (ex72 (cdr x) y))
(cons (car x) (ex72 (cdr x) y)))))
73. Սահմանել պրեդիկատ, որը ստուգում է արդյոք տրված
ցուցակը կազմված է
nil-ից տարբեր ատոմներից:
(defun no-nils (x)
(if (endp x)
t
(and (not (null (car x)))
(no-nils (cdr x)))))
74. Սահմանել ֆունկցիա, որը սիմվոլներից կազմված
\(x\) գծային ցուցակում բոլոր
a-երը
փոխարինում է
b-երով:
(defun ex74 (x a b)
(if (endp x)
'()
(cons (if (eq (car x) a) b (car x))
(ex74 (cdr x) a b))))
75. Սահմանել պրեդիկատ, որը ստուգում է տրված
ցուցակի գծային լինելը:
(defun linear-p (x)
(if (endp x)
t
(and (atom (car x)) (linear-p (cdr x)))))
76. Սահմանել ֆունկցիա, որը տրված \(x\) գծային
ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (((c) b) a)
(defun ex76 (x)
(cond
((endp x) (print x) '())
((endp (cdr x)) (cons (car x) '()))
(t (list (ex76 (cdr x)) (car x)))))
77. Սահմանել ֆունկցիա, որը տրված \(x\) գծային
ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (a (b (c)))
(defun ex77 (x)
(cond
((endp x) (print x) '())
((endp (cdr x)) (cons (car x) '()))
(t (list (car x) (ex77 (cdr x))))))
78. Սահմանել ֆունկցիա, որը տրված \(x\) գծային
ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (((a) b) c)
(defun ex78 (x)
(ex76 (reverse x)))
79. Սահմանել ֆունկցիա, որը տրված \(x\) գծային
ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(((a) b) c) -> (a b c)
(defun ex79 (x)
(if (atom x)
(cons x '())
(append (ex79 (car x)) (cdr x))))
80. Սահմանել ֆունկցիա, որը տրված \(x\) և
\(y\) գծային ցուցակներից ստանում է նոր ցուցակ
հետևյալ կերպ.
(a b c),(1 2 3) -> ((a 1)(b 2)(c 3))
(defun zip (x y)
(if (or (endp x) (endp y))
'()
(cons (list (car x) (car y))
(zip (cdr x) (cdr y)))))
81. Սահմանել ֆունկցիա, որը տրված \(x\) գծային
ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c d e f) -> ((a b)(c d)(e f))
(a b c d e) -> ((a b)(c d)(e nil))
(defun zip-2 (x)
(if (endp x)
'()
(cons (list (car x) (cadr x))
(zip-2 (cddr x)))))
82. Սահմանել ֆունկցիա, որը վերադարձնում է \(x\)
ցուցակի խորությունը:
(defun depth-1 (x)
(if (or (not (listp x)) (null x))
0
(1+ (apply #'max (mapcar #'depth-1 x)))))
83. Սահմանել ֆունկցիա, որը վերադարձնում է \(x\)
ոչ գծային ցուցակի խորությունը:
(defun depth-2 (x)
(if (atom x)
0
(1+ (apply #'max (mapcar #'depth-2 x)))))
84. Սահմանել տրված ցուցակի սիմետրիկությունը ստուգող պրեդիկատ:
(defun palindrome-p (x)
(equal (reverse x) x))
(defun palindrome-p-2 (x) (print x)
(if (or (endp x) (endp (cdr x)))
t
(and (equal (first x) (car (last x)))
(palindrome-p-2 (butlast (cdr x))))))
85. Սահմանել պրեդիկատ, որը ստուգում է արդյոք \(x\) ցուցակը \(y\) ցուցակի սկիզբն է:
(defun prefix-p (x y)
(if (endp y)
t
(and (equal (car x) (car y))
(prefix-p (cdr x) (cdr y)))))
86. Սահմանել ֆունկցիա, որը տրված \(x\) ցուցակի սկզբից հեռացնում է \(y\) ցուցակին համապատասխանող տարրերը:
(defun ex86 (x y)
(if (prefix-p x y)
(nthcdr (list-length y) x)
x))
87. Սահմանել պրեդիկատ, որը ստուգում է արդյոք տրված \(x\) ցուցակը \(y\) ցուցակի իտերացիան է:
(defun ex87 (x y)
(if (equal x y)
t
(if (prefix-p x y)
(ex87 (nthcdr (list-length y) x) y)
nil)))
88. Սահմանել ֆունկցիա, որն արգումենտում ստանում է ինֆիքսային տեսքով գրված արտահայտություն (ցուցակի տեսքով, առանց հաշվի առնելու գործողությունների առաջայնությունը, բոլոր գործողություները երկտեղանի են) և վերադարձնում է նրա արժեքը:
((-2 + 4) * 3) -> 6
(-2 + (4 * 3)) -> 10
((-2 > 0) and (3 < 5)) -> t
-2 -> -2
(defun calc (x)
(flet
((func-op (op)
(case op
((and) #'(lambda (a b) (and a b)))
((or) #'(lambda (a b) (or a b)))
(t op))))
(if (atom x)
x
(funcall (func-op (second x))
(calc (first x))
(calc (third x))))))
89. Սահմանել
is-in պրեդիկատը, որը
վերադարձնում է
t, եթե
y-ը
x բազմության տարր է: Հակառակ դեպքում
վերադարձնում է
nil:
(defun is-in (y x)
(if (endp x)
nil
(or (equal (car x) y) (is-in y (cdr x)))))
90. Սահմանել
is-set պրեդիկատը,
որը ստուգում է տրված ցուցակի բազմություն լինելը:
(defun is-set (x)
(if (endp x)
t
(and (not (is-in (car x) (cdr x)))
(is-set (cdr x)))))
91. Սահմանել
list-to-set ֆունկցիան, որը
վերադարձնում է տրված գծային ցուցակի տարրերի բազմությունը:
(defun list-to-set (x)
(cond
((endp x) '())
((member (car x) (cdr x)) (list-to-set (cdr x)))
(t (cons (car x) (list-to-set (cdr x))))))
92. Սահմանել
list-set ֆունկցիան, որը
վերադարձնում է տրված ոչգծային ցուցակի տարրերի բազմությունը:
(defun tree-to-set (x)
(labels
((flatten (y)
(cond
((null y) '())
((atom y) (list y))
(t (mapcan #'flatten y)))))
(list-to-set (flatten x))))
93. Սահմանել
set-of-evens ֆունկցիան, որը
վերադարձնում է տրված \(X\) բնական թվերի ցուցակի զույգ
տարրերի բազմությունը:
(defun set-of-evens (x)
(remove-duplicates (remove-if #'oddp x)))
(defun set-of-evens-1 (x)
(if (endp x)
'()
(let ((head (car x))
(tail (set-of-evens-1 (cdr x))))
(if (and (evenp head) (not (member head tail)))
(cons head tail)
tail))))
94. Սահմանել
set-not-zero ֆունկցիան, որը
վերադարձնում է տրված \(X\) բնական թվերի ցուցակի ոչզրոյական
տարրերի բազմությունը:
(defun set-not-zero (x)
(remove-duplicates (remove-if #'zerop x)))
95. Սահմանել
lonion ֆունկցիան, որը
վերադարձնում է տրված երկու բազմությունների միավորումը:
(defun lunion (x y)
(cond
((endp x) y)
((member (car x) y) (lunion (cdr x) y))
(t (cons (car x) (lunion (cdr x) y)))))
96. Սահմանել
union-of-odds ֆունկցիան,
որը վերադարձնում է տրված երկու բազմությունների կենտ տարրերի
ենթաբազմությունների միավորումը:
(defun union-of-odds (x y)
(union (remove-if-not #'oddp x) (remove-if-not #'oddp y)))
97. Սահմանել
lintersection ֆունկցիան,
որը վերադարձնում է տրված երկու բազմությունների հատումը:
(defun lintersection (x y)
(cond
((or (endp x) (endp y)) '())
((member (car x) y) (cons (car x) (lintersection (cdr x) y)))
(t (lintersection (cdr x) y))))
98. Սահմանել ֆունկցիա, որը վերադարձնում է տրված
երկու բազմությունների թիվ հանդիսացող ատոմների հատումը:
(defun ex98 (x y)
(intersection (remove-if-not #'numberp x)
(remove-if-not #'numberp y)))
99. Սահմանել ֆունկցիա, որը վերադարձնում է տրված
երկու բազմությունների տարբերությունը:
(defun ldifference (x y)
(cond
((endp x) '())
((endp y) x)
((member (car x) y) (ldifference (cdr x) y))
(t (cons (car x) (ldifference (cdr x) y)))))
100. Սահմանել ֆունկցիա, որը վերադարձնում է տրված
երկու բազմությունների սիմետրիկ հանումը:
(defun sim-diff (x y)
(set-difference (union x y) (intersection x y)))
101. Սահմանել երկու բազմությունների դեկարտյան
արտադրյալը վերադարձնող ֆունկցիա:
(defun cartesian (x y)
(if (endp x)
'()
(append (mapcar #'(lambda (e) (list (car x) e)) y)
(cartesian (cdr x) y))))
102. Սահմանել պրեդիկատ, որը ստուդում է երկու
բազմությունների հատվող լինելը:
(defun are-intersect (x y)
(if (endp x)
nil
(or (member (car x) y) (are-intersect (cdr x) y))))
(defun are-intersect-2 (x y)
(not (null (intersection x y))))
103. Սահմանել պրեդիկատ, որը ստուդում է երկու
բազմությունների չհատվող լինելը:
(defun are-not-intersect (x y)
(null (intersection x y)))
104. Սահմանել
is-subset ֆունկցիան,
որը ստուգում է. արդյոք տրված \(X\) բազմությանը
\(Y\) բազմության ենթաբազմություն է:
(defun is-subset (x y)
(if (endp x)
t
(and (member (car x) y) (is-subset (cdr x) y))))
105. Սահմանել
is-own-subset ֆունկցիան,
որը ստուգում է. արդյոք տրված \(X\) բազմությանը
\(Y\) բազմության սեփական ենթաբազմություն է:
(defun is-own-subset (x y)
(and (is-subset x y) (> (list-length y) (list-length x))))
