理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題1.20

(gcd 206 40)
->(gcd 40 (rem 206 40)) ; 1回目
->(gcd (rem 206 40) (rem 40 (rem 206 40))) ; 累積3回目
->(gcd (rem 40 (rem 206 40)) 
       (rem (rem 206 40) (rem 40 (rem 206 40)))) ; 累積7回目
->(gcd (rem (rem 206 40) (rem 40 (rem 206 40)))
       (rem (rem 40 (rem 206 40))
            (rem (rem 206 40) (rem 40 (rem 206 40)))))) ; 累積14回目
->(rem (rem 206 40) (rem 40 (rem 206 40)))) ; 累積18回目

というわけで、正規順序評価だとrem(=remainder)の評価回数は18回になる。


もう一個、作用的順序だと

(gcd 206 40)
->(gcd 40 (rem 206 40))
->(gcd 40 6) ; 1回目
->(gcd 6 (rem 40 6))
->(gcd 6 4)  ; 2回目
->(gcd 4 (rem 6 4))
->(gcd 4 2)  ; 3回目
->(gcd 2 (rem 4 2))
->(gcd 2 0)  ; 4回目
->2

てことなので、4回の評価です。