Edit Question - KnowledgeHub

Title Body

I've been trying to solve this programming problem , but since I can't figure it out, I found a solution online. but I can't really understand why that solution works either .. the task is to calculate in how many ways can a 3*n ( n >= 0 , n is the only input) rectangle be completely filled with 2*1 dominos. e.g. (red lines represent dominos): This was what I first drew on a sheet of paper when I read the text, and I saw that there were three possible combinations that a 3*2 rectangle can have, and that if n is odd the solution is 0 because there is no way to fill up the entire rectangle then (one piece will always stay uncovered by a domino). So I thought the solution was simply 3^n , if n was even, and 0 , if n was odd. turns out, I was wrong. I found a relatively simple solution here: #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; } Why does this work?!

Tags (comma-separated) Cancel