读书人

求算法思路,该如何处理

发布时间: 2012-02-11 09:51:34 作者: rapoo

求算法思路
红黄蓝白四种颜色珠子若干个,用6棵珠子穿成一串。问能串成多少种不同的串

[解决办法]
考虑排列组合,我先占个沙发。。。
[解决办法]
各种颜色的都同样多的话,我总觉得是个排列的问题,是不是4的6次方啊。
[解决办法]
这是个有序问题。
R-Y-R-Y-R-Y

Y-R-Y-R-Y-R
是不同的。

[解决办法]
参考
http://community.csdn.net/Expert/topic/5489/5489376.xml
题目有两种不同理解:
第一种只把旋转后会相同的看成一种。
第二种把翻转后会相同的方案也看成一种。
对于第一种观点,总共有6个置换:
一个单位置换: x1^6,
二个置换为长度为6的轮换: 2*x6
二个包含两长度为3的轮换:2*x3^2
一个包含3个长度为2的轮换:x2^3
即颜色多项式为:
x1^6+x2^3+2*x3^2+2*x6
如果用第二种观点,那么还多了6种翻转,都是两个数不变,另外4个成对交换,所以是
6*x1^2*x2^2
所以颜色多项式为
x1^6+x2^3+2*x3^2+2*x6+6*x1^2*x2^2
[解决办法]
所以最终结果为
P(4,4,4,4,4,4)/|G| (也就是将上面多项式中所有x1,x2,x3,x4,x5,x6全部用4代替,然后除以置换数目)
,对于第一种观点,结果是
(4^6+4^3+2*4^2+2*4)/6=700
而对于第二种观点,结果是
(4^6+4^3+2*4^2+2*4+6*4^2*4^2)/12=478
[解决办法]
这是俺们尊敬的老大以前写的群论科普文章:

http://bbs.oursci.org/showthread.php?threadid=10227

本来打算回去恶补一番的,不过到底还是让琐事给耽误了。
[解决办法]
(4^6 - 4^3) / 2 + 4^3 = (4096 - 64) / 2 + 64 = 2016 + 64 = 2080

读书人网 >软件架构设计

热点推荐