結城さんのはさみの問題

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が今回のはさみを使う回数と一致したっぽい
(う〜ん、上の定理と若干異なるのが気になる・・・)

雑な感じだけどフィボナッチ数列もこんなRubyで実装

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

が答え、と。

以上



追記
この記事に関してですが、
挑戦受付が終了しているということで、問題ないということでした。

ブログ記事にかんしての注意事項などは下記のページに記載されています。
他の問題に関する情報もありますで
今後も追加されていくと思いますので、挑戦してみたいッ!
ってかたは一度ごらんになってみるといいと思います。

CodeIQの問題に挑戦しよう!