ブルーブリッジカップ-タイル配置-プッシュ-java
1325 ワード
問題の説明
長さN(1<=N<=10)の床があり、2つの異なるタイルが与えられる.1つの長さは1であり、もう1つの長さは2であり、数は限らない.この長さNの床を敷き詰めるには、全部で何種類の異なる敷き方がありますか?
例えば、長さ4の床には、次の5つの舗装法があります.
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
プログラミングは再帰的な方法で上記の問題を解く.
入力フォーマット
床の長さを表すNは1つしかありません
出力フォーマット
すべての異なるタイルの舗装方法の総数を表す数を出力します.
サンプル入力
サンプル出力
5
問題の構想を解く:経験のある人は一目でこれがフィボナッチの数列であることを見て、それからこの問題は解決しましたが、私のような初心者は共通の疑問を持っています.この問題はこの法則に合ってどのように推出されたのですか.
与えられた長さにかかわらず、私たちは2つの選択しかありません.1を選ぶか2を選ぶかで、与えられた長さがnであると仮定すると、1つ目の残りの長さを選ぶのはn-1です.
2つ目の残りの長さはn-2です.残りの長さで(n−1)−1および(n−1)−2,(n−2)−1および(n−2)−2を選択し続けた後、このように推定する
したがって、このときnのシナリオ数は、長さn−1のシナリオ数に加えて長さn−2のシナリオ数である
コアコード:arr[i]=arr[i-1]+arr[i-2];
ソースコードは次のとおりです.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int [] arr = new int [n+1];
arr[0]=1;arr[1]=1;
for (int i = 2; i < arr.length; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
System.out.println(arr[n]);
}
}
}
長さN(1<=N<=10)の床があり、2つの異なるタイルが与えられる.1つの長さは1であり、もう1つの長さは2であり、数は限らない.この長さNの床を敷き詰めるには、全部で何種類の異なる敷き方がありますか?
例えば、長さ4の床には、次の5つの舗装法があります.
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
プログラミングは再帰的な方法で上記の問題を解く.
入力フォーマット
床の長さを表すNは1つしかありません
出力フォーマット
すべての異なるタイルの舗装方法の総数を表す数を出力します.
サンプル入力
4
サンプル出力
5
問題の構想を解く:経験のある人は一目でこれがフィボナッチの数列であることを見て、それからこの問題は解決しましたが、私のような初心者は共通の疑問を持っています.この問題はこの法則に合ってどのように推出されたのですか.
与えられた長さにかかわらず、私たちは2つの選択しかありません.1を選ぶか2を選ぶかで、与えられた長さがnであると仮定すると、1つ目の残りの長さを選ぶのはn-1です.
2つ目の残りの長さはn-2です.残りの長さで(n−1)−1および(n−1)−2,(n−2)−1および(n−2)−2を選択し続けた後、このように推定する
したがって、このときnのシナリオ数は、長さn−1のシナリオ数に加えて長さn−2のシナリオ数である
コアコード:arr[i]=arr[i-1]+arr[i-2];
ソースコードは次のとおりです.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int [] arr = new int [n+1];
arr[0]=1;arr[1]=1;
for (int i = 2; i < arr.length; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
System.out.println(arr[n]);
}
}
}