하노이 타워

#lang racket
(define (hanoitower disc src aux dst)
  (cond
    [(> disc 0)
     (hanoitower (- disc 1) src dst aux)
     (displayln (format "Move ~s from ~s to ~s"disc src dst))
     (hanoitower (- disc 1) aux src dst)]))

(hanoitower 3 1 2 3)

언어별 나머지

나머지 구하기
scheme : remainder

erlang : rem

clisp : rem

몫 구하기

erlang : / 실수형
           div 정수형

clisp  : 정수 / 정수 :  분수
           정수 / 실수 or 실수 / 정수 : 실수

원주율 구하기

#lang racket
;; 라이프니츠의 공식
(define (findpi current result add)
   (cond ((> current 10000000) (* 4 result))
         (else
          (cond ((equal? + add) (findpi (+ current 2) (+ result (/ 1 (+ current 2))) -))
                ((equal? - add) (findpi (+ current 2) (- result (/ 1 (+ current 2))) +))))))

;; 오일러의 식 
(define (findpi2 current result)
   (cond ((> current 10000000) (sqrt (* 6 result)))
         (else (findpi2 (+ current 1) (+ result (/ 1 (* current current)))) )))

[sicp] 1.17, 1.18

#lang scheme
(define (even? n)
  (= (remainder n 2) 0))

(define (double a )
   (double-iter a 2 0))

(define (double-iter a counter product)
  (if (= counter 0)
      product
      (double-iter a (- counter 1) (+ a product))))

(define (mod a div)
  (- (/ a div) (/ 1 div)))

;; 1.18
(define (fast-multi-iter a counter product result )
  (cond ((= counter 1) (+ product  result ) )
        (( even? counter) (fast-multi-iter a (/ counter 2)  (double product) result ))
        (else (fast-multi-iter a (mod counter 2) (double product) (+ result product ) ) )))
 
(define (* a b)
  (fast-multi-iter a b a 0 )
  )

 

 

 

;; 1.17
(define (fast-multi b n)
  (cond ((= n 0) 0)
        ((even? n) (double (fast-multi b (/ n 2))))
        (else (+ b (fast-multi b (- n 1))))))

 

ps. 1.18 을 답을 보니 나만 틀렸네 ㅡㅡ

잘못된 방법으로 풀었음 .

역시 난 ㅠㅠ

영어 어려워서 책 질렀음

[sicp] 1.16

;;; sicp 1.16
#lang scheme
(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-expt-iter b counter product)
  (if (= counter 0)
      product
     (if (even? counter)
         (fast-expt-iter b
                (/ counter 2)
                (* b  product product))
         (fast-expt-iter b
                (- counter 1)
                (* b product))
          )
         ))
(define (fast-expt b n)
 (fast-expt-iter b n 1))

(fast-expt 2 16)

 

이것도 들렸다 ㅠㅠ

[sicp] 1.13

Exercise 1.13.  Prove that Fib(n) is the closest integer to ⁿ/5, where = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (ⁿ - ⁿ)/5.
0 1 1 2 3 5 8
fin n = 1  ((1+ 5)/2 - (1-5)/2 )/5 => 5/5 => 1
fin n = 2  (((1+ 5)/2)^2 - ((1-5)/2 )^2)/5
=> ( (1+ 5)/2 - (1-5)/2 )( (1+ 5)/2 + (1-5)/2 ) ) /5
=> 5/5 => 1

#lang scheme
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define A
 (/   (+ 1 (expt 5 0.5))
     2))

(define B
 (/   (- 1 (expt 5 0.5))
     2))

(define (fib2 n)
 (/ (- (expt A n)
    (expt B n))
   (expt 5 0.5)))

(fib2 1) = 1.0
(fib 1) = 1
(fib2 2) = 1.0
(fib 2) = 1
(fib2 3) = 2.0
(fib 3) = 2
...
(fib2 40) = 102334155.00000013
(fib 40) = 102334155
(fib2 50) = 12586269025.00002
(fib 50) = 12586269025
...
(fib2 60) = 1548008755920.003
(fib 60) =1548008755920
(fib2 70) = 190392490709135.44
(fib 70) = 190392490709135

(fib2 80) = 23416728348467744.0
(fib 80) = 23416728348467685

70까지는 거의 근접하고 1~ 3까지는 확실히 똑같다. 3 이후부터는 소수점이 많이 늘어난다.

[sicp] 1.12

Exercise 1.12.  The following pattern of numbers is called Pascal's triangle.

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.³⁵ Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

#lang scheme
(define (pascal_triangle a b )
  (cond
       ((= a b) 1)
        ((= a 2) 1)
         ((= b 1) 1)
       (else (+ (pascal_triangle (- a 1) (- b 2))
               (pascal_triangle (- a 1) (- b 1))))))

--------------------------------------------------------------------------------

;;; sicp 1.12
#lang scheme
(define (pascal_triangle a b )
  (cond
       ((< a b) '틀렸음)
       ((= a b) 1)
         ((= b 1) 1)
       (else (+ (pascal_triangle (- a 1) (- b 1))
               (pascal_triangle (- a 1) b)))))

 

수정함

[sicp] 1.11

Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

- recursive process
#lang scheme

(define (f n)
  (cond ((= n 0) 0)
       ((= n 1) 1)
       ((= n 2) 2)
       (else (+ (f (- n 1))
               (* 2 (f (- n 2)))
               (* 3 (f (- n 3)))) ) ) )

- iterative process
#lang scheme

(define (f-iter a b c count)
   (if (= count 0)
     c
        (f-iter (+ a (* 2 b) (* 3 c) )
               a   b  (- count 1) ) ) )
    
(define (f n )
(f-iter 2 1 0 n) )

[sicp] 1.9

1.9

첫번째 : iterative

a : counter

b : product

a가 1 감소할때마다 b는 1씩 증가해서 a가 0이 되면 b는 결과 출력

[code] #lang scheme (define ( inc a ) (- a -1)) (define (dec a) (- a 1)) (define (+ a b) (if (= a 0) b (+ (dec a) (inc b)))) (+ 4 5) [/code]
erlang 버젼
[code] -module(iterative). -export([inc/1,dec/1,plus/2]). inc(A)->A+1. dec(A)->A-1. plus(0,B) -> B; plus(A,B)-> plus(dec(A),inc(B)). [/code]
두번째 : recursive

전형적인 재귀
a가 1씩 감소할떄마다 재귀호출를 1번씩 해서 총 a가 감소만 만큼 재귀호출한 후에
a만큼 다시 더하는 방식

[code] #lang scheme (define ( inc a ) (- a -1)) (define (dec a) (- a 1)) (define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (+ 4 5) [/code]