数学研发论坛

 找回密码
 欢迎注册
查看: 2013|回复: 15

[讨论] 魔方循环问题

[复制链接]
发表于 2009-10-4 09:12:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
问题表述如下:
对于魔方来说,给定一个指定步骤,请问重复旋转多少次会回到初始状态?
由于魔方状态有限,所以一定是会回到初始状态的。

具体举例:
如果进行R变换,需要4次,就是说将右侧面旋转4次就会回到初态;
如果进行R2变换,需要2次就可以了;
如果进行RU变换,则需要105次才会第一次回到初态!

附注:
对于不了解魔方公式定义的朋友我进行一下变换代号说明:
R:右手面顺时针旋转(right)
U:上面顺时针旋转(up)
F:前面顺时针旋转(front)
B:后面顺时针旋转(back)
L:左手面顺时针旋转(left)
D:下面顺时针旋转(down)
顺时针的定义为正面朝向该面进行判断,
后面加个2表示旋转两次,加' (一撇)表示逆时针旋转。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-10-4 09:12:41 | 显示全部楼层
本帖最后由 winxos 于 2009-10-4 09:40 编辑

我做了一些简单的分析,比如对于长度为6的只有顺时针旋转的公式,循环次数最长为720,
回复后可以查看。

游客,如果您要查看本帖隐藏内容请回复
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-4 14:58:41 | 显示全部楼层
群论问题.
对于任何一个步骤,魔方所有状态树目为这个次数的倍数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-10-4 19:02:42 | 显示全部楼层
很实际的问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-12-31 03:51:15 | 显示全部楼层
为什么一定要回复才能查看呢。: (
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-1-7 11:09:18 | 显示全部楼层
Lwins_G 发表于 2013-12-31 03:51
为什么一定要回复才能查看呢。: (


回复查看之后,发现链接都已经失效,人世间悲催之事莫过如此,

如果你感兴趣,我可以帮你 把楼主 拉回来。

点评

不用了,这个还算是比较基础的问题。  发表于 2014-1-7 14:39
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-16 12:29:06 | 显示全部楼层
同一个操作循环1260次,一定会回到原来的状态
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-23 13:41:12 | 显示全部楼层
我以前编程算过这个,就是你给一套公式,我程序算做多少次能回去。
不过没试过随机生成公式的,我觉得楼上1260次这个结论很神奇,我要再做做。

点评

何必追求所谓的群论的知识? 用mathematica数值计算两下不就可以了吗?  发表于 2018-11-23 17:25
https://bbs.emath.ac.cn/thread-15591-1-1.html 看看这个能回复吗?  发表于 2018-11-23 14:00
你怎么编程的?  发表于 2018-11-23 14:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-23 21:20:02 | 显示全部楼层
魔方8个角上块可以相互交换,12个边上块可以互相交换,两者分别构成一个8阶置换群和12阶置换群。(这时还没有考虑这20个块的方向)
另外我们知道每次变换都是偶置换(可以通过偶数次两个元素交换得到),所以变换能够达到的情况也必须是偶置换,所以只有两种情况
i)8阶置换群中的偶置换搭配12阶置换群的偶置换
ii)8阶置换群中的奇置换搭配12阶置换群的奇置换
而置换群中每个置换都可以分解成一些不相交的轮换,比如(1345)(276)(8)就是8阶置换群中一个变换分解为互不相交的轮换的例子,就是1号到3号,3号到4号,4号到5号,5号到1号,2号到7号,7号到6号,6号到2号,8号保持位置不变。这样分解的好处是可以非常容易计算出这个置换的阶,它就是所有轮换数目的最小公倍数,比如这个例子就是[4,3,1]=12.另外需要注意的是偶数个数的轮换是奇置换,奇数个数的轮换是偶置换。
很显然每个置换的阶之和它这种分解模式相关,于是我们就可以很简单的穷举了。
比如8阶的可以分解为
8   (奇置换,阶数为8)
7+1 (偶置换,阶数7)
6+2 (偶置换,阶数6)
6+1+1(奇置换,阶数6)
5+2+1 (奇置换,阶数10)
...
我们只需要找出其中阶数大的如
5+3(偶置换,阶数15)
4+3+1(奇置换,阶数12)
而对于12阶置换群有
9+2+1 (奇置换,阶数18)
8+3+1(奇置换,阶数24)
7+5(偶置换,阶数35)
7+3+2(奇置换,阶数42)
6+5+1(奇置换,阶数30)
5+3+2+1(奇置换,阶数30)
...当然最好计算机穷举
然后分析它们的组合,要求奇置换配奇置换,偶置换配偶置换,组合阶数的最小公倍数尽量大
计算机得出最大组合是210,
比如S8中取6阶偶置换,S12中35阶偶置换,或
   S8中取7阶偶置换,S12中取30阶偶置换,或
   S8中取15阶偶置换,S12中取14阶偶置换,或
   S8中取10阶奇置换,S12中取42阶奇置换。
所以我们得出最多210轮后,所有的积木块都返回了它应该到达的位置。只是这时又部分积木块的取向可能不对,由于角上3种方向,边上2种,所以最多重复6次后可以使得取向也正确,所以最大阶数是210*6=1260
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-23 21:21:57 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <set>
  3. using namespace std;
  4. int gcd(int a, int b)
  5. {
  6.     if(a==0)return b;
  7.     return gcd(b%a, a);
  8. }
  9. int lcm(int a, int b)
  10. {
  11.     return (a/gcd(a,b))*b;
  12. }
  13. #define MAX_ORDER 12
  14. set<int> even[MAX_ORDER+1];
  15. set<int> odd[MAX_ORDER+1];
  16. void calset()
  17. {
  18.     int i,j;
  19.     set<int>::iterator it;
  20.     even[1].insert(1);//order 1 reached for even perm (1)
  21.     even[2].insert(1);//order 1 reached for even perm (1)(2)
  22.     odd[2].insert(2);//order 2 reach for odd (12)
  23.     for(i=3;i<=MAX_ORDER;i++){
  24.        if(i&1){
  25.           even[i].insert(i);
  26.        }else{
  27.           odd[i].insert(i);
  28.        }
  29.        for(j=i-1;j>=2;j--){
  30.           //use number j
  31.           if(j&1){
  32.               //use even perm with j numbers
  33.               for(it=even[i-j].begin();it!=even[i-j].end();++it){
  34.                    even[i].insert(lcm(*it,j));
  35.               }
  36.               for(it=odd[i-j].begin();it!=odd[i-j].end();++it){
  37.                    odd[i].insert(lcm(*it,j));
  38.               }
  39.           }else{
  40.               //use odd perm with j numbers
  41.               for(it=even[i-j].begin();it!=even[i-j].end();++it){
  42.                    odd[i].insert(lcm(*it,j));
  43.               }
  44.               for(it=odd[i-j].begin();it!=odd[i-j].end();++it){
  45.                    even[i].insert(lcm(*it,j));
  46.               }
  47.           }
  48.        }
  49.     }
  50. }

  51. void find_max_8_12()
  52. {
  53.     set<int>::iterator it1,it2;
  54.     int maxorder=0;
  55.     calset();
  56.     for(it1=even[8].begin();it1!=even[8].end();++it1){
  57.        for(it2=even[12].begin();it2!=even[12].end();++it2){
  58.          int r=lcm(*it1,*it2);
  59.          if(r>=maxorder){
  60.              maxorder=r;
  61.              printf("find order %d, even8=%d, even12=%d\n",maxorder, *it1, *it2);
  62.          }
  63.        }
  64.     }
  65.     for(it1=odd[8].begin();it1!=odd[8].end();++it1){
  66.        for(it2=odd[12].begin();it2!=odd[12].end();++it2){
  67.          int r=lcm(*it1,*it2);
  68.          if(r>=maxorder){
  69.             maxorder=r;
  70.             printf("find order %d, odd8=%d, odd12=%d\n", maxorder, *it1, *it2);
  71.          }
  72.        }
  73.     }
  74.     printf("max order is %d\n",maxorder);
  75. }

  76. int main()
  77. {
  78.     find_max_8_12();
  79.     return 0;
  80. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-6 18:39 , Processed in 0.068640 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表