2014年8月6日 星期三

訓練數學感 28 ─ 植樹問題

https://4rdp.blogspot.com/2014/08/28.html






H4

A

H2



B




H5
C
H1




D


H3


E
1
2
3
4
5


上圖表示一個村落五戶人家 (綠色 H),現在要在空地種五棵樹須鄰近住家 (例如 B4 位置種一棵算鄰近 H4 但不鄰近 H5),並使每一行每一列看起來都有一棵樹,請問如何安排?

進階問題,如果一棵沒辦法,那有辦法安排每戶種兩棵鄰近的樹嗎?

加分題:
如果上述問題無解,請重新安排房屋與樹,兩兩相鄰,並且每行每列都有一棵樹一棟房子?

16 則留言:

  1. 無解。 使用 DFS 演算法。
    進階跟加分題看不懂...

    回覆刪除
    回覆
    1. 嗯,一棵樹確實是無解。
      進階題,有無可能每戶房子旁邊各種兩棵樹,使每行每列看起來各有兩棵樹?
      加分題,雷同初始題目,五棟房屋全部重新排置,並且旁邊也須種一棵樹,使每行每列看起來有一棟房子,以及一棵樹?

      刪除
    2. 對了補充 DFS 是深度優先搜索演算法(Depth-First-Search)。

      刪除
  2. 進階題好像無解,不過不知道應該怎麽證明。
    思路:有四個房子只有三個樹坑,一個房子有四個樹坑。
    把所有能種樹的坑全部種滿,每列樹木總數依次為3,4,3,3,3,
    每行樹木總數依次為3,4,3,3,3。
    因爲有一個房子多種了一棵樹的關係,所以要符合要求必須除去一棵。
    顯然,只有除去(4,4)這棵樹滿足條件。但可惜,這個位置沒有樹!
    至此,僅僅證明到“在空地種十五棵樹須鄰近住家,使每一行每一列看起來都有三棵樹”是不可能的。

    回覆刪除
    回覆
    1. Linke,

      你提供的是每行每列種三棵樹的解答,它確實是不可能,但是種兩棵樹應該有解。

      刪除
  3. 這問題其實我沒有寫程式。只是用DFS的方式在紙上畫出search tree. 類似的問題有八皇后問題。可以參考: http://programming.im.ncnu.edu.tw/exapmle_for_java/9.htm
    或者冼鏡光老師的 名題精選百則:技巧篇

    回覆刪除
    回覆
    1. 行天下,

      謝謝你分享許多資訊,有你的加持,讓這裡的討論內容更有深度。
      Google 冼鏡光老師的書,可參考 http://www.books.com.tw/products/0010488984

      刪除
    2. 八皇后問題我點擊鏈接看過了。
      裏面的要求比這道題更加苛刻(這道題只是八隻車不用考慮對角綫),
      解法一定會多不少。

      刪除
  4. 0 1 0 x 1
    0 x 1 1 0
    1 0 0 1 x
    x 0 1 0 1
    1 1 x 0 0
    在1的位置上种樹,保證了每個x旁邊都有兩棵樹。
    雖然我運氣好,只試了四次,但這題是否有規律可循呢?

    回覆刪除
    回覆
    1. 嗯,正解,我不確定是否還有其它的解法 (屏除鏡射的另解)。
      Linke 你所提的規律,意指哪方面的?

      刪除
    2. 我的意思是,關於這道題的解法,
      除了一個個的試(窮舉),還有別的方法嗎?

      刪除
    3. 0 0 0 1 x
      1 x 0 0 0
      0 0 1 x 0
      0 0 x 0 1
      x 1 0 0 0
      想問上圖是否符合加分題的要求?(覺得應該不會接受 :(

      刪除
    4. Linke,

      通常組合排列型態的問題,現代的解法都是用電腦程式求解,就是你說的窮舉法,這題用網友行天下所述 DFS 一定可以找出所有的解答。至於有無其它的解法,恕我魯鈍應該沒有。

      關於加分題,有一棵樹是共有,一棵樹又無主,確實不是期望的解答。再加油,看能不能解出來,或是證明是無解,我的直覺是無解。

      刪除
  5. 這道題的通解討論(除去1*1和2*2):
    當3*3時,房屋位置只有如下兩種情況,
    00x
    0x0
    x00
    以及
    0x0
    00x
    x00
    這兩種類型無論怎樣种樹都不符合要求(可窮舉)。
    當4*4時,只需要把房子和樹兩兩分組,在有同組房子的行或列种樹,幾乎隨便種都符合要求。

    回覆刪除
  6. 當5*5時,可以把5的邊長劃分成4+1或3+2。
    4+1:即先填好符合要求的4*4區域,再把剩下的一間房和一棵樹放入。
    這樣,其實最後可以放的區域只有1*1,放了房子就不能放樹。無解。
    3+2:即先天好符合要求的3*3區域,再把剩下的兩間房子和兩棵樹放入。
    這樣,在5*5區域中會剩下兩個1*2的區域。只要這兩個區域不相鄰,
    也是幾乎隨便放都符合要求,比如:
    0aaa0
    0aaa0
    0aaa0
    1000x
    x0001 (假設a區域能放成符合要求的形狀)
    但,這個假設不成立!
    所以5*5區域不能放成符合要求的形狀。
    5*5中所有情況都不成立,故無解。
    推廣:所有奇數的正方形區域都無解,所有的偶數正方形區域都有不止一個解。

    回覆刪除
    回覆
    1. Linke,

      厲害,沒想到一題看似簡單的題目,經過你仔細地剖析,這個加分題通解的型態,已經被破解了!

      刪除