谁能用图论来解这道题? 恳请牛人出着。
用123456六个数组成一个六位数, 要求任何相邻的两个数互质。
用排列组合有几种解法,思路差不多。 但是觉得都比较 ad hoc, 不具推广性--如果各任意大的数,比如100,你怎么算?
想到一个图论的思路,但想了一天没想出来。当然顺着这个思路编程序好算。 就不知道有没有用图论的理论直接解决的办法。
我的思路是这样的: 把自然数看作顶点, 把互质的数用边连起来。 这道题就变成了,从各个顶点出发,遍历所有顶点,有几条路线? 感觉上应该跟连通图有关。
SwiperTheFox
2010-04-13 09:02:14忘了把原题写完整,应该是: