Skip to content

Instantly share code, notes, and snippets.

@mumoshu
Created Apr 13, 2013
Embed
What would you like to do?
stepsFib3(1000)

結果

res33: BigInt = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
import annotation.tailrec
def stepsFib3(n: BigInt): BigInt = {
val One = BigInt(1)
@tailrec
def tailrecFib(n: BigInt, next: BigInt, res: BigInt): BigInt = n match {
case One => res
case _ =>
tailrecFib(n - 1, next + res, next)
}
tailrecFib(n, 2, 1)
}
1段 0から1段上る場合の1通り = 1
2段 0->2, 0->1->1 = 1 + 1 = 2
3段 0->1->3, 0->2->3, 0->1->2->3 = 3
4段 0->1->2->3->4, 0->1->2->4, 0->1->3->4, 0->2->3->4, 0->2->4, = 5
以降、n段目 = n-1段目から1段登る場合と、n-2段目から2段登る場合 = n-1段のパターン+n-2段パターン
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment