/*有十个开关等间距排成一线，每个开关对应其上方的一盏灯（十盏灯也排成一线）。每按动一下开关，可以使对应的灯改变状态（原来亮着的将熄灭，原来熄灭的将被点亮）。但是，由于开关之间的距离很小，每次按动开关时，相邻的一个开关也将被按动。例如：按动第5个开关，则实际上第4、5、6个开关都被按动。而按动靠边的第1个开关时，第1、2个开关都被按动。并且，无法只按动最靠边的一个开关。现在给出十盏灯的初始的状态和目标状态，要求计算：从初始状态改变到目标状态所需要的最少操作次数。函数接口：int MinChange(const int Start[],const int End[]);其中：Start表示了初始状态，End表示了目标状态。表示状态的数组（Start和End）中，若某元素为0表示对应的灯亮着，否则表示对应的灯没有亮。调用函数时保证Start和End数组长度均为10，并保证有解。*操作方法：设当前灯编号为i，其下一盏灯编号为i+1若i灯的初始状态与末状态相同，且i+1灯的初始状态与末状态相同：i = i + 1，不按开关；若i灯的初始状态与末状态相同，但i+1灯的初始状态与末状态不同：i = i + 2，按下开关；若i灯的初始状态与末状态不同，不论i+1灯的初始状态与末状态是否相同：i = i + 1，按下开关。若出现无解的情况，则操作次数取32768； 从左边和右边各顺序操作一次，取操作数较小的返回 *注：因为按照如上的操作方法，最边上的两个开关是不用亲自去按的；而这样会漏掉一些解。所以把初始状态扩展到4种情况：1。与给定的初始状态一模一样2。在原状态下，先按下最左边的开关 3。在原状态下，先按下最右边的开关4。在原状态下，先按下最左边和最右边的开关*//*2006-2-12 梁见斌*/ #include <iostream>#include <cmath> using namespace std; int MinChange(const int Start[],const int End[]);//把初始状态扩展到四种情况 void Change(int array[], int lable, int max);//按下开关，改变对应的灯及其相邻的灯的状态 int DMinChange(const int start[], const int end[]);//按照给定操作方法操作 int main(){ int a[10]={1,1,1,1,1};    int b[10]={1,0,0,0,0}; int n = 9;  n = MinChange(a, b); cout << "n=" << n << "\n";;  getchar(); return 0;} int MinChange(const int start[], const int end[]){ const int MAXLEN = 5;//存储灯的数量  int c_start[MAXLEN]; //存储灯的初始状态  int count;  //记录每一种初始状态下的最少操作数  int minCount;  //记录总的最少操作数  //从左边开始操作  for (int j=0; j<MAXLEN; j++) //复制数组   c_start[j] = start[j];  cout << "先不按任何开关，直接按照操作方法进行 \n"; minCount = DMinChange(c_start, end); //先不按任何开关，直接按照操作方法进行   cout << "先按下最左边的开关\n"; Change(c_start, 0, MAXLEN - 1);//先按下最左边的开关 count = DMinChange(c_start, end) + 1; //加上按最边上开关的操作  minCount = (minCount < count) ? minCount : count;  cout << "先按下最左边和最右边的开关\n"; Change(c_start, MAXLEN-1, MAXLEN - 1);//先按下最左边和最右边的开关 count = DMinChange(c_start, end) + 2; //加上按最边上开关的操作  minCount = (minCount < count) ? minCount : count;  cout << "先按下最右边的开关\n"; Change(c_start, 0, MAXLEN - 1);//先按下最右边的开关 count = DMinChange(c_start, end) + 1; //加上按最边上开关的操作  minCount = (minCount < count) ? minCount : count;  return minCount;}/*函数介绍:根据给定的初状态和末状态，按照操作方法顺序操作，返回所需的最少操作数  */int DMinChange(const int start[], const int end[]){ const int MAXLEN = 5;//存储灯的数量  int c_start[MAXLEN]; //存储灯的初始状态  int countLeft = 0;//累计从左边开始操作的所需的操作次数  int countRight = 0;//累计从右边开始操作的所需的操作次数  int i;  //从左边开始操作  for (int j=0; j<MAXLEN; j++) //复制数组   c_start[j] = start[j];  i = 0; while (i < MAXLEN - 1) {  if (c_start[i] == end[i])//若当前灯的初始状态与末状态相同   {   if (c_start[i+1] == end[i+1])//若相邻的下一盏灯的初始状态与末状态相同     i++;   else   {    if (i <= MAXLEN - 3)     {     i += 2;     Change(c_start, i, MAXLEN - 1);//按下开关，改变对应的灯及其相邻的灯的状态      cout << i;     //显示操作的步骤      countLeft ++;    }    else    {     countLeft = 32768;//出现错误的操作或无解      break;    }    }                     }  else  //若当前灯的初始状态与末状态不相同   {   i++;   Change(c_start, i, MAXLEN - 1);//按下开关，改变对应的灯及其相邻的灯的状态    cout << i;       //显示操作的步骤    countLeft ++;   }  } cout << "\n"; //从右边开始操作 for (int j=0; j<MAXLEN; j++) //复制数组   c_start[j] = start[j];   i = MAXLEN - 1;  while (i > 0) {  if (c_start[i] == end[i])  {   if (c_start[i-1] == end[i-1])    i--;   else   {    if (i >= 2)    {     i -= 2;     Change(c_start, i, MAXLEN - 1);//按下开关，改变对应的灯及其相邻的灯的状态      cout << i;   //显示操作的步骤      countRight++;    }    else    {     countRight = 32768;//出现错误的操作或无解      break;    }    }  }  else  {   i--;   Change(c_start, i, MAXLEN - 1);//按下开关，改变对应的灯及其相邻的灯的状态    cout << i;      //显示操作的步骤    countRight++;   }  } cout << "\n"; cout << "a=" << countLeft << "\n";   cout  << "b=" <<  countRight << "\n";  return (countLeft < countRight) ? countLeft : countRight;  } /*函数介绍:输入一个整型数组和某元素下标,以及数组长度，改变该元素极其相邻元素的状态（0或非0）  */void Change(int array[], int lable, int max){ if (lable > 0)  array[lable-1] = (array[lable-1] ? 0 : 1);   array[lable] = (array[lable] ? 0 : 1);  if (lable < max)  array[lable+1] = (array[lable+1] ? 0 : 1);}

评论