本日天氣：大太陽
本日心情：心情不錯
《Awesome 0005》：搭上203公車，發現原來這是一趟可以到紅橘綠棕藍五種捷運的路線。
《Awesome 0006》：紅毛城全票80元，正要掏錢時發現原來自己新北市民不用錢（汐止和淡水隔很遠但都是新北）。
《Awesome 0007》：海洋體驗營錄取了！這個八月我要出海去玩兩天一夜！。
碁峰出版了一本『鍛鍊你的數學腦』…好吧，這其實是一本教你寫Ruby 語言的書。
【來源】不過它裡頭有很多的題目，是屬於排列組合型的，而且很活用，可以挑戰你自己的運算思維。我們就來看看Q 17『挑戰30人31腳』的題目吧：
小學生30人31腳的活動很風行，本單元要思考的是有利於30人31腳在跑的排列方式。女孩子連續排在一起，在體力上會吃虧，所以不讓女孩子排在一起。假設是男孩子幾個人排在一起也不會有影響，請問當30人排成一排時，請算出可排出幾種排法。先只考慮男女的排列方式，不考慮誰站在哪個位置。
【這聽起來有點性別歧視的問題，但是我只是照書上所寫的啊！我是豬但不是沙豬！】
我先來談的是我的想法，再來講書上的寫法，也許很意外的，我們會看出不同的東西。
在講我的想法前，我先講一道排列組合的題目：
X+Y+Z = 10
假設三者都是整數，請問有幾種可能性？
這是一道高中的排列組合題目，我其實已經忘了它怎麼算，幸好Google大神重新教會了我它的概念。
它是假設有10個一樣的東西擺在那邊
你手上有隔板，要在10個東西形成的9個位置塞入兩塊隔板，然後形成三個數量，合起來就會是10。
它的可能性就符合的需求，因此算法就是C(9,2)。
但如果這三個數字可以是零呢？當初學會的算法讓我感受到數學的美妙，就是把它想成每個數字都至少是1，所以：
(X-1)+(Y-1)+(Z-1) = 10
整理一下後就變成X+Y+Z = 13，因此算法就是C(12,2)。（因為中間有12個間隔）
此時就可以談這一題我的想法了。
假設先排女生，沒有女生的排法當然30個都男生，就是只有一種排法。
如果有1個女生的話，男生可以排她前面也可以排後面，所以有2個位子可以排29個男生，我們就可以把它想成是 (a-1)+(b-1) = 29 的問題。
那如果兩個女生先排呢？因為中間至少要有個男生，所以可以先假設除了那個站最後的女生外，前方的女生右邊要有一個男生。接下來就有3個位置要排27個男生，就可以把它想成(a-1)+(b-1)+(c-1) = 27 的問題。
以此類推，當三個女生時，非最後一個的女生右邊都要配一個男生，然後還有25個男生要排在四個位置，就是(a-1)+(b-1)+(c-1)+(d-1) = 25的概念。
一直這樣子做下去，基本上只要算到第15個女生就可以，因為若是算到第16個女生，不管怎麼排，女生一定會連在一起。
好啦我知道這樣的做法有一點土砲，但我就是喜歡咩！而且如果真的用程式來跑的話，其實它有規律，很快也就算出來了。
這是我的解法，我們再看看書上的。
書上先不急著講規律，他們先假設左方起頭的第一個人是男或女，列出來然後再做延伸。
比如第一個是男生，那第二個就可以接男生或女生，但如果第一個是女生，之後就只能接男生。我們這樣子延伸下去之後再來看一下情況，先看一下這個圖的旁邊的數字，你看到了什麼？
好熟悉的數字對不對？如果你有這個敏銳度，你也可以去當達文西密碼的主角了。沒錯那個數字就是費波那契數列。
記得這個數列剛開始是談兔子生小孩的問題嗎？最著名的就是每一個數字都是 這個數字的前兩個數的和。讓我們再重新回想一下這個圖去做對應，是不是也是在一樣的概念？
也就是我們不用去談排列組合，只要去算出費波那契數列第卅個數字，我們就成功了。
於是小學生的30人31腳的可能性，不過就只是一堆的兔子數量的問題。
【來源】
沒有留言:
張貼留言