事實上可以發現有直板跟橫板兩種情況。
直板一個佔用一個面積,橫板一個佔用兩個面積。
所以n = 1時,無橫板,
n = 2時,最多1個橫板,
n = 3時,最多1個橫板,
n = 4時,最多2個橫板,
n = 5時,最多2個橫板,
n = 6時,最多3個橫板。
可以發現最多橫板數為n / 2。
每多一個橫板,組合方式就會多一種。
n = 1時,無橫板的組合,
n = 2時,無橫板的組合 + 1個橫板的組合,
n = 3時,無橫板的組合 + 1個橫板的組合,
n = 4時,無橫板的組合 + 1個橫板的組合 + 2個橫板的組合,
n = 5時,無橫板的組合 + 1個橫板的組合 + 2個橫板的組合,
n = 6時,無橫板的組合 + 1個橫板的組合 + 2個橫板的組合 + 3個橫板的組合。
無橫板的組合,就都是直板:Cn取n。
1個橫板的組合,為n - 2個直板 + 1個橫板:C的n - 1取1。
2個橫板的組合,為n - 4個直板 + 2個橫板:C的n - 2取2。
看出來了嗎?
每多一塊橫板,直板的數目就會少2。
有了直板與橫板的數目,就可以求得組合的情況。
其實就是要算這種問題:
有m塊直板跟n塊橫板,求其組合方式:(m + n)! / (n! * m!)。
把組合數加一加,就是答案了。
可以利用ACM369的方式計算組合。
/* ACM 900 Brick Wall Patterns * mythnc * 2011/12/30 10:12:43 * run time: 0.008 */ #include <stdio.h> #define MAXN 50 #define MIN(X, Y) ((X <= Y) ? X : Y) long long count(int); long long com(int, int); int gcd(int, int); int main(void) { int n, i; while (scanf("%d", &n) && n != 0) printf("%lld\n", count(n)); return 0; } /* count: return the combination numbers */ long long count(int n) { int i, ver, hor; long long times; times = 1; ver = n - 2; hor = 1; while (ver >= 0) { times += com(ver, hor); ver -= 2; hor++; } return times; } /* com: return the combination times: * (m + n)! / (n! * m!) */ long long com(int m, int n) { int sum, i, j, times, factor, tmp; long long ans[MAXN] = { 0 }; if (m == 0 || n == 0) return 1; if (m == 1 || n == 1) return m + n; times = 0; sum = m + n; /* init */ for (i = sum - MIN(m, n) + 1; i <= sum; i++) ans[times++] = i; /* simplify */ for (i = 2; i <= MIN(m, n); i++) { tmp = i; for (j = 0; j < times; j++) { if (ans[j] % tmp == 0) { ans[j] /= tmp; break; } if ((factor = gcd(tmp, ans[j])) != 1) { ans[j] /= factor; tmp /= factor; } } } /* cal ans */ for (i = 1; i < times; i++) ans[0] *= ans[i]; return ans[0]; } /* gcd: return gcd */ int gcd(int a, int b) { while ((a %= b) && (b %= a)) ; return a + b; }
沒有留言:
張貼留言