誰能用圖論來解這道題? 懇請牛人出著。

來源: 2010-04-13 08:57:38 [] [博客] [舊帖] [給我悄悄話] 本文已被閱讀: 次 (450 bytes)
本文內容已被 [ SwiperTheFox ] 在 2010-04-15 10:02:55 編輯過。如有問題,請報告版主或論壇管理刪除.
用123456六個數組成一個六位數, 要求任何相鄰的兩個數互質。

用排列組合有幾種解法,思路差不多。 但是覺得都比較 ad hoc, 不具推廣性--如果各任意大的數,比如100,你怎麽算?

想到一個圖論的思路,但想了一天沒想出來。當然順著這個思路編程序好算。 就不知道有沒有用圖論的理論直接解決的辦法。

我的思路是這樣的: 把自然數看作頂點, 把互質的數用邊連起來。 這道題就變成了,從各個頂點出發,遍曆所有頂點,有幾條路線? 感覺上應該跟連通圖有關。

所有跟帖: 

忘了把原題寫完整,應該是: -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (82 bytes) () 04/13/2010 postreply 09:02:14

回複:忘了把原題寫完整,應該是: -sqgs- 給 sqgs 發送悄悄話 sqgs 的個人群組 (112 bytes) () 04/13/2010 postreply 12:58:36

你有沒有考慮 -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (20 bytes) () 04/13/2010 postreply 13:21:33

144 -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (79 bytes) () 04/13/2010 postreply 20:28:01

no -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (26 bytes) () 04/14/2010 postreply 08:21:48

70 -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (220 bytes) () 04/14/2010 postreply 17:33:29

You are close, but not exactly -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (364 bytes) () 04/15/2010 postreply 09:55:41

72=(5!-4!*2) -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (10 bytes) () 04/15/2010 postreply 13:26:38

This seems to be the best solution, can you reveal details? -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (6 bytes) () 04/16/2010 postreply 09:44:10

Thanks. -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (0 bytes) () 04/17/2010 postreply 05:17:39

details? please! -皆兄弟也- 給 皆兄弟也 發送悄悄話 皆兄弟也 的博客首頁 皆兄弟也 的個人群組 (0 bytes) () 04/16/2010 postreply 12:19:17

回複:details? please! -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (221 bytes) () 04/16/2010 postreply 16:00:53

2*4!可以理解,5!仍不太明白。anyway, thank you! -皆兄弟也- 給 皆兄弟也 發送悄悄話 皆兄弟也 的博客首頁 皆兄弟也 的個人群組 (0 bytes) () 04/16/2010 postreply 20:55:59

回複:2*4!可以理解,5!仍不太明白。anyway, thank you! -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (161 bytes) () 04/17/2010 postreply 05:43:11

回複:誰能用圖論來解這道題? 懇請牛人出著。 -aisanguo- 給 aisanguo 發送悄悄話 aisanguo 的博客首頁 aisanguo 的個人群組 (187 bytes) () 04/13/2010 postreply 15:44:53

You're right.If don't think about first and last Nbs.Erler paths -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (98 bytes) () 04/13/2010 postreply 18:52:23

0. -twfx- 給 twfx 發送悄悄話 twfx 的個人群組 (35 bytes) () 04/13/2010 postreply 21:09:41

1雖然不是質數但 -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (120 bytes) () 04/14/2010 postreply 02:25:08

進一步的思路,覺得可以徹底解決 -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (298 bytes) () 04/14/2010 postreply 02:27:10

這個不對 -SwiperTheFox- 給 SwiperTheFox 發送悄悄話 SwiperTheFox 的博客首頁 SwiperTheFox 的個人群組 (28 bytes) () 04/14/2010 postreply 02:41:41

非圖論解一:偶數不相鄰,3,6不相鄰,共32種。 -皆兄弟也- 給 皆兄弟也 發送悄悄話 皆兄弟也 的博客首頁 皆兄弟也 的個人群組 (954 bytes) () 04/15/2010 postreply 17:30:56

非圖論解二:偶數不相鄰,共72種。其中3,6相鄰,40種。72-40=32種 -皆兄弟也- 給 皆兄弟也 發送悄悄話 皆兄弟也 的博客首頁 皆兄弟也 的個人群組 (700 bytes) () 04/15/2010 postreply 18:11:51

偶數不相鄰,共144種。其中3,6相鄰,72種。144-72=72種 -jinjing- 給 jinjing 發送悄悄話 jinjing 的個人群組 (187 bytes) () 04/16/2010 postreply 06:14:25

我的結論不對,少算了兩種情況。謝謝! -皆兄弟也- 給 皆兄弟也 發送悄悄話 皆兄弟也 的博客首頁 皆兄弟也 的個人群組 (0 bytes) () 04/16/2010 postreply 08:24:31

think easy - combinatorial solution 回複:誰能用圖論來解這道題? 懇請牛人出著。 -mathg- 給 mathg 發送悄悄話 mathg 的個人群組 (145 bytes) () 08/15/2010 postreply 21:46:19

加跟帖:

當前帖子已經過期歸檔,不能加跟帖!
回到頂部