依照以下步驟執行(動作A→B表示把A升瓶倒到B升瓶)
步驟 | 動作 | 結果 |
---|
12升瓶 | 9升瓶 | 5升瓶 |
---|
- |
初始狀況 |
12 |
0 |
0 |
1. |
12→5 |
7 |
0 |
5 |
2. |
12→9 |
0 |
7 |
5 |
3. |
5→12 |
5 |
7 |
0 |
4. |
9→5 |
5 |
2 |
5 |
5. |
5→12 |
10 |
2 |
0 |
6. |
9→5 |
10 |
0 |
2 |
7. |
12→9 |
1 |
9 |
2 |
8. |
9→5 |
1 |
6 |
5 |
9. |
5→12 |
6 |
6 |
0 |
解析
我要編輯
用C程式跑
#include<iostream>
#include<cstdlib>
using namespace std;
int ctop[3]={12,7,5};
int c[3]={12,0,0};
bool mc1toc2(int c1n,int c2n);
int min(int a,int b);
void tryall();
int past[200][3];//c1n c2n c[c1n] c[c2n]
int pasttop=0;
void check()
{
//cout<<c[0]<<" | "<<c[1]<<" | "<<c[2]<<endl;
if( c[0]+c[1]+c[2]!=12){cout<<"12fause";cout<<endl<<"sys2";while(1)system("pause");}
if(c[0]==6||c[1]==6||c[2]==6){cout<<"GG"<<endl;
for(int i=0;i<=pasttop;i++)
{
cout<<past[i][0]<<" | "<<past[i][1]<<" | "<<past[i][2]<<" | "<<endl;
}while(1)system("pause");}
}
int main()
{
past[0][0]=12;
past[0][1]=0;
past[0][2]=0;
tryall();
cout<<endl<<"sys1";
system("pause");
}
void tryall()
{
int count=0;
if(mc1toc2(2,0)){tryall();count++;}
if(mc1toc2(2,1)){tryall();count++;}
if(mc1toc2(0,1)){tryall();count++;}
if(mc1toc2(0,2)){tryall();count++;}
if(mc1toc2(1,0)){tryall();count++;}
if(mc1toc2(1,2)){tryall();count++;}
}
bool mc1toc2(int c1n,int c2n)
{
int k;
if(c[c1n]+c[c2n]==12&&c2n==0)return false;
if(c[c1n]>0&&c[c2n]<ctop[c2n])
{
k=min(ctop[c2n]-c[c2n],c[c1n]);
c[c2n]+=k;
c[c1n]-=k;
pasttop++;
past[pasttop][0]=c[0];
past[pasttop][1]=c[1];
past[pasttop][2]=c[2];
for(int i=0;i<pasttop;i++)
if(c[0]==past[i][0] &&c[1]==past[i][1]&&c[2]==past[i][2])
{
c[c2n]-=k;
c[c1n]+=k;
pasttop--;
return false;
}
//cout<<c1n<<"to"<<c2n<<" ";
check();
return true;
}
return false;
}
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
--------------------------
結果:
12 | 0 | 0 |
5 | 7 | 0 |
0 | 7 | 5 |
7 | 0 | 5 |
7 | 5 | 0 |
2 | 5 | 5 |
2 | 7 | 3 |
9 | 0 | 3 |
9 | 3 | 0 |
4 | 3 | 5 |
4 | 7 | 1 |
11 | 0 | 1 |
11 | 1 | 0 |
6 | 1 | 5 |