白峻1904号.

4846 ワード
白駿 ダイナミックプログラミング フィボナッチ cpp テキストリンク
1904号
👍 質問する
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다.
그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다.
결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다.
예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다.
(01, 10은 만들 수 없게 되었다.)
또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.
단 타일들은 무한히 많은 것으로 가정하자.
👍 入力/出力
입력 : 자연수 N (1 ≤ N ≤ 1,000,000)
출력 : (만들 수 있는 2진 수열 개수) % 15746
👍 好きなように説明する
どうしてフィボナッチ数列なの?
  • N時の数
    (N-2の場合、数字の組み合わせ+00の組み合わせ)と
    (N-1の場合の数の組み合わせに+1の組み合わせを加える)
    • N−1を組み合わせた場合、その組み合わせに1または0を加えることができる.
    0はいたずらっ子である東株巨魔連続の00しか使えない
    N-2コンビネーション時
  • 10と0の合一タイルは日本語では言えない組合せ
    • である.
    n−2の組合せに1で終わる数字がある場合、
  • 01は成立しない.
    0で終わるとしても0個の奇数が連続するため、
    • は成立しない.
  • 111を貼り付けると、前のN-1の組み合わせが1で終わったときと同じ結果になります.
    これも成り立たない(私のミス)
  • なので、00の組み合わせを加えるしかありません.
    • そのため、フィボナッチ数列に適用されます.
    👍 c++正しいコード
    #include <bits/stdc++.h>
using namespace std;

long long fibo[1000001];
void init() {
	fibo[1] = 1;
	fibo[2] = 2;
}

int main() {
	init();
	int N;
	cin >> N;
	for (int i = 3; i <= N; i++) {
		fibo[i] = (fibo[i - 1] + fibo[i - 2])%15746;
	}

	cout << fibo[N] << '\n';
}
    どうして家に帰らせないの?
    再帰呼び出しを使用する場合
    fibo(N)を呼び出す場合は、fibo(N−1)、fibo(N−2)を呼び出す必要があります.
    fibo(N-2)、fibo(N-3)を呼び出してfibo(N-1)を計算する
    fibo(n-3)、fibo(n-4)を呼び出してfibo(n-2)を計算する
    同じ計算の繰り返し呼び出しを実行すると、演算が遅くなります.
    時間の複雑さ:O(2)になる
    動的プログラミング
    もう計算しなくてもいいです.
    時間複雑度:O(N)のみ
    いやでも!!!
    피보나치를 더해갈 때마다 모듈러 연산을 수행하면 계산 결과가 잘못되지 않을까?
but 모듈러 연산은
(A+B)modC의 나머지나
(AmodC + BmodC)modC의 나머지가 같은 특징이 존재하기에
문제가 되지 않음.
    レビューコード
    AndroidでListView、RecyclerViewでitemがずれを表示する問題は?