競プロ練習の日々。ペットボトルの箱書い…割り算は最速のアルゴリズム

徒然草2.0

>B本のお茶(ペットボトル)はA本入りの箱を何個買えばよいか?

BとAに何が入っても正しい値が出ないといけないコードで真っ先に思い浮かぶのは何箱買ったらBを越えるかを加算して求めること。6個入りの箱を20本のお茶がほしい時は6,12,18,24…だから4箱いる!と数列をカウントして求める…が効率が悪い…ので「割り算」という仕組みを用いる。(800本のペットが欲しくて0から順番にカウントしていたら日が暮れてしまう)

↑実は私たちが小学生(何年生か知りませんが4年生ぐらい?)で理解する割り算は(ループして制御するより速く効率的に)割られる数から割る数の個数を求めるアルゴリズムの一種である…ということが分かる。余談だが、分数もこの夜に存在しない無理数をあたかも有理数のように扱うテクニック(3分の1のケーキは整数で表せない)だが、ふつーに扱っている。

(自戒の意味を込めて)割り算で求めればいい値をループ制御で求めるコードを書くという過ちを犯す業務プログラマは多いと思うが…、大人も誤るし小人はすごいことやっていると言える。こういう言い方はよくないかもしれない。まあ、とにかくアルゴリズムというものは奥が深い。勉強する価値があるものだ。

徒然草2.0
スポンサーリンク
シェアする
gomiryoをフォローする
ごみぶろぐ

コメント

タイトルとURLをコピーしました