結城さんのはさみの問題
CodeIQで乗り遅れたのでgihyo.jpにあがってるのを解いてみた
第6回 ハサミを使うタイミング〜どうやって端を見つけるの?─結城浩からの問題
ブログとかで解答していいのか知らんし、あってるかもわからんのでなんかったら消します。
あと、自分で解きたいからネタバレイヤヨって人も見ないでください。
横の長さをx、縦の長さをyとしたときに
2で出来上がるのが必ず長さyの正方形。
3は ny <= x となるn個の正方形を作る。
なので切り取った左側をa、右側をbとすると
x = a + b a = ny x = ny + b
つぎに使うのがbなので
b = x - ny ( = x % y)
でこのbを新たなy, 今までyをxとしてbが0になるまでの計算回数-1が40になればおkと
(一回目の計算で0になるとはさみを使っていないので)
ここまでくるとお分かりのようにやってることがユークリッドの互除法と一緒なんですね。
というわけで最大公約数ではなくそのときの回数を求めるRubyのコード
#はさみを使った回数なのでカウントは0から始める def gcd_count(a, b, level = 0) if a < b puts "error" return 0 end r = a % b if r == 0 return level else gcd_count(b, r, level + 1) end end
で、どうやって40回再帰されるaとbを見つけようかなと思ったんだけど、さすがいろんなあたい入れて試行錯誤するのも疲れるし、
間違って黄金比にでもあたったら一生計算が終わらなくなるwジャイロさんの黄金長方形と一緒で無限に回転するのですよwたぶん
という訳で計算回数の求めかたを調べてみたら
こんなページを見つけた。定理7.3の下の方に書いてある。
どうやらフィボナッチ数列を使えばいいみたい。
Fn % Fn-1 = Fn-2(n >3, n = 0, 1, 2, 3, 4 ...)
なのね
Fn = Fn-1 + Fn-2 -> Fn = 1 * Fn-1 + Fn-2
とかんがえると当たり前か
Fn = 3〜13くらいまでで手計算してみたところ
n-2が今回のはさみを使う回数と一致したっぽい
(う〜ん、上の定理と若干異なるのが気になる・・・)
def fib(count, level = 0, now1 = 1, now2 = 1) if level !=0 && level != 1 tmp = now1 + now2 now2 = now1 now1 = tmp end if level == count return now1 else return fib(count, level + 1, now1, now2) end end
あとは40回にするために40 + 2で
x = fib(42) y = fib(41) puts fib(x, y) #=> 40 puts x #=> 433494437 puts y #=> 267914296
で
267914296x433494437
が答え、と。
以上
追記
この記事に関してですが、
挑戦受付が終了しているということで、問題ないということでした。
ブログ記事にかんしての注意事項などは下記のページに記載されています。
他の問題に関する情報もありますで
今後も追加されていくと思いますので、挑戦してみたいッ!
ってかたは一度ごらんになってみるといいと思います。