Re: [bep] 割り算の答えを小数で出すには？ <Re: learning lisp: while

[TAKAHASHI Naoto <ntakahas@m17n.org>]

ここ数日、英語論文の校閲と、Cプログラムの検証に明け暮れているn高橋です。

Reiko TAKAHASHI  (高橋玲子)writes:

> 昼間＆放課後がちょっとだけ立て込んでいたのと、夜遅くスターバックスのアイ
> スグランデラテを一気飲みしておなかを壊したのと、夜よりは強いはずの朝なの
> に全然起きられなかったのと……いろいろあって遅くなりました。

自発的にやってるんですから、ゆっくり行きましょう。

> ちゃんと覚えてはいないのですが、最初、ここを
> (and (> x 3) (/= (% x 2) 0))
> にしたらおかしなことになって、もう時間もないのでどさくさで(or)にしたら一
> 応それらしい答えを表示してくれたので、「えい、これでいいや！」とポストし
> てしまいました。
> でも、どうして(and)だとだめだったんでしょう……？　今ゆっくり見てもわかり
> ません。

while は、条件が成立し続ける間だけループを繰り返すからです。つまり、一
度条件が成立しなくなると、その時点でループは終了します。たとえ後もう一
回まわればまた成立するような場合でも同じです。確認のため、r高橋版プロ
グラムの or を and に変えたものを下に示します。

(let ((x 1000) (y 3))
  (while 
      (and (> x 3) (/= (% x 2) 0))
    (while 
        (and (<= y (+ (/ x 2) 1))  
             (/= (% x y) 0))
      (setq y (+ y 1))
      (when (= y (+ (/ x 2) 1)) 
        (insert (format "%s\n" x)))) 
    (setq x (- x 1))
    (setq y 3))
  (insert (format "%s\n" 3))  
  (insert (format "%s\n" 2)))

xは最初1000で、これは (and (> x 3) (/= (% x 2) 0)) を満たします。次にx 
が1だけ減って998になると、(> x 3) は満たされても (/= (% x 2) 0) は満た
されません。ですからここでループが終了してしまい、残の数はチェックされ
なくなってしまうのです。

> } それから他のスレッドで話題になっていますが、y で割り切れるかどうかチェッ
> } クするときの上限値は (+ (/ x 2) 1) ではなくて、(sqrt x) です。sqrt は
> } square root (平方根) の略です。x が2以上の場合、(sqrt x) は常に
> } (+ (/ x 2) 1) よりも小さくなりますから、ループを回る回数をさらに減らす
> } ことができます。

> 　これ、どうしてそう言えてしまうのかが未だによくわかりません。
> 割る数が平方根になったとき、答えも平方根になるから、それ以上大きな数で割
> っても、前に割ったことのある小さな数が答えになるだけで、結局同じことを二
> 度やってしまっている……ということでしょうか？？
> ……あっ、それなら今なんとなくわかったような気が……。

そうです。たとえば12を2個の正の整数の積で表すことを考えてみます。この
場合可能な組み合わせは 1*12, 2*6, 3*4, 4*3, 6*2, 12*1 の6通りです。が、
掛算は*記号の右と左を入れ替えても答が同じになりますから、実際には*記号
の左側の数が右側の数より大きくなったら、もうそれ以上調べる必要はありま
せん。

> でも、平方根って整数ではないですよね。その場合は、切り上げした整数を使え
> ばいいですか？

切り上げまで計算する必要はありません。切り捨てで充分です。今、素数かど
うか調べたい数がnで、nの平方根の切り上げをi、さらに n/i=x とします。最
後の式を変形すると n=x*i ですが、iがnの平方根より大きいのですから、xは
当然nの平方根より小さくなります。つまりたとえxが整数であっても、もうす
でに調べてあることになりますし、xが整数でなかったらそもそも調べる必要
ありません。

nが12のときの例で言うと、ルート12は約3.46です。これを切り上げると4にな
りますが、上で見たように切り捨ての3まで調べれば充分なことがわかります。

> 平方根を整数にするには、どうすればいいでしょう？（って、みなさんが書いた
> のを見ればいいですね(^^;;;)）。

(floor (sqrt x)) ですね。でもわざわざ整数に直す必要はありません。単に
(sqrt x) と試し割りする整数の大小比較すればいいだけの話です。

> 　ところで、(let ...)で、使う変数を指定するとき、そこに値を当てはめなくて
> もいいんですね。私は、必ずなにかの値を入れなければならないと思っていまし
> た。

はい、必ずしも初期値を与える必要はありません。初期値が与えられない場合
は暗黙のうちに nil が初期値になります。ただし、本当に nil を初期値にし
たい場合は明示的に (let ((v nil)) ..) のように書いておいた方がはっきり
していいと思います。今回は y を使う前に毎回必ず setq で明示的に値をセッ
トしているので、let の先頭では初期値を与えませんでした。

> } ;; n高橋スマートバージョン
> } ;; 2は特別扱いして、奇数だけ調べる
> } ;; xが素数かどうかは、(sqrt x) までの奇数で割って調べる
> } (let ((x 3) y limit)                    ; 3から調べ始める
> }   (insert "2\n")                        ; ここだけずるをする
> }   (while (<= x 1000)
> }     (setq y 3 limit (sqrt x))           ; 試し割りは3からルートxまで
> }     (while (and (<= y limit) (/= 0 (% x y))) ; limitも試すので<=と等号が必要
> }       (setq y (+ y 2)))                 ; 試し割りは奇数だけなので+2
> }     (when (> y limit)                   ; limitで割り切れたときは合成数
> }       (insert (format "%s\n" x)))       ;   だから>=でなくて>
> }     (setq x (+ x 2))))                  ; 次の奇数を試す

> 　(when (> y limit)                   ; limitで割り切れたときは合成数
> というのがわかりません。
…
> あっ、もしかして、さっき書いた、平方根が整数だった時とそうじゃなかった時
> の処理に関係している……？

そうです。xの平方根が整数になるとき、内側のループは y=limit まで回る可
能性があります。たとえばxが25だと、yは5まで大きくなります。ですから素
数かどうかのチェックはyがlimitよりも大きいかどうかで判断することになり
ます。

と、ここまで書いたところでスマートバージョンの無駄に気付きました。もし
xの平方根が整数になるならば、xは絶対に素数じゃありませんね。つまり内側
のループの終了判定は (< y limit) でいいことになります。人生、勉強だ。

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/