Script Programming(스크립트 프로그래밍)

아래는 GNU CLisp 로 실행한 것인데. Clozure CL 로 실행해도 거의 같은 결과를 얻는다.

다항식 p(x) 를 1차 다항식 ax - b 로 나눌 때의 몫과 나머지를 구하는 조립제법을
Python 언어로 구현해 보았다. 조립제법은 일명 Horner의 방법이라고도 불리우는데, 이는
x = a 에서 다항식 p(x)의 값 p(a)을 계산하는 가장 빠른 알고리즘이기도 하다.

         p(x) = (ax - b)q(x) + r

여기서 r은 나머지이며 r = p(b/a) 이다. 또 q(x)는 몫이다.

[참고]
    * 온라인으로 조립제법 표 만들기 손으로 계산하는 조립제법 표 
    * 온라인으로 구하는 다항식의 도함수: 조립제법을 이용한 다항식의 도함수


아래의 소스파일은 이전에 작성했던 파일 testSyntheticDivision.lsp 를 수정한 것이다.

1. ;;  Filename: testSyntheticDivision2.lsp
2. ;;
3. ;;  Purpose:  Find the quotient and remainder when some polynomial is
4. ;;            divided by a monic polynomial of the first degree.
5. ;;
6. ;;  Execute:  clisp testSyntheticDivision2.lsp 5 -4 7 8 6 8
7. ;;
8. ;;  Date: 2013. 9. 7.
11. ;; 사용법 표시
12. (defun printUsage()
13.     (format t "사용법: clisp testSyntheticDivision2.lsp [제식의 계수] [피제식의 계수들]~%")
14.     (format t "조립제법(synthetic method)에 의한 다항식 나눗셈 결과를 보여준다.~%")
15. )
17. ;; 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
18. ;; 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
19. (defun simplify(v &optional width)
20.     (let* ((tt "")
21.            (slen 0))
22.         (setf tt (format nil "~A" v))
23.         (setf slen (length tt))
24.         (if (and (>= slen 2) (string= (substring tt (- slen 2) slen) ".0"))
25.             (setf tt (substring tt 0 (- slen 2))) )
26.         (setf slen (length tt))
27.         (if width
28.             (if (< slen width)
29.                 (setf tt (concatenate 'string (make-string (- width slen) :initial-element #\Space) tt)) ))
30.         tt
31.     )
32. )
34. ;; "/수" 표시하기
35. ;; 부동소수점수의 표현이 .0 으로 끝나는 경우 이를 잘라낸다.
36. ;; 전체 문자열 표시 너비는 매개변수 width 로 전달받아 처리한다.
37. (defun simplifyReciprocal(v &optional width)
38.     (let* ((tt "")
39.            (tlen 0))
40.         (setf tt (format nil "/~A" v))
41.         (setf tlen (length tt))
42.         (if (and (>= tlen 2) (string= (substring tt (- tlen 2) tlen) ".0"))
43.             (setf tt (substring tt 0 (- tlen 2))) )
44.         (setf tlen (length tt))
45.         (if width
46.             (if (< tlen width)
47.                 (setf tt (concatenate 'string (make-string (- width tlen) :initial-element #\Space) tt)) ))
48.         tt
49.     )
50. )
52. ;; 다항식을 내림차순의 스트링 표현으로 반환
53. (defun toPolyString(c)
54.     (let* ((ttt "")
55.            (sc0 "")
56.            (sc "")
57.            (k 0))
58.         (setf ttt "")
59.         (setf sc0 (simplify (nth 0 c) nil ))
60.         (if (> (length c) 2)
61.             (cond
62.                ((string= sc0 "1") (setf ttt (concatenate 'string ttt (format nil "x^~D" (- (length c) 1)))))
63.                ((string= sc0 "-1") (setf ttt (concatenate 'string ttt (format nil "-x^~D" (- (length c) 1)))))
64.                (t (setf ttt (concatenate 'string ttt sc0 (format nil " x^~D" (- (length c) 1)))))
65.             )
66.         )
68.         (if (= (length c) 2)
69.             (cond
70.                ((string= sc0 "1") (setf ttt (concatenate 'string ttt "x")))
71.                ((string= sc0 "-1") (setf ttt (concatenate 'string ttt "-x")))
72.                (t (setf ttt (concatenate 'string ttt sc0 " x")))
73.             )
74.         )
75.         (if (= (length c) 1)
76.                (setf ttt (concatenate 'string ttt sc0))
77.         )
79.         (loop for i from 1 below (length c) do
80.             (setf k (- (length c) 1 i))
81.             (setf sc (simplify (nth i c) nil))
82.             (if (> k 1) (progn
83.                 (cond
84.                     ((> (nth i c) 0.0)
85.                         (if (string= sc "1")
86.                             (setf ttt (concatenate 'string ttt " + " (format nil "x^~D" k)))
87.                             (setf ttt (concatenate 'string ttt " + " sc (format nil " x^~D" k)))
88.                         ) )
89.                     ((< (nth i c) 0.0)
90.                         (if (string= sc "-1")
91.                             (setf ttt (concatenate 'string ttt " - " (format nil "x^~D" k)))
92.                             (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c)) nil) (format nil " x^~D" k)))
93.                         ) )
94.                     )
95.                 )
96.             )
98.             (if (= k 1)
99.                 (cond
100.                     ((> (nth i c) 0.0)
101.                         (if (string= sc "1")
102.                             (setf ttt (concatenate 'string ttt " + " "x"))
103.                             (setf ttt (concatenate 'string ttt " + " sc " x"))
104.                         ) )
105.                     ((< (nth i c) 0.0)
106.                         (if (string= sc "-1")
107.                             (setf ttt (concatenate 'string ttt " - " "x"))
108.                             (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c))) " x"))
109.                         ) )
110.                 )
111.             )
112.             (if (= k 0)
113.                 (cond
114.                     ( (> (nth i c) 0.0) (setf ttt (concatenate 'string ttt " + " sc)) )
115.                     ( (< (nth i c) 0.0) (setf ttt (concatenate 'string ttt " - " (simplify (abs (nth i c))) )) )
116.                 )
117.             )
118.         )
119.         ttt
120.     )
121. )
124. ;; 다항식 나눗셈 결과를
125. ;;     (피제식) = (제식)(몫) + (나머지)
126. ;; 형태로 출력
127. (defun printDivisionResult(a c d b)
128.     (let* ((strLine ""))
129.         (setf strLine (concatenate 'string "  " (toPolyString c)))
130.         (format t "~A~%" strLine)
131.         (setf strLine (concatenate 'string "    = ( " (toPolyString (list (nth 0 a) (- (nth 1 a)))) " )"))
132.         (setf tmp (make-list (- (length b) 1) :initial-element 0.0)) 
133.         (loop for i from 0 below (length tmp) do
134.             (setf (nth i tmp) (nth i b)) )
135.         (setf strLine (concatenate 'string strLine "( " (toPolyString tmp) " )"))
136.         (setf r (nth (- (length d) 1) d))
137.         (cond
138.            ((> r 0.0)  (setf strLine (concatenate 'string strLine " + " (simplify r nil) )))
139.            ((< r 0.0)  (setf strLine (concatenate 'string strLine " - " (simplify (abs r) nil) )))
140.         )
141.         (format t "~A~%" strLine)
142.     )
143. )
146. ;; 조립제법 계산표 출력 함수
147. (defun printSyntheticTable(a c s d q)
148.     (let* ((strLine ""))
149.         (setf strLine "         | ")
150.         (setf strLine (concatenate 'string strLine (simplify (nth 0 c) 10) ))
152.         (loop for i from 1 below (length c) do
153.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i c) 10) )))
154.         (format t "~A~%" strLine)
156.         (setf strLine (concatenate 'string (simplify (nth 1 a) 8) " |"))
157.         (setf strLine (concatenate 'string strLine "             "))
158.         (setf strLine (concatenate 'string strLine (simplify (nth 1 s) 10)))
159.         (loop for i from 2 below (length s) do
160.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i s) 10) )))
161.         (format t "~A~%" strLine)
163.         (setf strLine "         |")
164.         (loop for i from 0 below (length q) do
165.             (setf strLine (concatenate 'string strLine "------------")))
166.         (format t "~A~%" strLine)
168.         (setf strLine "         | ")
169.         (setf strLine (concatenate 'string strLine (simplify (nth 0 d) 10)))
170.         (loop for i from 1 below (length d) do
171.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i d) 10))))
172.         (format t "~A~%" strLine)
174.         (setf strLine (concatenate 'string (simplifyReciprocal (nth 0 a) 8) " | "))
175.         (setf strLine (concatenate 'string strLine (simplify (nth 0 q) 10)))
176.         (loop for i from 1 below (1- (length q)) do
177.             (setf strLine (concatenate 'string strLine "  " (simplify (nth i q) 10) )))
178.         (format t "~A~%" strLine)
179.     )
180. )
182. ;; 실행 시작 지점
183. (if (< (length ext:*args*) 3) (progn
184.     (printUsage)
185.     (quit) ))
187. ;; ----------------------------------------------------
188. ;; 피제식은 c_0 x^n +  c_1 x^(n -1) + ... + c_n
189. ;; 제식은 a x -  b
190. (setf a (list (read-from-string (nth 0 ext:*args*)) (- (read-from-string (nth 1 ext:*args*)))) )
191. (setf c (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
192. (setf s (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
193. (setf d (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
194. (setf b (make-list (- (length ext:*args*) 2) :initial-element 0.0) )
196. (loop for i from 0 below (length c) do
197.     (setf (nth i c) (read-from-string (nth (+ i 2) ext:*args*))))
199. ;; ----------------------------------------------------
200. ;; 조립제법의 주요 부분
201. (setf (nth 0 s) 0.0)
202. (setf (nth 0 d) (nth 0 c))
203. (setf (nth 0 b)  (+ 0.0 (/ (nth 0 c) (nth 0 a))))
204. (loop for i from 1 below (length c) do
205.     (setf (nth i s) (* (nth (- i 1) b) (nth 1 a)))
206.     (setf (nth i d) (+ (nth i c) (nth i s)))
207.     (setf (nth i b) (+ 0.0 (/ (nth i d) (nth 0 a)))) )
209. ;; ----------------------------------------------------
210. ;; 몫의 계수와 나머지를 출력한다.
211. (format t "몫의 계수는 ")
212. (loop for i from 0 below (- (length b) 2) do
213.     (format t (concatenate 'string (simplify (nth i b)) ",  ")))
214. (format t (concatenate 'string (simplify (nth (- (length b) 2) b)) " "))
215. (format t (concatenate 'string "이고, 나머지는 " (simplify (nth (- (length d) 1) d)) " 이다.~%"))
216. (terpri)
218. ;; ----------------------------------------------------
219. ;; 조립제법 표를 출력한다.
220. (printSyntheticTable a c s d b)
221. (terpri)
223. ;; ----------------------------------------------------
224. ;; (피제식) = (제식) x (몫) + (나머지)
225. (printDivisionResult a c d b)
226. (format t "~%")

실행> clisp testSyntheticDivision2.lsp 5 -4 7 8 6 8

Common Lisp 언어로 숫자 맞추기 게임을 작성해 보았다.

아래 소스의 18째 줄 (setf guess (parse-integer sbuf)) 는 스트링을 정수로 변환하는 과정이다.



소스 파일명: guessNumber01.lsp

1. #!/usr/bin/env clisp
3. ;;   Filename: guessNumber01.lsp
4. ;;   Purpose:  Interatice game guessing a given number.
5. ;;                 (if condition
6. ;;                     (........)    ; when condition is true
7. ;;                     (........)    ; when condition is flase
8. ;;                 )
9. ;;   Execute: clisp guessNumber01.lsp
10. ;;                     ......
11. ;;   Date: 2013. 9. 7.
13. (defun doGuessing(num)
14.     (let* ((sbuf "")
15.            (guess 0))
16.         (format t "Enter your guess:~%")
17.         (setf sbuf (read-line))
18.         (setf guess (parse-integer sbuf))
19.         (if (= guess num)
20.             (progn
21.                 (format t "You win!~%")
22.                 (quit)
23.             )
24.         )
26.         ;; we won't get here if (= guessnum)
27.         (if (< guess num)
28.             (progn
29.                 (format t "Too low!~%")
30.                 (doGuessing num)
31.             )
32.             (progn
33.                 (format t "Too high!~%")
34.                 (doGuessing num)
35.             )
36.         )
37.     )
38. )
40. (doGuessing 123)

실행> clisp guessNumber01.lsp
Enter your guess:
111
Too low!
Enter your guess:
222
Too high!
Enter your guess:
123
You win!

[파일명:  testStringFindInList.lsp]------------------------------------------------
(defun my-find(arr s)
    (let ((k -1)
          (r -1))
        (loop for i from 0 below (length arr) do
            (setf k (search s (nth i arr)))
            (if k (progn (setf r i) (return i)))
        )
        r
    )
)

(defun printList(arr)
    (format t "[")
    (loop for i from 0 below (1- (length arr)) do
        (format t "~A, " (nth i arr))
    )
    (if (plusp (length arr))
        (format t "~A" (nth (1- (length arr)) arr))
    )
    (format t "]~%")
)

(setf words (list "하나" "둘" "셋" "넷" "다섯" "여섯"))

(format t "list: ")
(printList words)
(setf w (my-find words "셋"))
(if (>= w 0)
    (progn
        (format t "발견!  ~%")
        (format t "Next word of 셋 in list: ~A~%" (nth (1+ w) words))
    )
)

(format t "Sorting...~%")
(sort words #'string<)

(format t "list: ")
(printList words)
(setf w (my-find words "셋"))
(if (>= w 0)
    (progn
        (format t "발견!  ~%")
        (format t "Next word of 셋 in list: ~A~%" (nth (1+ w) words))
    )
)
------------------------------------------------


실행> clisp testStringFindInList.lsp
list: [하나, 둘, 셋, 넷, 다섯, 여섯]
발견!  Next word of 셋 in list: 넷
Sorting...
list: [넷, 다섯, 둘, 셋, 여섯, 하나]
발견!  Next word of 셋 in list: 여섯

[파일명:  testSort.lsp]------------------------------------------------
(defun printArray(a)
    (format t "[")
    (loop for i from 0 below (1- (length a)) do
        (format t "~A, " (nth i a))
    )
    (if (plusp (length a))
        (format t "~A" (nth (1- (length a)) a))
    )
    (format t "]~%")
)

(setf list ext:*args*)
(sort list #'string<)
(printArray list)
------------------------------------------------


실행> clisp testSort.lsp one two three four five
[five, four, one, three, two]

실행> clisp testSort.lsp 하나 둘 셋 넷 다섯
[넷, 다섯, 둘, 셋, 하나]

정의 (소수와 합성수)
    1보다 큰 양의 정수 n에 대하여
    (i) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하면,
        n을 합성수(合成數, composite number)라고 한다. 참고로 이 경우,
        a, b 중에 적어도 하나는 sqrt(n) 보다 작거나 같다.
        합성수의 예로는 4, 6, 9, 24, 143 등이 있다.
    (ii) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하지 않으면,
         즉 n을 두 양의 정수의 곱으로 표현하는 방법이 1*n과 n*1 두 가지 뿐이면,
         n을 소수(素數, prime number)라고 한다.  소수의 예로는 2, 3, 5, 7, 11 등이 있다.
         n이 소수인지 아닌지 확인하려면, 
         n을 2 보다 크거나 같고 sqrt(n) 보다 작거나 같은 모든 정수로 나누어 본다.
         이 경우 언제나 나누어 떨어지지  않으면 n은 소수이고, 그렇지 않으면 n은 합성수이다.
    

우선 다음의 Common Lisp 소스 코드는 명령행 인자로 전달 받은 양의 정수 n을
2 및 3, 5, 7, ... , (sqrt n) 이하의 홀수들로 나누어 보아 n이 합성수인지 아닌지
확인하는 애플리케이션 소스이다. 확인하는데 걸린 경과 시간도 알려준다.

이제 다음은 정수의 인수분해 능력이 뛰어난  Pollard의 rho 방법(일명 거북이와 토끼 알고리즘, tortoise-hair algorithm)을 구현한  Common Lisp 소스 코드이다. 이 알고리즘은 소수에 대해서는 시간이 많이 걸리지만, 합성수에 대해서는 시간이 매우 적게 걸린다는 것이 특징이다.

 

초등학교 때 배우는 두 정수의 곱셈표를 만들어 주는 Common Lisp 소스이다.
(이 소스는 CLisp으로 잘 실행됨을 확인하였다.)

Common Lisp 언어로, 양의 정수 a를 양의 정수 b로 나는 몫을 구하려면

        (setf q (floor (/ a b)))

한다. 그 몫은 변수 q에 저장된다. 이렇게 하는 이유는

        (setf q (/ a b))

로 한 경우 q에는 분수 a/b가 저장되기 때문이다.

실행> clisp makeMultTable.lsp 230 5100
결과>

         230
   x )   5100
     ------
         23
       115
     ------
       1173000

다음은 초등학교에서 배우는 나눗셈 계산표를 만들어주는 Common Lisp 소스 코드이다.
나눗셈 계산표를 완성하고 나서 약수, 배수 관계를 알려준다.

아래의 소스는 CLisp으로 실행되도록 작성되었다.

1. #!/usr/bin/env clisp
3. ;;  Filename: makeDivisionTable.lsp
4. ;;
5. ;;  Purpose:  Make a division table in a handy written form.
6. ;;
7. ;;  Execute: clisp makeDivisionTable.lsp 12345 32
8. ;;           clisp makeDivisionTable.lsp 500210 61
9. ;;           ./makeDivisionTable.lsp 500210 61
10. ;;
11. ;;     Date:  2013, 9. 5.
13. (defun printUsage()
14.     (format t "사용법: clisp makeDivisionTable.lsp [피제수] [제수]~%")
15.     (format t "손으로 작성한 형태의 나눗셈 표를 만들어준다.~%") )
17. (defun simplify(v &optional width)
18.     (let* ((tt "")
19.            (slen 0))
20.         (setf tt (format nil "~A" v))
21.         (setf slen (length tt))
22.         (if (and (>= slen 2) (string= (substring tt (- slen 2) slen) ".0"))
23.             (setf tt (substring tt 0 (- slen 2))) )
24.         (setf slen (length tt))
25.         (if width
26.             (if (< slen width)
27.                 (setf tt (concatenate 'string (make-string (- width slen) :initial-element #\Space) tt)) ))
28.         tt
29.     )
30. )
32. (defun getSuffix(v)
33.     (let* ((tt (mod (abs v) 10))
34.            (suffix "은"))
35.         (if (search (format nil "~A" tt) "2459")
36.             (setf suffix "는") )
37.         suffix
38.     )
39. )
41. (defun makeTable(numer denom quotient)
42.     (let* ((strNumer (format nil "~A" numer))
43.            (strDenom (format nil "~A" denom))
44.            (strQuotient (format nil "~A" quotient))
45.            (lenN (length strNumer))
46.            (lenD (length strDenom))
47.            (lenQ (length strQuotient))
48.            (offsetLeft (+ 3 lenD 3))
49.            (spaces (make-string 100 :initial-element #\Space))
50.            (uline (make-string (+ lenN 2) :initial-element #\_))
51.            (sline (make-string lenN :initial-element #\-))
52.            (bias (- lenN lenQ))
53.            (strTmpR (substring strNumer 0 (+ bias 1)))
54.            (tmpR (parse-integer strTmpR))
55.            (tmpSub 0)
56.            (oneDigit nil) )
58.         (format t "~A~A~A~%" (substring spaces 0 offsetLeft) (substring spaces 0 bias) (format nil "~D" quotient))
59.         (format t "~A~A~%" (substring spaces 0 (- offsetLeft 2)) uline)
60.         (format t "~A~A~A~A" "   " strDenom " ) " strNumer)
62.         (loop for i from 0 below lenQ do
63.             (if (string= (substring strQuotient i (1+ i)) "0")
64.                 (progn
65.                     (if (< (1+ i) lenQ)
66.                         (progn
67.                            (setf oneDigit (substring strNumer (+ bias i 1) (+ bias i 2)))
68.                            (format t "~A" oneDigit)
69.                            (setf strTmpR (concatenate 'string strTmpR oneDigit))
70.                            (setf tmpR (parse-integer strTmpR))
71.                         )
72.                     )
73.                 )
74.                 (progn
75.                     (format t "~%")
76.                     (setf tmpSub (* (parse-integer (substring strQuotient i (1+ i))) denom))
77.                     (format t "~A~A~%" (substring spaces 0 offsetLeft) (simplify tmpSub (+ bias i 1)))
78.                     (format t "~A~A~%" (substring spaces 0 offsetLeft) sline)
79.                     (setf tmpR (- tmpR tmpSub))
80.                     (if (and (= tmpR 0) (< (+ i 1) lenQ))
81.                         (format t "~A~A" (substring spaces 0 offsetLeft) (substring spaces 0 (+ bias i 1)))
82.                         (format t "~A~A" (substring spaces 0 offsetLeft) (simplify tmpR (+ bias i 1)))
83.                     ) 
85.                     (setf strTmpR (format nil "~D" tmpR)) 
86.                     (if (< (+ i 1) lenQ)
87.                         (progn
88.                             (setf oneDigit (substring strNumer (+ bias i 1) (+ bias i 2)))
89.                             (if (plusp (length oneDigit))
90.                                 (progn
91.                                     (format t "~A" oneDigit)
92.                                     (setf strTmpR (concatenate 'string strTmpR oneDigit))
93.                                 )
94.                             )
95.                             (setf tmpR (parse-integer strTmpR))
96.                         )
97.                     )
98.                 )
99.             )
100.         )
101.         tmpR
102.     )
103. )
106. ;; Begin here
107. (if (< (length ext:*args*) 2)
108.     (progn
109.         (printUsage)
110.         (quit)
111.     )
112. )
115. (setf a nil)
116. (setf b nil)
118. (handler-case
119.     (progn
120.         (setf a (parse-integer (nth 0 ext:*args*)))
121.         (setf b (parse-integer (nth 1 ext:*args*)))
122.         (if (minusp a)
123.             (progn
124.                 (format t "피제수: ~A~%" a)
125.                 (format t "피제수는 양의 정수라야 합니다.~%")
126.                 (quit)
127.             )
128.             (if (minusp b)
129.                 (progn
130.                     (format t "제수: ~A~%" b)
131.                     (format t "제수는 양의 정수라야 합니다.~%")
132.                     (quit)
133.                 )
134.             )
135.         )
137.         (setf q (floor (/ a b)))
138.         (setf r (mod a b))
140.         (format t "나눗셈 ~A ÷ ~A 의 결과: " a b)
141.         (format t "몫:  ~A, " q)
142.         (format t "나머지: ~A~%" r)
143.         (format t "~%")
145.         (setf k (makeTable a  b q))
146.         (format t "~%")
148.         (if (= k r)
149.             (format t "~%나머지: ~A~%" k)
150.         )
151.         (if (= k 0)
152.             (progn
153.                 (format t "~A = ~A x ~A~%" a b q)
154.                 (format t "~A~A ~A의 배수(mupltiple)이다.~%" a (getSuffix a) b)
155.                 (format t "~A~A ~A의 약수(divisor)이다.~%" b (getSuffix b) a)
156.                 (format t "~%")
157.             )
158.             (progn
159.                 (format t "~A = ~A x ~A + ~A~%" a b q r)
160.                 (format t "~A~A ~A의 배수(mupltiple)가 아니다.~%" a (getSuffix a) b)
161.                 (format t "~%")
162.             )
163.         )
164.     )
166.     (parse-error (c)
167.         (format t "예외상황: ~A" c)
168.         (format t "이 발생였음. 다시 하시오,~%~%")
169.     )
170. )

실행> clisp makeDivisionTable.lsp 500210 61

나눗셈 500210 ÷ 61 의 결과: 몫: 8200, 나머지: 10

          8200
      ________
   61 ) 500210
        488
        ------
         122
         122
        ------
            10

나머지: 10
500210 = 61 x 8200 + 10
500210은 61의 배수(mupltiple)가 아니다.