/* 现有3×3的九个方格，空出中心的方格，将数字1-8随机的放入到其它的8个方格中，数字1不动，其它的数字可以移动，   最终，使所有数字按1-8的顺序顺时针排列外围方格中。移动的规则是：   都可以移向横排或竖排相临空着的方格，而且，都可以移向中心空着的方格。   要求计算出移动移动最少的次数。        函数接口： int minMove(int a[]);    其中 a[] 表示从左上角顺时针放入的8个数。*//*2006-2-25*/ /*算法介绍： 1。设定位置标号：从左上角按顺时针依次设定位置标号为1-8，中间的空格位置标号为0。*2。创建一个类，其对象为数字1-8。为每个对象的属性包括位置标号pos和数字大小num。*3。定义一个对象数组，数组元素依次为数字1-8。为方便起见，这里使每个元素的大小等于其下标值。*4。从数字2开始依次按照移动规则操作每个数字，使其按顺序顺时针排列到外围方格中。    操作方法：若数字n（2 <= n <=8 )已经位于n-1之后，则对n不做任何操作，直接操作n+1；    若数字n不在n-1之后，则：    1。若n处于中间的方格中（指位置标号为2，4，6，8处，非中间空格处），则将其移至中间空格处，然后将其位置前面的数字依次按逆时针移动，直到空出一个合适的方格，即方格的前一位置处是数字n-1，将n移到该空方格处。    2。若n不处于中间的方格中（即位置标号为1，3，5，7处），则将其移到中间的方格中。    具体操作为：将n位置前面的数字移至中间空格处，然后将它及其位置后面的数字依次按逆时针移动，直到空出一个合适的方格，即方格的后一位置处的数字比n大或者是数字1，将中间空格处的数字移到该空方格处。此时n已经处于中间的方格中。    *5。累计每次移动，最后返回移动的次数，此即移动最少的次数。*6。本程序还可以打印每次移动后各数字的分布情况（中间空格处无数字），    用户可以将其打印出来以便帮助实际操作。 */ #include using namespace std;int count = 0;   //全局变量，用来累计移动的次数 const int Max = 8; //全局变量，表示数的个数 class Date{   //创建一个类，用来描述每一个数字的大小和位置标号    int pos;    int num;public:    int GetPos()  //读取位置标号     {        return pos;    }    int GetNum()//读取数字大小     {        return num;    }    void SetPos(int p) //设置位置标号     {        pos = p;    }    void SetNum(int n) //设置数字大小     {                      num = n;    }    int PrePos() //读取该数字的前一位置标号     {        if (pos == 1)            return 8;        else            return pos-1;    }        Date operator =(Date A)    {        pos = A.GetPos();        num = A.GetNum();                return *this;    }};void SetDate(const int a[], Date A[]);//根据传入的数据，设置对象数组 void PrintDate(const Date A[]);//打印对象数组，即各数字的分布情况（中间空格处无数字）void SortDate(Date A[]); //按照位置标号大小，用选择排序法对数组元素进行排序 int NextPos(int pos); //传入一个位置标号，返回该位置之后的位置标号 void MoveDate(Date A[], int blank, int n); //按要求移动数字 bool IsMid(int pos);//传入一个位置标号，判断该位置是否处于中间 void ToMid(Date A[], Date D); //将数字对象D移到外围方格中间的方格中int ToCen(Date &D); //将数字对象D移到中间的空格格中int Forward(Date &D);//传入一个数字对象，将其按逆时针顺序向前移动int MinMove(int a[]); //计算出移动移动最少的次数int main()             {    int a[Max] = {1, 2, 3, 4, 5, 6, 8, 7};    cout << "c=" << MinMove(a) << "\n";            getchar();    return 0;}int MinMove(int a[]){    Date A[Max+1];    int blank;    extern int count;        SetDate(a, A); //根据传入的数据，设置对象数组         PrintDate(A); //打印对象数组，即各数字的分布情况（中间空格处无数字）       for (int i=2; i<=Max; i++) //从数字2开始依次按照移动规则操作每个数字    {            if (A[i].PrePos() != A[i-1].GetPos()) //若数字i未按顺序排列         {                    if (! IsMid(A[i].GetPos())) //若数字i不处于中间的方格中                 ToMid(A, A[i]);  //则将其移到中间的方格中                        //    cout << "c=" << count << "\n";             //    PrintDate(A);                     //若数字i已经按顺序排列了，跳过后面的操作，操作数字i+1             if (A[i].PrePos() == A[i-1].GetPos())            {                //    cout << "c=" << count << "\n";            //    PrintDate(A);                   continue;            }                        // 否则，把数字i移到中间空格处，并将其位置前面的数字依次按逆时针移动             //直到空出一个合适的方格，即方格的前一位置处是数字i-1，将i移到该空方格处。            blank = ToCen(A[i]);            MoveDate(A, blank, i);                     //    cout << "c=" << count << "\n";          //    PrintDate(A);         }    }       // PrintDate(A);       return count;}/*函数介绍: 传入一个位置标号，返回该位置之后的位置标号 */int NextPos(int pos){    if (pos == 8)        return 1;    else        return pos + 1;}/*函数介绍: 若n处于中间的方格中（指位置标号为2，4，6，8处，非中间空格处），则将其移至中间空格处，然后将其位置前面的数字依次按逆时针移动，直到空出一个合适的方格，即方格的前一位置处是数字n-1，将n移到该空方格处。 *形参： Date A[]：对象数组     int blank：空格处的位置标号    int n：正在处理的数字对象的下标，即其数字的大小 */void MoveDate(Date A[], int blank, int n){    extern int count;        while (1)    {        for (int i=1; i<=Max; i++) //将n的位置前面的数字依次按逆时针移动        {            if (A[i].PrePos() == blank)            {                blank = Forward(A[i]);                    count++;                break;            }        }                //如果空格在中间，并且空格之前的数字为n-1，则停止移动其他数字         if ((IsMid(blank)) && (blank == NextPos(A[n-1].GetPos())))            break;    }        A[n].SetPos(blank);  //将n移到空方格处    count++;        }/*函数介绍: 传入一个位置标号，判断该位置是否处于中间 */bool IsMid(int pos){    if (pos == 2 ||   pos == 4 || pos == 6 || pos == 8)        return true;    else        return false;}/*函数介绍: 若n不处于中间的方格中（即位置标号为1，3，5，7处），则将其移到中间的方格中。    具体操作为：将n位置前面的数字移至中间空格处，然后将它及其位置后面的数字依次按逆时针移动，直到空出一个合适的方格，即方格的后一位置处的数字比n大或者是数字1，将中间空格处的数字移到该空方格处。此时n已经处于中间的方格中。*形参： Date A[]：对象数组     Date D：正在处理的数字对象 */void ToMid(Date A[], Date D){    extern int count;    int flag = 0;         int blank;        for (int i=1; i<=Max; i++)  //将n位置前面的数字移至中间空格处    {        if (A[i].GetPos() == D.PrePos())        {                 blank = ToCen(A[i]);            break;        }    }               while (1)    {            for (int i=1; i<=Max; i++) //将它及其位置后面的数字依次按逆时针移动        {            if (A[i].PrePos() == blank)            {                     blank = Forward(A[i]);                count++;                      break;            }        }                if (IsMid(blank))//直到发现一个合适的空格         {               for (int i=1; i<=Max; i++)            {                if ((A[i].GetPos() == NextPos(blank)) &&                 ((A[i].GetNum() > D.GetNum()) || (A[i].GetNum() == 1)))                {                      flag = 1;                    break;                }            }        }                if (flag == 1)            break;    }        for (int i=1; i<=Max; i++) // 将中间空格处的数字n移到该空方格处    {        if (A[i].GetPos() == 0)        {               A[i].SetPos(blank);            count++;               break;        }    }    }/*函数介绍: 传入一个数字对象，将其移到中间空格（位置标号为0）处 */int ToCen(Date &D){    extern int count;    int blank = D.GetPos();        D.SetPos(0);    count++;            return blank;}/*函数介绍: 传入一个数字对象，将其按逆时针顺序向前移动*/int Forward(Date &D){    int blank = D.GetPos();        D.SetPos(D.PrePos());        return blank;}/*函数介绍: 根据传入的数据，设置对象数组 */void SetDate(const int a[], Date A[]){    for (int i=0; i

评论