PuzzleUp 2008 討論系列5 – 疊床架屋 Part I

文字-A A +A

這是一篇充滿了『圖』的文章… 

PuzzleUp 2008 -14

發布日: October 29, 2008

國中時參加過一個營隊。
你知道的, 營隊不外乎就是那些元素 – 大哥哥大姐姐, 很多你喜歡和不喜歡的人, 一堆現在看起來很幼稚的團康, 外加最後哭到生離死別的晚會。

記得有個團康是這樣子玩的, 當時我們在闖關…

關主:『每個人脫掉一隻鞋子。』
於是地上出現了各色的鞋子, 還有的霸凌爬到人家頭上。
關主:『把鞋子依間隔距離排好。』
鞋子們排好隊, 準備升旗唱國歌…

遊戲開始了,  每個人要輪流上場(輪完可以再輪), 做什麼??
跳鞋子…不過是單腳。
在單腳的狀況下, 你要依序跳過鞋子隊伍。可以隨時停, 然後你就把你跳過的鞋子都拿回去, 再換下一個人。但有個條件, 要是你踩到了鞋子, 那麼即使之前跳過的也不能拿走, 自己得摸摸鼻子回到隊伍最後等下一輪。

每個人都想當英雄, 大家心裏想的大概是類似的:『要是我一個人可以跳完全程, 拿回所有的鞋子, 不就馬上就過關了嗎??』
公布中場結局 – 所有人都輪過了, 但一隻鞋子都沒回來。
終於這時候有個人醒了 – 我們應該從近的鞋子拿起啊, 跳一隻就停, 拿回一隻。每拿走一隻, 前面的路也清空了。這樣會不會比較快?
兩分鐘不到, 所有的鞋子都回到主人腳上了。

從簡單的做起, 每一步都讓下一步有根基, 更容易。也許會花點時間做容易的事, 卻能更快解決問題。我們來看這道題目。

--
Height Row

20090121-00 by you.
(圖片來源: PuzzleUp 網站)

You will place 16 people with different heights to a meeting room with a 4x4 (square array) arrangement of seats such that each person will be taller than both the person in front of and left to her/him.
你要安排16個身高不同的傢伙坐在會談室, 座位排成如4x4 的方陣。而每個人都要比在他前方或左方的人來得高。

In how many different ways can this operation be carried out?
你有幾種排法??

If the question was for 9 people and a 3x3 arrangement of seats, then the answer would be 42.
假如這個問題改成9個傢伙坐在3x3的座位時, 答案會是42。

呃, 好吧!!我們將這些人從矮到高編號1-16(最矮的是1, 而16是最高的)。想想看每個位子可能坐哪些人…

20090121-01 by you.

然後我們得到一個結論 – 這種做法完全沒用!!因為你不可能把所有可能性相乘。

那我們也許可以試著一個一個去放…
首先是第一個人(其實16也可以直接放)

20090121-02 by you.

再來是第二個人, 第二個人雖然有兩種放法, 但我們只要去思考其中一種, 再將最後答案乘以2就好了, 因為另一種只是45度角的鏡射。

20090121-03 by you.然後第三個人…

20090121-04 by you.

第四個人…呃, 好像方式繁殖得有點快…

20090121-05 by you.

第五…『老子不幹了!!』, 比黃金鼠還會生。

20090121-06 by you.

顯然這也不是個好方法。你可能要有很大張的紙, 配上如証嚴法師的脾氣。

我們很期待可以一步就做完, 順順利利一路做下去, 但是事與願違。也許我們該從3x3去思索, 它是怎麼算出42的。
不過你還記得嗎??3x3 有9個人, 但是我剛才到了第5個人就凍未條了。

也許該再更少一點, 像是…2x2??
或乾脆一點, 反正圖的版面夠, 把2-4的可能性都畫出來好了。

20090121-07 by you.

然後是5格, 你就可以先放入1後, 再依剩下圖形來看有幾種可能。你不用再重新數, 因為4格的可能性有幾種你都算出來了。

20090121-08 by you.

20090121-09 by you.

20090121-10 by you.

接著6格, 我就舉其中一例來說明就好了-

20090121-11 by you.

也許你會認為到後面數字越多, 會不會有漏掉可能性的情況。
其實不會, 有三個原因 –

1. 有些圖形根本不用列入考慮

20090121-12 by you.

基本上放的過程中, 上面一定比下面來得晚放, 右邊一定比左邊來得晚放, 而我們到了最後, 是要檢查剩餘格子的, 所以不可能有以上的情況發生。

2. 邊界只有四格, 所以可能性會減少很多

20090121-13 by you.

不會發生像上面的圖形

3. 就算漏掉了, 因為我們是依圖形的區域來做統計, 所以不會有關係。而且到了下一步, 你自然會發現。

20090121-14 by you.

像是可能我們漏掉了6的其中一種可能, 但是當我們要到7格時, 自然就會發現缺了這個資訊, 要補也還來得及。

基本上到12就差不多了。

剩下的就用以下的圖形, 依序分析有幾種, 再加起來。

20090121-05 by you.

當然, 不要忘了最後答案還要再乘以2, 用來表示2位置的45度鏡射。

萬丈高樓平地起, 我們就這樣一層一層地搭, 每蓋一層樓, 都是為了下一層樓打基礎, 讓它有穩固的平面可以支撐。

最終, 我們完成了這個答案。

FB留言板

PeoPo 討論區

回應文章建議規則:

  • 文章屬於開放討論空間,回應文章的議題與內容不代表本站的立場
  • 於明知不實或過度謾罵之言論,本站及文章撰寫者保留刪除權
  • 請勿留下身份證字號、住址等個人隱私資料,以免遭人盜用,本站不負管理之責
  • 回應禁止使用HTML語法
祈求一顆天真的心

對耶, 我沒想到可以用這招...
你這樣一解釋我大概懂了, 的確這樣比較快..

至於我的答案我真的忘了, 可能也錯了吧, 畢竟我用了太麻煩的方法...
謝謝你的構想, 超厲害的!!

(明天有空再看你的詳細解決, 我網咖時間快到了, 還有別的事要做....:p)

Cheng-Lin Tsao

我驗算了一下,答案變成26202了 XD

我把詳細過程都打到google spreadsheet了,有空的話幫我看一下哪裡錯了吧 :p
http://spreadsheets.google.com/ccc?key=0AtXSKIA0uUItdGF1bmlhQUJseVBIczZJ...

計算都輸入成公式,應該很好理解。
每一個狀況裡,最小數字必然要填在最左下的格子裡,有多個選擇時就分開考慮然後加起來。
例如7格的最後一個狀況,最小數字填A時,剩下的格子會分成兩組:一格、五格的狀況三,故有90種填法,
最小數字填B時,剩下的格子分成兩組:四格的狀況四、兩格,故有30種填法,
總共120種填法。

我想算到八格狀況應該是夠用了,例如你給的排列,就是屬於「1~8的排列為八格狀況四,9~16的排列為八格狀況五」的其中一種。

祈求一顆天真的心

先謝謝你的回覆啊...
Puzzleup 的題型大多是如此的,
至於你問我算多少, 哈, 我也忘了, 而官網上我之前輸入的答案也被洗掉
所以我沒法回答...

但絕對不是21690, 而且還比那個數字小得多...

基本上你所言只要算到8格....呃....我列出一個可能的排列給你, 你就知道不能用你所說的方式算了

07 11 14 16
06 09 12 15
05 08 10 13
01 02 03 04

這道題要分析得更細才行

Cheng-Lin Tsao

回一篇舊文,這題你算的答案是多少?我算21690,官網上的確也沒放答案 @@

計算過程還蠻dynamic programming的,事實上應該算到8格的狀況就夠了,剩下的用乘的(1~8的排列 * 9~16的排列)

0

加入時間: 2007.06.06

祈求一顆天真的心

加入時間: 2007.06.06
157則報導
1則影音
0則OnTV

作者其他報導

PuzzleUp 2018

2018-07-26
瀏覽:
2,459
推:
0
回應:
0

[比賽] 2015 U.S. Puzzle Championship

2015-09-05
瀏覽:
1,859
推:
0
回應:
0

[比賽] WPF Puzzle Grand Prix 2015 - 第 8 場

2015-07-28
瀏覽:
1,457
推:
6
回應:
0

[比賽] WPF Sudoku Grand Prix 2015 - 第 8 場

2015-07-18
瀏覽:
1,834
推:
5
回應:
0

2013 Puzzleup 線上賽

2013-07-13
瀏覽:
1,260
推:
0
回應:
0

2012 U.S. Sudoku Team Qualifying

2012-09-01
瀏覽:
2,483
推:
0
回應:
5

US Puzzle Championship 2012

2012-08-25
瀏覽:
2,479
推:
0
回應:
2

[影片介紹]街舞狂潮

2010-11-08
瀏覽:
3,288
推:
0
回應:
0

特教影片 - 海洋天堂

2010-09-15
瀏覽:
5,549
推:
3
回應:
3

PuzzleUp 2008 討論系列5 – 疊床架屋 Part I

搜尋表單

目前累積了151,414篇報導,共11,348位公民記者

目前累積了151,414篇報導

11,348位公民記者