/*有十个开关等间距排成一线，每个开关对应其上方的一盏灯（十盏灯也排成一线）。
每按动一下开关，可以使对应的灯改变状态（原来亮着的将熄灭，原来熄灭的将被点亮）。
但是，由于开关之间的距离很小，每次按动开关时，相邻的一个开关也将被按动。
例如：按动第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);
}
评论