tag:blogger.com,1999:blog-3550204829234352390.post5035893741129247324..comments2024-03-27T09:13:48.546+08:00Comments on 研發養成所 ( Bridan's Blog - 4rdp, For R&D Person ): 訓練數學感 28 ─ 植樹問題Bridanhttp://www.blogger.com/profile/17055047757114667099noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3550204829234352390.post-7472660676835994632014-09-02T21:53:59.551+08:002014-09-02T21:53:59.551+08:00Linke,
厲害,沒想到一題看似簡單的題目,經過你仔細地剖析,這個加分題通解的型態,已經被破解了...Linke,<br /><br />厲害,沒想到一題看似簡單的題目,經過你仔細地剖析,這個加分題通解的型態,已經被破解了!Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-31528271164401959172014-09-02T13:36:23.442+08:002014-09-02T13:36:23.442+08:00當5*5時,可以把5的邊長劃分成4+1或3+2。
4+1:即先填好符合要求的4*4區域,再把剩下的一...當5*5時,可以把5的邊長劃分成4+1或3+2。<br />4+1:即先填好符合要求的4*4區域,再把剩下的一間房和一棵樹放入。<br />這樣,其實最後可以放的區域只有1*1,放了房子就不能放樹。無解。<br />3+2:即先天好符合要求的3*3區域,再把剩下的兩間房子和兩棵樹放入。<br />這樣,在5*5區域中會剩下兩個1*2的區域。只要這兩個區域不相鄰,<br />也是幾乎隨便放都符合要求,比如:<br />0aaa0<br />0aaa0<br />0aaa0<br />1000x<br />x0001 (假設a區域能放成符合要求的形狀)<br />但,這個假設不成立!<br />所以5*5區域不能放成符合要求的形狀。<br />5*5中所有情況都不成立,故無解。<br />推廣:所有奇數的正方形區域都無解,所有的偶數正方形區域都有不止一個解。<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-13687575173414787342014-09-02T12:42:00.529+08:002014-09-02T12:42:00.529+08:00這道題的通解討論(除去1*1和2*2):
當3*3時,房屋位置只有如下兩種情況,
00x
0x0
x...這道題的通解討論(除去1*1和2*2):<br />當3*3時,房屋位置只有如下兩種情況,<br />00x<br />0x0<br />x00<br />以及<br />0x0<br />00x<br />x00<br />這兩種類型無論怎樣种樹都不符合要求(可窮舉)。<br />當4*4時,只需要把房子和樹兩兩分組,在有同組房子的行或列种樹,幾乎隨便種都符合要求。Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-10261862112024229802014-08-28T22:47:45.836+08:002014-08-28T22:47:45.836+08:00Linke,
通常組合排列型態的問題,現代的解法都是用電腦程式求解,就是你說的窮舉法,這題用網友行...Linke,<br /><br />通常組合排列型態的問題,現代的解法都是用電腦程式求解,就是你說的窮舉法,這題用網友行天下所述 DFS 一定可以找出所有的解答。至於有無其它的解法,恕我魯鈍應該沒有。<br /><br />關於加分題,有一棵樹是共有,一棵樹又無主,確實不是期望的解答。再加油,看能不能解出來,或是證明是無解,我的直覺是無解。<br />Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-1495424708992758162014-08-28T09:03:19.693+08:002014-08-28T09:03:19.693+08:000 0 0 1 x
1 x 0 0 0
0 0 1 x 0
0 0 x 0 1
x 1 0 0 0
...0 0 0 1 x<br />1 x 0 0 0<br />0 0 1 x 0<br />0 0 x 0 1<br />x 1 0 0 0<br />想問上圖是否符合加分題的要求?(覺得應該不會接受 :(Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-7226533591417502842014-08-28T08:42:12.521+08:002014-08-28T08:42:12.521+08:00八皇后問題我點擊鏈接看過了。
裏面的要求比這道題更加苛刻(這道題只是八隻車不用考慮對角綫),
解法一...八皇后問題我點擊鏈接看過了。<br />裏面的要求比這道題更加苛刻(這道題只是八隻車不用考慮對角綫),<br />解法一定會多不少。Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-91884001422423085292014-08-28T08:36:35.748+08:002014-08-28T08:36:35.748+08:00我的意思是,關於這道題的解法,
除了一個個的試(窮舉),還有別的方法嗎?我的意思是,關於這道題的解法,<br />除了一個個的試(窮舉),還有別的方法嗎?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-55184042470647903842014-08-27T21:14:41.005+08:002014-08-27T21:14:41.005+08:00嗯,正解,我不確定是否還有其它的解法 (屏除鏡射的另解)。
Linke 你所提的規律,意指哪方面的?...嗯,正解,我不確定是否還有其它的解法 (屏除鏡射的另解)。<br />Linke 你所提的規律,意指哪方面的?<br />Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-30918102977977146972014-08-27T12:19:55.778+08:002014-08-27T12:19:55.778+08:000 1 0 x 1
0 x 1 1 0
1 0 0 1 x
x 0 1 0 1
1 1 x 0 0
...0 1 0 x 1<br />0 x 1 1 0<br />1 0 0 1 x<br />x 0 1 0 1<br />1 1 x 0 0<br />在1的位置上种樹,保證了每個x旁邊都有兩棵樹。<br />雖然我運氣好,只試了四次,但這題是否有規律可循呢?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-1060978551178765842014-08-26T21:20:05.836+08:002014-08-26T21:20:05.836+08:00行天下,
謝謝你分享許多資訊,有你的加持,讓這裡的討論內容更有深度。
Google 冼鏡光老師的書...行天下,<br /><br />謝謝你分享許多資訊,有你的加持,讓這裡的討論內容更有深度。<br />Google 冼鏡光老師的書,可參考 http://www.books.com.tw/products/0010488984Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-66346325701979472022014-08-25T23:43:04.244+08:002014-08-25T23:43:04.244+08:00這問題其實我沒有寫程式。只是用DFS的方式在紙上畫出search tree. 類似的問題有八皇后問題...這問題其實我沒有寫程式。只是用DFS的方式在紙上畫出search tree. 類似的問題有八皇后問題。可以參考: http://programming.im.ncnu.edu.tw/exapmle_for_java/9.htm<br />或者冼鏡光老師的 名題精選百則:技巧篇行天下https://www.blogger.com/profile/04992727596324526135noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-38758410368811586142014-08-25T21:53:40.127+08:002014-08-25T21:53:40.127+08:00Linke,
你提供的是每行每列種三棵樹的解答,它確實是不可能,但是種兩棵樹應該有解。Linke,<br /><br />你提供的是每行每列種三棵樹的解答,它確實是不可能,但是種兩棵樹應該有解。Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-87514179428522998052014-08-25T17:19:34.807+08:002014-08-25T17:19:34.807+08:00進階題好像無解,不過不知道應該怎麽證明。
思路:有四個房子只有三個樹坑,一個房子有四個樹坑。
把所有...進階題好像無解,不過不知道應該怎麽證明。<br />思路:有四個房子只有三個樹坑,一個房子有四個樹坑。<br />把所有能種樹的坑全部種滿,每列樹木總數依次為3,4,3,3,3,<br />每行樹木總數依次為3,4,3,3,3。<br />因爲有一個房子多種了一棵樹的關係,所以要符合要求必須除去一棵。<br />顯然,只有除去(4,4)這棵樹滿足條件。但可惜,這個位置沒有樹!<br />至此,僅僅證明到“在空地種十五棵樹須鄰近住家,使每一行每一列看起來都有三棵樹”是不可能的。Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-48009232079334622302014-08-22T23:41:01.662+08:002014-08-22T23:41:01.662+08:00對了補充 DFS 是深度優先搜索演算法(Depth-First-Search)。對了補充 DFS 是深度優先搜索演算法(Depth-First-Search)。Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-66504513958577340582014-08-22T23:38:28.316+08:002014-08-22T23:38:28.316+08:00嗯,一棵樹確實是無解。
進階題,有無可能每戶房子旁邊各種兩棵樹,使每行每列看起來各有兩棵樹?
加分題...嗯,一棵樹確實是無解。<br />進階題,有無可能每戶房子旁邊各種兩棵樹,使每行每列看起來各有兩棵樹?<br />加分題,雷同初始題目,五棟房屋全部重新排置,並且旁邊也須種一棵樹,使每行每列看起來有一棟房子,以及一棵樹?Bridanhttps://www.blogger.com/profile/17055047757114667099noreply@blogger.comtag:blogger.com,1999:blog-3550204829234352390.post-78350990662660680662014-08-22T01:00:38.165+08:002014-08-22T01:00:38.165+08:00無解。 使用 DFS 演算法。
進階跟加分題看不懂...無解。 使用 DFS 演算法。<br />進階跟加分題看不懂...行天下https://www.blogger.com/profile/04992727596324526135noreply@blogger.com