当前位置: 代码迷 >> 数据结构与算法 >> 求算法思路,该如何处理
  详细解决方案

求算法思路,该如何处理

热度:401   发布时间:2016-05-23 09:14:17.0
求算法思路
红黄蓝白四种颜色珠子若干个,用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
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Sat Sep 23 09:56:13 CST 2017
  • 最近登录:Sat Sep 23 09:56:13 CST 2017
  • 最近登录:Sat Sep 23 09:56:13 CST 2017
  • 最近登录:Sat Sep 23 09:56:13 CST 2017
  • 最近登录:Sat Sep 23 09:56:13 CST 2017