|
|
玻璃杯问题
巴尼在汽水柜台工作,他用10只玻璃杯给两名顾客出了个难题.巴尼:"这一排有10只玻璃杯,左边5只内有汽水,右边5只空着,请你使这排杯子变成满杯与空杯相互交错,条件是只允许移动4只杯子."两位顾客看了看巴尼,又看了看杯子,摇了摇头,不知道怎么办.巴尼:"好吧,我来告诉你们,只要分别把第二只杯子和第七只杯子,第四只杯子和第九只杯子交换一下位置就成了."
这时,奎贝尔教授正好来到柜台前,看到了他们的把戏,并且来了点小花招.奎贝尔教授:"何需移动四只杯子,我只要移动两只就行了,你行不行?"
巴尼纳闷地瞧着奎贝尔教授,不明就里.奎贝尔教授:"很简单,只要拿起第二只杯子,把里面的汽水倒进第七只杯子,再拿起第四只杯子,把里面的汽水倒入第九只杯子就行了."
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
■■■■■□□□□□--->■□■□■□■□■□
虽然奎贝尔教授抓住话语间的模棱两可之处解决了这个问题,但这个问题并不像乍看上去那么简单.例如,还是这么个问题,但改成100只满杯挨着100只空杯排成一排,请考虑一下,若要使其变成满杯和空杯交错排列,需将多少对杯子互换位置?显然,一般地,如果有2n只杯子,n只满杯,n只空杯,需要将[n/2]对杯子互换位置,方法是2k号杯子与2k+n号杯子互换位置即可(k=1,2,3,...)若n=100,则需互换50次.
有一个与上面分析的问题类似但困难的多的古典难题.咱们这回用两种不同颜色的杯子作为道具,但是移动方法却大相径庭:每次只能一块儿移动一对相邻的杯子,使结果成交错排列,以n=3为例,解题过程如下图所示:
1 2 3 4 5 6
■■■□□□
■□□□■■
■□□ ■□■
□■□■□■
普遍的解是什么呢?当n=1时,没有意义,n=2时你会发现,无解,当n>2时,解此问题至少需要移动n次.n=4时,求解很不容易,你不妨试试,煞是有趣,或许你能够把当n>=3时的解题过程公式化.不像上两道题比较容易,这个问题我还没有仔细研究过,先把这道题上载,大家也可以发表意见.
根据这一难题还可以产生许多奇异的变相问题,用来测验你的智力.这里试着举几例:
(1).仍然是同时移动两只相邻的杯子,但是如果颜色不同,则要在移动过程中交换位置,这样一对黑白的杯子就变成一对白黑排列了.解8只杯子需要移动5次.对于10只杯子,5次移动也够了.我还尚不知道他的普遍解,也许你能找出来.
(2).某种颜色的杯子少一个,即某种颜色的杯子有n只,另一种杯子有n+1只,其余规则不变,已经证明(不好意思,不是我证的,我还没有仔细研究过),对于任意n只杯子,其解须作n次移动,而且这是最少的移动次数.
(3).使用三种不同颜色的杯子.按照通常的方法移动一对相邻的杯子,使得所有这三种颜色交相辉映.当n=3(共有9个杯子),其解需要作5次移动.在这些变相问题中,假设在最终形成的排列中,不允许留有任何空距.如果允许留有空距,则问题的解法就令人惊奇地变为移动4次了.
看来,尚有许多其他的变化形式,例如,假设一次可以同时移动3只或更多的杯子,在上述各变相问题中改用这种移动方式,结果会如何呢?假如是第一次移动1只杯子,第二次移动2只杯子,第三次移动3只杯子,依次下去,那又会怎样?给定某种颜色的杯子n个,另一种颜色的杯子也为n个,这个问题的解是否总是作n次移动?这种种问题都有待于人们去解决,我还没有时间来考虑这些问题,这是非常有趣非常值得人们思考的趣题.
下面是我写的代码来解决这个问题,并按一般的情况假设玻璃杯的位置不能像题中那样摆到原来位置之外,大家帮我想一下,看有没有更好的方法
#include<iostream.h>
const length=6;
struct node {
int a;
int b;
};
int data[length];
void find(node [],int );
void exchange(int ,int,int,int);
void ex(int ,int);
int count();
void main(void)
{
node p[2*length];
int len=0;
for(int i=0;i<length;i++)
if(i<3)
data=1;
else
data=0;
for(i=0;i<2*length;i++)
p.a=p.b=0;;
find(p,len);
}
void find(node p[],int len)
{
int c=count();
if(c==length-1)
{
for(int i=0;i<=len;i++)
cout<<"("<<p.a<<","<<p.b<<")"<<endl;
int a;
cin>>a;
}
else
{
for(int i=0;i<length-1;i++)
if(data*data[i+1]==0)
{
p[len].a=i;
p[len].b=i+1;
for(int j=0;j<length-1;j++)
{
if((data[j]*data[j+1]==0)&&i!=j)
{
exchange(i,i+1,j,j+1);
if(count()>c)
find(p,len+1);
exchange(i,i+1,j,j+1);
exchange(i+1,i,j,j+1);
if(count()>c)
find(p,len+1);
exchange(i,i+1,j,j+1);
}
}
}
}
}
void exchange(int i,int i1,int j,int j1)
{
ex(i,j);
ex(i1,j1);
}
void ex(int i,int j)
{
int temp=data;
data=data[j];
data[j]=temp;
}
int count()
{
int c=0;
for(int i=0;i<length-1;i++)
if(data*data[i+1]==0&&(data||data[i+1]))
c++;
return c;
}
|
|
发表于 2003-7-25 02:02:48