問題 2.5
まず掛け算についておさらいしておこう。
・偶数と偶数を掛け算したときに、結果は偶数になる?それとも奇数になる? ・奇数と奇数を掛け算したときに、結果は偶数になる?それとも奇数になる?
この2つについてまず見ていこう。
偶数 x 偶数 = 2m * 2n = 4mn = 2 * 2mn
それぞれの偶数を m と n とすると、こんな風に計算できる。
最後に 4mn を 2 * 2mn にしたのはわざとです。
どんな数であっても 2 倍したら、必ず偶数になりますね。
2 * 2mn
この式、2mn の部分がどんな値であっても、2 倍しなければいけないので必ず偶数です。
2mn の部分がどんなに複雑な式になってもこれは変わりません。2 倍しないといけないので偶数にしかなりません。
偶数 x 偶数 = 2m * 2n = 4mn = 2 * 2mn = 偶数
つまり、
偶数 x 偶数 = 偶数
こうです。次は奇数同士の掛け算を考えます。
奇数 x 奇数 = (2m - 1) * (2n - 1) = 4mn - 2m - 2n + 1 = 2 * (2mn - m - n) + 1
奇数は 2 * n - 1 なのはいいよね?
1 は足してもいいけども、偶数 2n を -1 か、もしくは +1 したものが奇数です。
同様に式を計算するんですが、最後に 2 をくくりだしているのはわざとです。
2 * (2mn - m - n) + 1
ここをよく見てください。2 倍したら、とにかく偶数になります。
2mn - m - n の値が何であれ、もっと複雑な式だとしても、2 倍したら偶数確定です。
それに +1 するってなってるので、つまり奇数になると言うことです。
奇数 x 奇数 = (2m - 1) * (2n - 1) = 4mn - 2m - 2n + 1 = 2 * (2mn - m - n) + 1 = 奇数
間を省略して
奇数 x 奇数 = 奇数
奇数同士の掛け算は必ず奇数です。偶数になることはありません。
問題に戻って、ということは、
2^a * 3^b から、 a を取り出すには 2 で何回割り切れるか b を取り出すには 3 で何回割り切れるか を求めれば良い
ということがわかります。
実は問題がさっきの掛け算の性質を利用しているということです。
2^a * 3^b のようにして値をまとめても、
掛け算の性質から 2 (偶数同士)を何回掛けたのか、あるいは 3 (奇数同士)を何回掛けたのか、
わからなくなってしまう事は無いのです。
(define (lcons a b) (* (expt 2 a) (expt 3 b))) (define (div-cnt x d) (define (iter n c) (let ((nn (/ n d))) (if (not (integer? nn)) c (iter nn (+ c 1))))) (iter x 0)) (define (lcar x) (div-cnt x 2)) (define (lcdr x) (div-cnt x 3))
このように実装でき、
gosh> (lcar (lcons 10 4)) 10 gosh> (lcdr (lcons 10 4)) 4
普段使っている cons car cdr のように、このように値が取り出せます。