Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Scalaビギナーズ関西 #2 の課題の解答例です。
/**
* たかし君が階段をのぼります。
* 課題:たかし君は階段を1段ずつ、または2段ずつ(1段飛ばし)でのぼるかをまぜてのぼることができます。
* 10段のぼるには、何通りののぼり方がありますか。
*
* #scala_kansai_beginners
*/
val firstStep1 = 1 :: Nil // 最初の1歩は1段
val firstStep2 = 2 :: Nil // 最初は1歩は2段
def patternsToArriveAt(step:Int): List[List[Int]] = step match {
case 1 => firstStep1 :: Nil // 1歩で1段しかありえない
case 2 => (1 :: firstStep1) :: firstStep2 :: Nil // 2歩の場合と1歩の場合がある
case _ => {
patternsToArriveAt(step - 1).map( // 目的の1段前にたどり着く全パターン
aPattern => 1 :: aPattern // ...に対してプラス1段
) ::: patternsToArriveAt(step - 2).map( // 目的の2段前にたどり着く全パターン
aPattern => 2 :: aPattern // ...に対してプラス2段
) // を合体するとその段にたどり着く全パターン
// (※ 2段前+1+1 を含めないのは、1段前の1段前+1 で考えたパターンと重複するから)
}
}
val result = patternsToArriveAt(10)
result.foreach(println)
// result に対して、すべて合計10だとか、パターンがユニークだとかを検証もできるよ
println(result.length)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment