-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathex1.10-ackermann-function.scm
108 lines (93 loc) · 2.97 KB
/
ex1.10-ackermann-function.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
; (A 1 10)
; (A 0 (A 1 9))
; (A 0 (A 0 (A 1 8)))
; (A 0 (A 0 (A 0 (A 1 7))))
; (A 0 (A 0 (A 0 (A 0 (A 1 6)))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8)))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 32)))))
; (A 0 (A 0 (A 0 (A 0 64))))
; (A 0 (A 0 (A 0 128)))
; (A 0 (A 0 256))
; (A 0 512)
; 1024
;Recap
; (A 1 n) ;-> 2^n
; (A 2 4)
; (A 1 (A 2 3))
; (A 1 (A 1 (A 2 2)))
; (A 1 (A 1 (A 1 (A 2 1))))
; (A 1 (A 1 (A 1 2)))
; (A 1 (A 1 (A 0 (A 1 1))))
; (A 1 (A 1 (A 0 2)))
; (A 1 (A 1 (* 2 2)))
; (A 1 (A 1 4))
; (A 1 (A 0 (A 1 3)))
; (A 1 (A 0 (A 0 (A 1 2))))
; (A 1 (A 0 (A 0 (A 0 (A 1 1)))))
; (A 1 (A 0 (A 0 (A 0 2))))
; (A 1 (A 0 (A 0 (* 2 2))))
; (A 1 (A 0 (A 0 4)))
; (A 1 (A 0 8))
; (A 1 16) ; -> 2^16: 65536
; recap
; (A 2 4)
; (A 1 (A 1 (A 1 (A 2 1))))
; (A 1 (A 1 (A 1 2))); -> 2^(2^(2^2)) -> 2^(2^4) -> 2^16
; (A 2 n) ;-> 2^(2^(2^2))
; ; | n times |
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
; (A 3 3)
; (A 2 (A 3 2))
; (A 2 (A 2 (A 3 1)))
; (A 2 (A 2 2)) ;-> 2^[(2^2)]
; (A 2 4) ;-> 2^(2^(2^2))
; (A 3 5)
; (A 2 (A 3 4))
; (A 2 (A 2 (A 3 3)))
; (A 2 (A 2 (A 2 (A 3 2))))
; (A 2 (A 2 (A 2 (A 2 (A 3 1)))))
; (A 2 (A 2 (A 2 (A 2 2))))
; (A 2 (A 2 (A 2 4)))
; (A 2 (A 2 65536))
; (A 2 )
; recap
; (A 3 n) ;-> (A 2 (A 2 ... (A 2 2) ...))
; | n times |
; _
; ;-> 2^2 |
; |2| -> 4 |
; ;-> 2^(2^(2^2)) |
; | 4 | -> 65536 n-1 times
; ;-> 2^(2^ ...(2^2)) |
; | 65536 | -> too big |
; . |
; . |
; . -
(define (f n) (A 0 n)) ;-> 2n
(define (g n) (A 1 n)) ;-> 2^n
(define (h n) (A 2 n)) ;
; (A 2 n) ;-> 2^(2^(2^2))
; | n times |
(define (k n) (* 5 n n)); 5n^2