ハサミを使うタイミングをやってみた

あっ, どーも僕です.


こちらの問題がおもしろそうなのでやってみました.

第6回 ハサミを使うタイミング~どうやって端を見つけるの?─結城浩からの問題|gihyo.jp … 技術評論社


ただ, 解答期間が過ぎていたので提出できないです. 残念.
まぁ方針はゴリ押しなのでそれでもいいか.



解答の方針は「一番小さい長方形を大きくしていく」です.

問題を見ていただければわかりますが, これ以上カットできない状態で最も小さい長方形は縦と横の比が1:2なのは明らかです. 
なので, 縦と横の比が1:2の長方形に横の長さの正方形を加えることでできる新しい長方形は, 一つ前の長方形の一つのはずです. これをカット回数が40になるまでこれを増やしていくことでお望みの長方形の一つが生成できます.
ただし, この方法だと部分部分では最小の面積を求めていると思いますが, 全体としてはどうなのでしょう?帰納法で証明できそうな気がしますが, その辺はそっとしておきます.

計算のイメージはこちら. 最初の青い長方形に, 赤い正方形, 緑の正方形と順々に増やしていきます.


f:id:aaaazzzz036:20130131130542p:plain


この計算をa=1としてRを使ってやってみたところ結果は縦が267914296, 横が433494437となりました.

....むちゃくちゃでかいなおい.


#結城先生からの問題
#http://gihyo.jp/dev/serial/01/codeiq/0006
#解答方針:
#最終的に最小な縦=1, 横=2の長方形に横の長さの正方形を加えていいく
compute_YuukiChallenge <- function(CutsNumber)
{
  a0 <- 1 ; b0 <- 2 
  for( i in seq(length = CutsNumber)) {
  a <- b0 ; b <- a0 + b0
  a0 <- a ; b0 <- b
  }
  
  return(c(a0, b0))
}
compute_YuukiChallenge(40)
#[1] 267914296 433494437

cheak_YuukiChallenge <- function(height , width)
{
  n <- 0
  K <- 1
  while( K != 0){
    K <- width %% height
    width  <- height
    height <- K
    n <- n + 1
  }
  
  return(n-1)
}
cheak_YuukiChallenge(267914296, 433494437)
#[1] 40


S <- 267914296 * 433494437
format(S, scientific = F)
[1] "116139356908771360"