一個(gè)經(jīng)典的問題：給定n個(gè)數(shù)，求其中的任意一個(gè)子集滿足集合中的每個(gè)元素值加和正好是n的倍數(shù)。剛開始怎么也沒有思路，因?yàn)閚很大，直接搜索顯然是不行的。后來在組合數(shù)學(xué)書上找到了這個(gè)例題（暈，之前白看了，居然把這個(gè)經(jīng)典的題目都給忘了），是抽屜原理的典型應(yīng)用。
假定n個(gè)數(shù)為a1，a2，...，an，前n項(xiàng)和分別是S1、S2、...、Sn，那么如果有一個(gè)Si模n是0，就是答案，否則，n個(gè)數(shù)模n的余數(shù)只能在1到n - 1之間，把余數(shù)作為抽屜，顯然n個(gè)數(shù)放到n - 1個(gè)抽屜里面，肯定有兩個(gè)數(shù)余數(shù)相等，這樣取它們的差就得到了結(jié)果，算法復(fù)雜度是O(n)的。
抽屜原理的應(yīng)用都十分巧妙。還有一個(gè)例子，一個(gè)屋子里面有n個(gè)人，他們的最大年齡不超過k歲，問是否肯定存在2組人（兩組沒有重復(fù)的人），使得這兩組人的年齡和相等。n個(gè)人的組合一共有2 ^ n種方法，注意到最大情況n的人的年齡和是n * k，這樣如果2 ^ n > n * k，根據(jù)抽屜原理，一定存在兩種組合他們的年齡和相等，而且沒有重復(fù)的人（如果重復(fù)，把那個(gè)人刪去就行了）。所以O(shè)(1)的時(shí)間就判斷出了結(jié)果。
不過在最開始做題目（PKU 2356）的時(shí)候，雖然代碼很短，但是錯(cuò)了好多次。首先是數(shù)組開小了，然后發(fā)現(xiàn)輸出的時(shí)候題目要求的是輸出數(shù)但是我給輸出下標(biāo)了。最后的問題出在一個(gè)很關(guān)鍵的地方，在取模為零的時(shí)候，我本應(yīng)該直接就記錄產(chǎn)生了解，但是我以為取模為零的時(shí)候下次肯定會(huì)產(chǎn)生重復(fù)的標(biāo)記，就沒有特殊處理。其實(shí)如果第一個(gè)數(shù)取模就是0的話，就有可能后面不產(chǎn)生重復(fù)的標(biāo)記，這樣我的程序就錯(cuò)了，還有就是最后一個(gè)是取模為零的時(shí)候也會(huì)出問題。想了很久才想到這個(gè)問題，改正之后終于過了。以后寫程序要仔細(xì)，不能想當(dāng)然啊。
附PKU 2356代碼：
#include <cstdio>
const int N = 10010;
int main()
{
int a[N], n, mod[N] = {0}, tmp = 0, len = 0, pos;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (len) continue;
tmp = (tmp + a[i]) % n;
if (tmp == 0)
{
len = i;
pos = 1;
}
if (mod[tmp])
{
len = i - mod[tmp];
pos = mod[tmp] + 1;
}
else
mod[tmp] = i;
}
printf("%d\n", len);
for (int i = 0; i < len; i++)
printf("%d\n", a[pos+i]);
return 0;
}
posted on 2009-06-12 09:09
sdfond 閱讀(576)
評論(2) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics