天天看点

魔方——操作阶数实验

这是我徒弟请教我的一个问题,是一个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代码如下:

魔方——操作阶数实验
魔方——操作阶数实验

Code_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()

        {

            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;

    case '"':

        *angle = 180;

    }

    //获取五个受影响的面,第一个是主面,其他四个是从主面看过去的顺时针顺序影响面

    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;

    case 'R': //右

        sides[0]=P_RIGHT; //主旋转面

        sides[2]=P_BACK;

        sides[4]=P_FRONT;

    case 'T': //顶面

        sides[0]=P_TOP;

        sides[1]=P_BACK;

        sides[2]=P_RIGHT;

        sides[3]=P_FRONT;

        sides[4]=P_LEFT;

    case 'D': //底面

        sides[0]=P_BOTTOM;

        sides[1]=P_FRONT;

        sides[3]=P_BACK;

    case 'F': //前面

        sides[0]=P_FRONT;

    case 'B': //背面

        sides[0]=P_BACK;

        sides[2]=P_LEFT;

        sides[4]=P_RIGHT;

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

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];

    case -90: //逆时针旋转90, offset = 2

            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];

        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];

    case 180: //翻转180, offset = 4

            cells[sides[0]][i]=temp[(i+4)%8];

        //上下对换

        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];

        //左右对换

        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];

    }        

//

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个受影响面的旋转也统一起来,从而使上面代码进一步简化。有时间的时候我将补充改进后的代码。

继续阅读