魔方循环问题
问题表述如下：对于魔方来说，给定一个指定步骤，请问重复旋转多少次会回到初始状态？
由于魔方状态有限，所以一定是会回到初始状态的。
具体举例：
如果进行R变换，需要4次，就是说将右侧面旋转4次就会回到初态；
如果进行R2变换，需要2次就可以了；
如果进行RU变换，则需要105次才会第一次回到初态！
附注：
对于不了解魔方公式定义的朋友我进行一下变换代号说明：
R：右手面顺时针旋转(right)
U：上面顺时针旋转(up)
F：前面顺时针旋转(front)
B：后面顺时针旋转(back)
L：左手面顺时针旋转(left)
D：下面顺时针旋转(down)
顺时针的定义为正面朝向该面进行判断，
后面加个2表示旋转两次，加' （一撇)表示逆时针旋转。 本帖最后由 winxos 于 2009-10-4 09:40 编辑
我做了一些简单的分析，比如对于长度为6的只有顺时针旋转的公式，循环次数最长为720，
回复后可以查看。
**** Hidden Message ***** 群论问题.
对于任何一个步骤,魔方所有状态树目为这个次数的倍数 很实际的问题 为什么一定要回复才能查看呢。: ( Lwins_G 发表于 2013-12-31 03:51
为什么一定要回复才能查看呢。: (
回复查看之后，发现链接都已经失效，人世间悲催之事莫过如此， :lol
如果你感兴趣，我可以帮你 把楼主 拉回来。 同一个操作循环1260次,一定会回到原来的状态 我以前编程算过这个，就是你给一套公式，我程序算做多少次能回去。
不过没试过随机生成公式的，我觉得楼上1260次这个结论很神奇，我要再做做。 魔方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号保持位置不变。这样分解的好处是可以非常容易计算出这个置换的阶，它就是所有轮换数目的最小公倍数，比如这个例子就是=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 #include <stdio.h>
#include <set>
using namespace std;
int gcd(int a, int b)
{
if(a==0)return b;
return gcd(b%a, a);
}
int lcm(int a, int b)
{
return (a/gcd(a,b))*b;
}
#define MAX_ORDER 12
set<int> even;
set<int> odd;
void calset()
{
int i,j;
set<int>::iterator it;
even.insert(1);//order 1 reached for even perm (1)
even.insert(1);//order 1 reached for even perm (1)(2)
odd.insert(2);//order 2 reach for odd (12)
for(i=3;i<=MAX_ORDER;i++){
if(i&1){
even.insert(i);
}else{
odd.insert(i);
}
for(j=i-1;j>=2;j--){
//use number j
if(j&1){
//use even perm with j numbers
for(it=even.begin();it!=even.end();++it){
even.insert(lcm(*it,j));
}
for(it=odd.begin();it!=odd.end();++it){
odd.insert(lcm(*it,j));
}
}else{
//use odd perm with j numbers
for(it=even.begin();it!=even.end();++it){
odd.insert(lcm(*it,j));
}
for(it=odd.begin();it!=odd.end();++it){
even.insert(lcm(*it,j));
}
}
}
}
}
void find_max_8_12()
{
set<int>::iterator it1,it2;
int maxorder=0;
calset();
for(it1=even.begin();it1!=even.end();++it1){
for(it2=even.begin();it2!=even.end();++it2){
int r=lcm(*it1,*it2);
if(r>=maxorder){
maxorder=r;
printf("find order %d, even8=%d, even12=%d\n",maxorder, *it1, *it2);
}
}
}
for(it1=odd.begin();it1!=odd.end();++it1){
for(it2=odd.begin();it2!=odd.end();++it2){
int r=lcm(*it1,*it2);
if(r>=maxorder){
maxorder=r;
printf("find order %d, odd8=%d, odd12=%d\n", maxorder, *it1, *it2);
}
}
}
printf("max order is %d\n",maxorder);
}
int main()
{
find_max_8_12();
return 0;
}
页:
[1]
2