あまつぶ: Memo/Q172

ハサミを使うタイミング

問題ページ

  [ハサミを使うタイミング]
  [ハサミを使うタイミング]

例題

  3回、2回、3回で、はさみは2回。

なにをしているか

  ユークリッドの互除法を使って最大公約数を見つけるアルゴリズム。
  1回目は、横を縦で割ったあまりを求めており、商は3。
  2回目は、縦を先ほど求めたあまりで割った余りを求めており、商は3。
  3回目は、最初に求めたあまりを次に求めたあまりで割ったあまりを求めており、商は2。
  ここであまりが0になったので、終了。
  最後ははさみを使わないので、あまりが0になった回は除いて、3回-1回=2回。

例題の縦と横は

  2回目のあまりを、最小の正の整数である1とすると、
  3回目の計算は ○ ÷ 1 = 2 あまり 0 だから、最初のあまりは2。
  2回目の計算は 縦 ÷ 2 = 3 あまり 1 だから、縦は2*3+1で7。
  1回目の計算は 横 ÷ 7 = 3 あまり 2 だから、横は7*3+2で23。
  ということで、横23、縦7かな。

検算

  1回目。23(横)÷7(縦)＝3あまり2。あまりがあるのでもう一度。
  2回目。7(縦)÷2(1回目のあまり)＝3あまり1。あまりがあるのでもう一度。
  3回目。2(1回目のあまり)÷1(2回目のあまり)＝2あまり0。あまりがなくなったので終了。

  最後のあまり1を起点に、常に商が1になるようにしたら小さいのができる？
  いや、最後は1ではだめ。
    ○ ÷ 1 = 1 あまり 0 だと、○も1になってしまって、その時点で割り切れてる
  なので、最後の商は2で。

  最後(41回目)。○ ÷ 1 = 2 あまり 0 ⇒ 40回目のあまりは2。
  40回目。○ ÷ 2 = 1 あまり 1 ⇒ 39回目のあまりは2*1+1=3。
  39回目。○ ÷ 3 = 1 あまり 2 ⇒ 38回目のあまりは3*1+2=5。
  38回目。○ ÷ 5 = 1 あまり 3 ⇒ 37回目のあまりは5*1+3=8。
  37回目。○ ÷ 8 = 1 あまり 5 ⇒ 36回目のあまりは8*1+5=13。
  ・・・フィボナッチ数列になってるよ。

  ってことで、横と縦がフィボナッチ数列の連続する2項になっているときに切る
  回数が多いということになるのかな。

  フィボナッチ数列を順に生成しつつ、ユークリッドの互除法を使って切る回数
  を調べるプログラムを作って試した結果が以下。

  (     WIDTH,     HEIGHT)
  
  (         2,          1) => GCD :  1, COUNT :  0
  (         3,          2) => GCD :  1, COUNT :  1
  (         5,          3) => GCD :  1, COUNT :  2
  (         8,          5) => GCD :  1, COUNT :  3
  (        13,          8) => GCD :  1, COUNT :  4
  (        21,         13) => GCD :  1, COUNT :  5
  (        34,         21) => GCD :  1, COUNT :  6
  (        55,         34) => GCD :  1, COUNT :  7
  (        89,         55) => GCD :  1, COUNT :  8
  (       144,         89) => GCD :  1, COUNT :  9
  (       233,        144) => GCD :  1, COUNT : 10
  (       377,        233) => GCD :  1, COUNT : 11
  (       610,        377) => GCD :  1, COUNT : 12
  (       987,        610) => GCD :  1, COUNT : 13
  (      1597,        987) => GCD :  1, COUNT : 14
  (      2584,       1597) => GCD :  1, COUNT : 15
  (      4181,       2584) => GCD :  1, COUNT : 16
  (      6765,       4181) => GCD :  1, COUNT : 17
  (     10946,       6765) => GCD :  1, COUNT : 18
  (     17711,      10946) => GCD :  1, COUNT : 19
  (     28657,      17711) => GCD :  1, COUNT : 20
  (     46368,      28657) => GCD :  1, COUNT : 21
  (     75025,      46368) => GCD :  1, COUNT : 22
  (    121393,      75025) => GCD :  1, COUNT : 23
  (    196418,     121393) => GCD :  1, COUNT : 24
  (    317811,     196418) => GCD :  1, COUNT : 25
  (    514229,     317811) => GCD :  1, COUNT : 26
  (    832040,     514229) => GCD :  1, COUNT : 27
  (   1346269,     832040) => GCD :  1, COUNT : 28
  (   2178309,    1346269) => GCD :  1, COUNT : 29
  (   3524578,    2178309) => GCD :  1, COUNT : 30
  (   5702887,    3524578) => GCD :  1, COUNT : 31
  (   9227465,    5702887) => GCD :  1, COUNT : 32
  (  14930352,    9227465) => GCD :  1, COUNT : 33
  (  24157817,   14930352) => GCD :  1, COUNT : 34
  (  39088169,   24157817) => GCD :  1, COUNT : 35
  (  63245986,   39088169) => GCD :  1, COUNT : 36
  ( 102334155,   63245986) => GCD :  1, COUNT : 37
  ( 165580141,  102334155) => GCD :  1, COUNT : 38
  ( 267914296,  165580141) => GCD :  1, COUNT : 39
  ( 433494437,  267914296) => GCD :  1, COUNT : 40

  横2、縦1（0回）から始まって、40回になるところまで。

答えは

  ( 433494437,  267914296)

  かな？

上記のプログラムのソース

  https://gist.github.com/1682405dfbf6bcdb629f

Google Docs の Spread Sheet で

  https://docs.google.com/spreadsheet/ccc?key=0Ap9XUxAowQnPdEZfWElVZEFIT2c0dzRHTHVESnd3bHc