鴿巢原理是抽屜原理嗎，鴿巢原理是什麼意思？

1樓：小徐老師數學課堂

鴿巢問題又名抽屜原理，一種跟生活實際非常相關的數學。

鴿巢原理

2樓：雞蛋泡泡安

鴿巢原理也叫抽屜原理，是ramsey定理的特例。它的簡單形式是：把n＋1個物體放入n個盒子裡，則至少有乙個盒子裡含有兩個或兩個以上的物體。

讓我來舉個例子：有乙個晚上你的房間的電燈忽然間壞了，伸手不見五指，而你又要出去，於是你就摸床底下的襪子。你有三雙分別為紅、白、藍顏色的襪子，可是你平時做事隨便，一脫襪就亂丟，在黑暗中不能知道哪一雙是顏色相同的。

你想拿最少數目的襪子出去，在外面借街燈配成同顏色的一雙。這最少數目應該是多少？如果你懂得鴿籠原理，你就會知道只需拿出去四隻襪子就行了。

為什麼呢？因為如果我們有三個塗上紅、白、藍的盒子，裡面各放進相對顏色的襪子，只要我們抽出4只襪子一定有乙個盒子是空的，那麼這空的盒子取出的襪子是可以拿來穿。

或者是乙個袋子裝了100個蘋果，100個香蕉，100個橘子，100個梨子。如果我們每分鐘從袋子裡取出1種水果，那麼需要多少時間我就能肯定至少已經拿出1打相同種類的水果。假如有n+1個元素放到n個集合中，其中必定有乙個集合裡至少有兩個元素。

鴿巢原理是什麼意思？

3樓：霓脦那些

若有n個籠子和n+1只鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有乙個籠子有至少2只鴿子。

運用抽屜原理的核心是分析清楚問題中，哪個是物件，哪個是抽屜。例如，屬相是有12個，那麼任意37個人中，至少有乙個屬相是不少於4個人。

這時將屬相看成12個抽屜，則乙個抽屜中有 37/12，即3餘1，餘數不考慮，而向上考慮取整數，所以這裡是3+1=4個人，但這裡需要注意的是，前面的餘數1和這裡加上的1是不一樣的。

因此，在問題中，較多的一方就是物件，較少的一方就是抽屜，比如上述問題中的屬相12個，就是對應抽屜，37個人就是對應物件，因為37相對12多。

應用。鴿巢原理經常在計算機領域得到真正的應用。比如：

雜湊表的重複問題（衝突）是不可避免的，因為keys的數目總是比indices的數目多，不管是多麼高明的演算法都不可能解決這個問題。

這個原理，還證明任何無失真壓縮演算法，在把一些輸入變小的同時，作為代價一定有其他的輸入增大，否則對於長度為l的輸入集合，該壓縮演算法總能將其對映到乙個更小的長度小於l的輸出集合，而這與鴿巢理論相悖。