このプログラミングの問題を解決しようとしてきましたが、わからないので、オンラインで解決策を見つけました。しかし、そのソリューションが機能する理由もよくわかりません..
n >= 0タスクは、3*n ( 、n が唯一の入力) の長方形を 2*1 のドミノで完全に埋めることができる方法の数を計算することです。
例 (赤い線はドミノを表します):
これは私がテキストを読んで最初に紙に描いたもので、3*2 の長方形には 3 つの可能な組み合わせがあり、n が奇数の場合、解は 0 になることがわかりました。次に、長方形全体を埋めます (1 つのピースは常にドミノに覆われないままになります)。
したがって、n が偶数の場合、n が奇数の場合、解決策は単純3^nであると考えました。0結局、私は間違っていました。
ここで比較的簡単な解決策を見つけました：
#include <iostream>
using namespace std;
int main()
{
int arr[31];
arr[0]=1;
arr[1]=0;
arr[2]=3;
arr[3]=0;
for(int i = 4; i < 31; i++) {
arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
}
int n;
while(1) {
cin >> n;
if(n == -1) {
break;
}
cout << arr[n] << endl;
}
return 0;
}
なぜこれが機能するのですか？
