文学城论坛
+A-

谁能用图论来解这道题? 恳请牛人出着。

SwiperTheFox 2010-04-13 08:57:38 ( reads)

用123456六个数组成一个六位数, 要求任何相邻的两个数互质。

用排列组合有几种解法,思路差不多。 但是觉得都比较 ad hoc, 不具推广性--如果各任意大的数,比如100,你怎么算?

想到一个图论的思路,但想了一天没想出来。当然顺着这个思路编程序好算。 就不知道有没有用图论的理论直接解决的办法。

我的思路是这样的: 把自然数看作顶点, 把互质的数用边连起来。 这道题就变成了,从各个顶点出发,遍历所有顶点,有几条路线? 感觉上应该跟连通图有关。

跟帖(25)

SwiperTheFox

2010-04-13 09:02:14

忘了把原题写完整,应该是:

sqgs

2010-04-13 12:58:36

回复:忘了把原题写完整,应该是:

SwiperTheFox

2010-04-13 13:21:33

你有没有考虑

jinjing

2010-04-13 20:28:01

144

SwiperTheFox

2010-04-14 08:21:48

no

jinjing

2010-04-14 17:33:29

70

SwiperTheFox

2010-04-15 09:55:41

You are close, but not exactly

jinjing

2010-04-15 13:26:38

72=(5!-4!*2)

SwiperTheFox

2010-04-16 09:44:10

This seems to be the best solution, can you reveal details?

jinjing

2010-04-17 05:17:39

Thanks.

皆兄弟也

2010-04-16 12:19:17

details? please!

jinjing

2010-04-16 16:00:53

回复:details? please!

皆兄弟也

2010-04-16 20:55:59

2*4!可以理解,5!仍不太明白。anyway, thank you!

jinjing

2010-04-17 05:43:11

回复:2*4!可以理解,5!仍不太明白。anyway, thank you!

aisanguo

2010-04-13 15:44:53

回复:谁能用图论来解这道题? 恳请牛人出着。

jinjing

2010-04-13 18:52:23

You're right.If don't think about first and last Nbs.Erler paths

twfx

2010-04-13 21:09:41

0.

SwiperTheFox

2010-04-14 02:25:08

1虽然不是质数但

SwiperTheFox

2010-04-14 02:27:10

进一步的思路,觉得可以彻底解决

SwiperTheFox

2010-04-14 02:41:41

这个不对

皆兄弟也

2010-04-15 17:30:56

非图论解一:偶数不相邻,3,6不相邻,共32种。

皆兄弟也

2010-04-15 18:11:51

非图论解二:偶数不相邻,共72种。其中3,6相邻,40种。72-40=32种

jinjing

2010-04-16 06:14:25

偶数不相邻,共144种。其中3,6相邻,72种。144-72=72种

皆兄弟也

2010-04-16 08:24:31

我的结论不对,少算了两种情况。谢谢!

mathg

2010-08-15 21:46:19

think easy - combinatorial solution 回复:谁能用图论来解这道题? 恳请牛人出着。