プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q17:30人31脚に挑戦！。

Q: 30人31脚をするときの男女の並び方が何通りあるか求める。ただし、女子が隣り合わないようにする。

def pattern(num:Int):Int = {  
  def stack(n:Int, last:Char):Int = {
    if(n == 0) 1
    else if(last == 'b') stack(n-1,'b')+stack(n-1,'g')
    else stack(n-1,'b')
  }
  stack(num-1,'b')+stack(num-1,'g')
}
pattern(30)