魔方——操作阶数实验-阿里云开发者社区

开发者社区> 开发与运维> 正文

魔方——操作阶数实验

简介: 这是我徒弟请教我的一个问题,是一个C++的作业题,题目是:  从一个已复原的魔方开始,重复某一个操作序列,必然会在有限次重复操作之后又复原,设计程序,输入任意一个操作序列,输入它的复原重复次数。  操作有18个:  L,L',L":分别为左面顺时针转90度、逆时针转90度和180度翻转;  R,R'...
这是我徒弟请教我的一个问题,是一个C++的作业题,题目是:
  从一个已复原的魔方开始,重复某一个操作序列,必然会在有限次重复操作之后又复原,设计程序,输入任意一个操作序列,输入它的复原重复次数。
  操作有18个:
  L,L',L":分别为左面顺时针转90度、逆时针转90度和180度翻转;
  R,R',R":分别为右面顺时针转90度、逆时针转90度和180度翻转;
  T,T',T":分别为顶面顺时针转90度、逆时针转90度和180度翻转;
  D,D',D":分别为底面顺时针转90度、逆时针转90度和180度翻转;
  F,F',F":分别为前面顺时针转90度、逆时针转90度和180度翻转;
  B,B',B":分别为背面顺时针转90度、逆时针转90度和180度翻转。
  在实验报告中记录如下事项:
  输入L,则输出4。
  输入L",则输出2。
  输入D" R,则输出30。
  输入D R,则输出105。以及其它自定的操作序列。
  ======================================================================
  
  看到这个题目,感觉尽管自觉不难,但是编码上一定要有很大的技巧性。我设想魔方一共有六个面,保持它的中心不动不旋转,那么每个面的中间一格也是永远不动的,而周围8个格子随着操作而变换。因此我用这样一个数组 cells[6][8], 来记录六个面。每个面有8个格子,我按照从正上方看过去顺时针方向对这8个格子编排索引。如下图(图中格子上的数字代表它在自己所在面的数组中的索引):

    

  解题的过程实际上就是魔方的旋转建模,因此我们继续完成这个模型。我们考虑上面描述的所有操作本质上都属于以一个主平面旋转,同时影响与它相邻的四个面的边缘三个格子。因此我们引入一个辅助函数:(getinfo) 用来对每一种旋转获取一个角度值和主旋转面,四个受影响面,并把面的索引存放到参数指定的数组中。
  然后我们针对旋转写一个函数:rotate;它根据三种角度,完成(1)对主旋转面的内部旋转;(2)对四个受影响面的格子轮换;
  最后我完成的C代码如下:

  
img_1c53668bcee393edac0d7b3b3daff1ae.gifimg_405b18b4b6584ae338e0f6ecaf736533.gifCode_magicCube
#include "stdafx.h"

/*
魔方——操作阶数实验
从一个已复原的魔方开始,重复某一个操作序列,必然会在有限次重复操作之后又复原,设计程序,输入任意一个操作序列,
输入它的复原重复次数。
操作有18个:
L,L',L":分别为左面顺时针转90度、逆时针转90度和180度翻转;
R,R',R":分别为右面顺时针转90度、逆时针转90度和180度翻转;
T,T',T":分别为顶面顺时针转90度、逆时针转90度和180度翻转;
D,D',D":分别为底面顺时针转90度、逆时针转90度和180度翻转;
F,F',F":分别为前面顺时针转90度、逆时针转90度和180度翻转;
B,B',B":分别为背面顺时针转90度、逆时针转90度和180度翻转。
在实验报告中记录如下事项:
输入L,则输出4。
输入L",则输出2。
输入D" R,则输出30。
输入D R,则输出105。
以及其它自定的操作序列。
*/
#include 
<stdio.h>
#include 
<string.h>

//面索引
#define P_LEFT      0
#define P_FRONT  1
#define P_RIGHT  2
#define P_BACK     3
#define P_TOP         4
#define P_BOTTOM 5

//六个面, 
//cells[0]: Left
//cells[1]: Front
//cells[2]: Right
//cells[3]: Back
//cells[4]: Top
//cells[5]: Bottom
//面内索引:
// 0 1 2
// 7 * 3
// 6 5 4
//================
char cells[6][8];

//初始化魔方
void init()
{
    
int i,j;
    
for(i=0;i<6;i++)
        
for(j=0;j<8;j++)
            cells[i][j]
=i;
}

//复原了吗?
bool isdone()
{
    
int i,j;
    
for(i=0;i<6;i++)
        
for(j=0;j<8;j++)
        {
            
if(cells[i][j] != i)
                
return false;
        }
    
return true;
}

//获取旋转的信息
void getinfo(char* mode, int* angle, int* sides)
{
    
//获取角度
    switch(mode[1])
    {
    
case 0
        
*angle = 90;
        
break;
    
case '\''
        *angle = -90;
        
break;
    
case '"':
        
*angle = 180;
        
break;
    }
    
    
//获取五个受影响的面,第一个是主面,其他四个是从主面看过去的顺时针顺序影响面
    switch(mode[0])
    {
    
case 'L'//
        sides[0]=P_LEFT;
        sides[
1]=P_TOP;
        sides[
2]=P_FRONT;
        sides[
3]=P_BOTTOM;
        sides[
4]=P_BACK;
        
break;
    
case 'R'//
        sides[0]=P_RIGHT; //主旋转面
        sides[1]=P_TOP;
        sides[
2]=P_BACK;
        sides[
3]=P_BOTTOM;
        sides[
4]=P_FRONT;
        
break;
    
case 'T'//顶面
        sides[0]=P_TOP;
        sides[
1]=P_BACK;
        sides[
2]=P_RIGHT;
        sides[
3]=P_FRONT;
        sides[
4]=P_LEFT;
        
break;
    
case 'D'//底面
        sides[0]=P_BOTTOM;
        sides[
1]=P_FRONT;
        sides[
2]=P_RIGHT;
        sides[
3]=P_BACK;
        sides[
4]=P_LEFT;
        
break;
    
case 'F'//前面
        sides[0]=P_FRONT;
        sides[
1]=P_TOP;
        sides[
2]=P_RIGHT;
        sides[
3]=P_BOTTOM;
        sides[
4]=P_LEFT;
        
break;
    
case 'B'//背面
        sides[0]=P_BACK;
        sides[
1]=P_TOP;
        sides[
2]=P_LEFT;
        sides[
3]=P_BOTTOM;
        sides[
4]=P_RIGHT;
        
break;
    }
}

//传入一个操作字符串,进行相应操作

void rotate(char* mode)
{
    
char temp[8],temp2[3];
    
int i, angle, sides[5];
    
//获取角度和5个面
    getinfo(mode, &angle, sides);

    
//复制主面到一个临时备份
    for(i=0;i<8;i++)
        temp[i]
=cells[ sides[0] ][i];

    
switch(angle)
    {
    
case 90//顺时针旋转90, offset = 6
        
//[1]主面内部旋转
        for(i=0;i<8;i++)
            cells[sides[
0]][i]=temp[(i+6)%8];

        
//备份影响面的数字
        temp2[0]=cells[sides[4]][4];
        temp2[
1]=cells[sides[4]][3];
        temp2[
2]=cells[sides[4]][2];

        
//4个受影响面
        cells[sides[4]][4]=cells[sides[3]][2];
        cells[sides[
4]][3]=cells[sides[3]][1];
        cells[sides[
4]][2]=cells[sides[3]][0];

        cells[sides[
3]][2]=cells[sides[2]][0];
        cells[sides[
3]][1]=cells[sides[2]][7];
        cells[sides[
3]][0]=cells[sides[2]][6];

        cells[sides[
2]][0]=cells[sides[1]][6];
        cells[sides[
2]][7]=cells[sides[1]][5];
        cells[sides[
2]][6]=cells[sides[1]][4];

        cells[sides[
1]][6]=temp2[0];
        cells[sides[
1]][5]=temp2[1];
        cells[sides[
1]][4]=temp2[2];

        
break;

    
case -90//逆时针旋转90, offset = 2
        
//[1]主面内部旋转
        for(i=0;i<8;i++)
            cells[sides[
0]][i]=temp[(i+2)%8];

        
//备份影响面的数字
        temp2[0]=cells[sides[1]][6];
        temp2[
1]=cells[sides[1]][5];
        temp2[
2]=cells[sides[1]][4];

        
//4个受影响面
        cells[sides[1]][6]=cells[sides[2]][0];
        cells[sides[
1]][5]=cells[sides[2]][7];
        cells[sides[
1]][4]=cells[sides[2]][6];

        cells[sides[
2]][0]=cells[sides[3]][2];
        cells[sides[
2]][7]=cells[sides[3]][1];
        cells[sides[
2]][6]=cells[sides[3]][0];

        cells[sides[
3]][2]=cells[sides[4]][4];
        cells[sides[
3]][1]=cells[sides[4]][3];
        cells[sides[
3]][0]=cells[sides[4]][2];

        cells[sides[
4]][4]=temp2[0];
        cells[sides[
4]][3]=temp2[1];
        cells[sides[
4]][2]=temp2[2];

        
break;

    
case 180//翻转180, offset = 4
        
//[1]主面内部旋转
        for(i=0;i<8;i++)
            cells[sides[
0]][i]=temp[(i+4)%8];

        
//备份影响面的数字
        
//上下对换
        temp2[0]=cells[sides[1]][6];
        temp2[
1]=cells[sides[1]][5];
        temp2[
2]=cells[sides[1]][4];

        cells[sides[
1]][6]=cells[sides[3]][2];
        cells[sides[
1]][5]=cells[sides[3]][1];
        cells[sides[
1]][4]=cells[sides[3]][0];

        cells[sides[
3]][2]=temp2[0];
        cells[sides[
3]][1]=temp2[1];
        cells[sides[
3]][0]=temp2[2];

        
//左右对换
        temp2[0]=cells[sides[4]][4];
        temp2[
1]=cells[sides[4]][3];
        temp2[
2]=cells[sides[4]][2];

        cells[sides[
4]][4]=cells[sides[2]][0];
        cells[sides[
4]][3]=cells[sides[2]][7];
        cells[sides[
4]][2]=cells[sides[2]][6];

        cells[sides[
2]][0]=temp2[0];
        cells[sides[
2]][7]=temp2[1];
        cells[sides[
2]][6]=temp2[2];

        
break;
    }        
}

//
int _tmain(int argc, _TCHAR* argv[])
{
    
char* token=NULL;
    
char step[128][4];
    
char line[512];
    
int i, length = 0//每一次有几步操作
    int result = 0;

    
//初始化
    init();

    gets(line);
    
    
//用空格分割
    token=strtok(line, " ");

    
//复制动作
    while(token!=NULL)
    {
        strcpy(step[length
++], token);
        token 
= strtok(NULL, " ");
    }

    
while(true)
    {
        
//执行一次动作序列
        for(i=0;i<length;i++)
            rotate(step[i]);

        result
++;

        
//复原了吗?
        if(isdone())
            
break;
    }

    printf(
"%d\n", result);
    getchar();
    
return 0;
}

  总结一下,上面的代码中,主旋转面的旋转已经被统一起来。对4个受影响面的格子的交换代码还是略显 “hard” 和“笨拙”,自觉感觉还是有改进的余地。因为四个受影响面中,每个面提供三个格子,连接组成了一个环形(共12个格子),因此我们可以用一个char[12]线性数组去完成相应的旋转,而且我们看到,针对特定主旋转面,其他12个元素在各自面内的索引相同,这就为我们改进这部分硬代码提供了理论保证。因此我们的getinfo的任务不变,还是需要提供4个受影响面,然后就可以把cells从二维数组看作一格一维线性表,根据面索引和格子索引在cells中定位到这个元素,然后把这12个元素作一个相应角度的轮转即可。这将把对4个受影响面的旋转也统一起来,从而使上面代码进一步简化。有时间的时候我将补充改进后的代码。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章