私はthis programming problemを解決しようとしていましたが、わからないのでオンラインで解決策を見つけました。私そのソリューションが機能する理由は本当に..どちらかを理解することはできませんSPOJ:M3TILEソリューションの説明
タスクは、* 3 *することができ、N(n >= 0
、nは入力のみである)矩形が2で満たさ完全ことがどのように多くの方法で計算することです。 1ドミノ。
(赤線は、ドミノを表す):
これは3 * 2の長方形が持つことができる3つの可能な組み合わせがあったことを私は文章を読んだとき、私は最初の一枚の紙の上に描いた、そして私が見たものでしたnが奇数の場合、解は0になります。なぜなら、長方形全体を埋める方法がないからです(1つの部分は常にドミノによって覆い隠されたままです)。
だから、nが偶数ならば3^n
となり、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;
}
なぜ、この仕事はありません!
ニースの証拠! http://oeis.org/A001835 –
@Daniel n = 0に対応する基本ケースについて説明できますか? –
@ AtulSingh n = 0の場合、セルを一切持たないボードがあります。タイルを配置する方法は1つあります.3×0ボードに3,0 = 0のセルがあるため、0 /(2・1)= 0/2 = 0のタイルが必要です。 –