階段の上り方の数
n 段の階段を一番下（0 段目）からてっぺん（n 段目）まで上る。
一歩で一段か二段上れる。
ちょうどてっぺんに着く、互いに異なる歩き方の数を出力せよ。
たとえば n = 3 なら 1+1+1、1+2、2+1 の 3 通りである。
- 入力
- 1 ≤ n ≤ 70
- 出力
- 上り方の数
3
3
50
20365011074
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
最後の一歩は一段か二段なので ways[i] = ways[i-1] + ways[i-2] で、表を 0 段目から埋めれば足し算は n 回で済みます（動的計画法）。
同じ式をそのまま再帰で書くと同じ段を何度も計算し直し、n = 70 では呼び出しが約 10^14 回になって終わりません — Craykon は実行ステップが約 5 千万回を超えると止まります。
答えは n = 46 で 2,971,215,073 となり 32 ビット int（約 21 億）を超えるので、C・C++・Java・C# は long/long long の表が必要です。
n = 70 の答え 308,061,521,170,129 は 2^53 未満なので JavaScript・TypeScript・Craykon の数でも正確で、Python は上限がありません。
表の作り方：Python [0] * (n + 1)、JavaScript new Array(n + 1).fill(0)、Java・C# new long[n + 1]、C++ std::vector<long long>(n + 1)、Craykon 新リスト(n + 1, 0)。
n = int(input())ways = [0] * (n + 1) # ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1ways[1] = 1for i in range(2, n + 1): ways[i] = ways[i - 1] + ways[i - 2] # 마지막 걸음이 한 칸 또는 두 칸print(ways[n])const n = Number(require("fs").readFileSync(0, "utf8").trim());const ways = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);import { readFileSync } from "node:fs";const n: number = Number(readFileSync(0, "utf8").trim());const ways: number[] = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);import java.util.Scanner; public class Main { public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } System.out.println(ways[n]); }}using System; class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } Console.WriteLine(ways[n]); }}#include <iostream>#include <vector> int main() { int n; std::cin >> n; std::vector<long long> ways(n + 1); // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } std::cout << ways[n] << '\n';}#include <stdio.h> int main(void) { int n; scanf("%d", &n); long long ways[71]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } printf("%lld\n", ways[n]); return 0;}n = コンソール.行読み().数に();// ways[i] = i번째 칸까지 오르는 방법 수ways = 新リスト(n + 1, 0);ways[0] = 1;ways[1] = 1;繰り返す (i = 2; i <= n; i++){ // 마지막 걸음이 한 칸 또는 두 칸 ways[i] = ways[i - 1] + ways[i - 2];}コンソール.書く(ways[n]);