求解一算法难题！

一个正方形的四个角a，b，c，d分别放若干个棋子，每次可从任意一角中去掉x枚棋子，同时在其相邻两个角的每个角上添加x枚棋子。初始状态时，a角上有1枚棋子，其他3个角没有。编程寻求一种方案，用最少的步数实现4个角从初始状态达到目标状态。目标状态时a，b，c，d角的棋子数由用户输入。

18 个解决方案

#1

新年快乐

#2

难道没人会吗？版主也不会吗？帮帮忙吧！！！谢谢了！

#3

这道题目到底难不难，就要看你对速度的要求了，
你可以试试搜索，比如下面这个程序就是这样：

#include <iostream.h>
#include <conio.h>

const int maxstep = 1000;

int best, way[maxstep][4], minway[maxstep][4];

int min(int a, int b)
{
  return ((a < b) ? a : b);
}

void calc(int step,
          int a, int b, int c, int d,
          int xa, int xb, int xc, int xd)
{

  if (step >= best)
  {
    return;
  }

  way[step][0] = a;
  way[step][1] = b;
  way[step][2] = c;
  way[step][3] = d;

  if ((xa == 0) && (xb == 0) && (xc == 0) && (xd == 0))
  {
    best = step;
    memcpy(minway, way, sizeof(minway));
    return;
  }

  int k;

  k = min(xa, a);
  if (k != 0)
  {
    calc(step + 1, a - k, b + k, c, d + k, xa - k, xb, xc, xd);
  }

  k = min(xb, b);
  if (k != 0)
  {
    calc(step + 1, a + k, b - k, c + k, d, xa, xb - k, xc, xd);
  }

  k = min(xc, c);
  if (k != 0)
  {
    calc(step + 1, a, b + k, c - k, d + k, xa, xb, xc - k, xd);
  }

  k = min(xd, d);
  if (k != 0)
  {
    calc(step + 1, a + k, b, c + k, d - k, xa, xb, xc, xd - k);
  }

}

void main()
{

  /*
    a   b

    d   c
  */

  int a, b, c, d;
  cin >> a >> b >> c >> d;

  int x = a + b + b + c - d - 1;
  if ((x % 3) != 0)
  {
    cout << "No answer" << endl;
    return;
  }
  int xd = x / 3;
  int xc = a + b - 1 - xd;
  int xb = a + b + c - 1 - xd - xd;
  int xa = b + c - xd;
  if ((xa < 0) || (xb < 0) || (xc < 0) || (xd < 0))
  {
    cout << "No answer" << endl;
    return;
  }

  best = maxstep;
  calc(0, 1, 0, 0, 0, xa, xb, xc, xd);

  if (best == maxstep)
  {
    cout << "Too many steps" << endl;
    return;
  }

  cout << "minstep = " << best << endl;
  cout << endl;

  for (x = 0; x <= best; x ++)
  {

    cout << "#" << x << endl;

    cout << minway[x][0] << "  " << minway[x][1] << endl;
    cout << endl;
    cout << minway[x][3] << "  " << minway[x][2] << endl;

    cout << endl;
    cout << "Press any key to continue ..." << endl;
    cout << endl;
    getch();

  }

}

#4

不需要吧，用笔算也才一会儿
比如如果本个角上分别有显示
a b
c d
则显示a的应该是(b+c+2*d-a)/3
以此类推

#5

有点bug呵呵
b:=b-1; first

#6

to ljskater(阿甘)

你的回复，我看了好几遍了，还是没弄明白。
能否再说清楚一点?

#7

这不过是一个数学题而已，
我们只需要计算在a,b,c,d四个角上各加多少个棋子就行了。
假设最终目的是a上A个子，b上B个子，c上C个子，d上D个子,
在a上去了u次，b上取了v次，c上去了w次，d上去了x次，
则
-u+v  +x=A-1
+u-v+w  =B
  +v-w+x=C
+u+v  -x=D
解这个方程，如果得到的u,v,w,x中至少有一个小于0则无解。
然后可以用贪心法，如果当前a,b,c,d中某个格子上数目做多，而且其对应去棋子的次数还没有用完，那么就可以现在这个格子上去掉若干枚。如果发现没有格子上的棋可去了（也就是还没有到达目的状态，而且每个格子要么没有棋子，要么已经去过足够的棋子），那么就是无解了。

#8

>>如果得到的u,v,w,x中至少有一个小于0则无解。

应该是 如果 有一个小于0 或 有一个不是整数，则无解。
即 原问题有解，当且仅当方程有非负整数解，

>>然后可以用贪心法

贪心法不一定能保证对吧 :)
所以我的程序又搜索了一下。

#9

int search(a,b,c,d)
{
if(a+b+c+d=1) return 1;//找到一种方法
l=a,b,c,d中数目最少的一角
m=l的相邻角中数目最少的角的值
if(m=0) return 0;//行不通，回溯
for(i=1;i<=m;i++)
{
 l角的值+i;
 l相邻角的值-i;//重新计算a,b,c,d的值
 push(a,b,c,d);//a,b,c,d压栈
 if(search(a,b,c,d)) return 1;//如果找到返回
 pop(a,b,c,d);//弹出a,b,c,d的值
}
return 0;//行不通，回溯
}

该算法不知对不对
算法思想是由已知的最终a,b,c,d值按照原规则的逆规则进行逆推
如果逆推不出某角为1，则回溯
之所以选a,b,c,d中数目最少的角+i是为了尽量保持各角的数目同时
向0，1靠拢
之所以i由1向上递增是为了减少回溯的次数
如果最终不是a为1，则在生成规则时将a,b,c,d旋转一下
举例如下：
     c=3    
b=2       d=4
     a=1

1.
a=a+1,b=b-1,c=c,d=d-1
     c=3
b=1       d=3
     a=2
2.
b=b+1,c=c-1,d=d,a=a-1
     c=2
b=2       d=3
     a=1
3.
a=a+1,b=b-1,c=c,d=d-1
     c=2
b=1       d=2
     a=2
4.
b=b+1,c=c-1,d=d,a=a-1
     c=1
b=2       d=2
     a=1
5.
a=a+1,b=b-1,c=c,d=d-1
     c=1
b=1       d=1
     a=2
6.
b=b+1,c=c-1,d=d,a=a-1
     c=0
b=2       d=1
     a=1
7.
c=c+1,d=d-1,a=a,b=b-1
     c=1
b=1       d=0
     a=1
8.
d=d+1,a=a-1,b=b,c=c-1
     c=0
b=1       d=1
     a=0
9.
a=a+1,b=b-1,c=c,d=d-1 
     c=0
b=0       d=0
     a=1

#10

to gagasame(进行式)

我写了个程序在上面，

在TC3.0下可以直接运行。

输入 1 2 3 4 ，你会发现，只要6步就可以了。


minstep = 6

#0
1  0

0  0

Press any key to continue ...

#1
0  1

1  0

Press any key to continue ...

#2
1  1

0  1

Press any key to continue ...

#3
0  2

1  1

Press any key to continue ...

#4
0  3

2  0

Press any key to continue ...

#5
3  0

2  3

Press any key to continue ...

#6
1  2

4  3

Press any key to continue ...

#11

To intfree,
>>应该是 如果 有一个小于0 或 有一个不是整数，则无解。
>>即 原问题有解，当且仅当方程有非负整数解，
第一句话是显然的，我只是偷了点懒，没有写的这么详细。
至于这个当且仅当，我可不敢保证了，凭感觉是不对的。
当然用贪婪法我也没有去证明，但是我的感觉是可用的（只要我们事先计算出每个点上需要移走的步数，在用贪婪法时保证这个总数不超过就行了）。

#12

to intfree
学习,学习

#13

我的想法和楼上mathe差不多的，我昨天用delphi做一个验证程序时修把概念换了一下，所以发帖的时候忘了换回来。

#14

how about this one?
#include <iostream>
#include <vector>
#ifdef min
#undef min
#endif
#include <algorithm>
using namespace std;
struct fourpair{
int a,b,c,d;
};

vector<fourpair> result;

int main(){
int a,b,c,d;
fourpair temp;
cin >> a >> b >> c >> d;

int x = a+2*b+c-d-1;
if(x%3!=0){
cout << "No answer" <<endl;
return -1;
}
int xd=x/3;
int xc=a+b-1-xd;
int xb=a+b+c-1-2*xd;
int xa=b+c-xd;
if(xa<0||xb<0||xc<0||xd<0){
cout<<"No answer"<<endl;
return -1;
}
temp.a=a;temp.b=b;temp.c=c;temp.d=d;
result.push_back(temp);
while(temp.a!=1||temp.b!=0||temp.c!=0||temp.d!=0){
#ifdef _WIN32
int ma=_cpp_min(temp.a,temp.c);
int mb=_cpp_min(temp.b,temp.d);
#else
int ma=min(temp.a,temp.c);
int mb=min(temp.b,temp.d);
#endif
if(mb>=ma){
if(temp.a>temp.c){
if(temp.a-temp.c>=mb-1){
temp.c+=mb;
temp.b-=mb;
temp.d-=mb;
result.push_back(temp);
}else{
int cadd=temp.a-temp.c;
cadd+=(mb-cadd)/2;
temp.c+=cadd;
temp.b-=cadd;
temp.d-=cadd;
result.push_back(temp);
cadd=mb-cadd;
temp.a+=cadd;
temp.b-=cadd;
temp.d-=cadd;
result.push_back(temp);
}
}else{
if(temp.c-temp.a>=mb-1){
temp.a+=mb;
temp.b-=mb;
temp.d-=mb;
result.push_back(temp);
}else{
int cadd=temp.c-temp.a;
cadd+=(mb+1-cadd)/2;
temp.a+=cadd;
temp.b-=cadd;
temp.d-=cadd;
result.push_back(temp);
cadd=mb-cadd;
temp.c+=cadd;
temp.b-=cadd;
temp.d-=cadd;
result.push_back(temp);
}
}
}else{
if(temp.b>temp.d){
if(temp.b-temp.d>=ma-1){
temp.d+=ma;
temp.a-=ma;
temp.c-=ma;
result.push_back(temp);
}else{
int cadd=temp.b-temp.d;
cadd+=(ma-cadd)/2;
temp.d+=cadd;
temp.a-=cadd;
temp.c-=cadd;
result.push_back(temp);
cadd=ma-cadd;
temp.b+=cadd;
temp.a-=cadd;
temp.c-=cadd;
result.push_back(temp);
}
}else{
if(temp.d-temp.b>=ma-1){
temp.b+=ma;
temp.a-=ma;
temp.c-=ma;
result.push_back(temp);
}else{
int cadd=temp.d-temp.b;
cadd+=(ma-cadd)/2;
temp.b+=cadd;
temp.a-=cadd;
temp.c-=cadd;
result.push_back(temp);
cadd=ma-cadd;
temp.d+=cadd;
temp.a-=cadd;
temp.c-=cadd;
result.push_back(temp);
}
}
}
}
vector<fourpair>::reverse_iterator it;
for(it=result.rbegin();it!=result.rend();it++){
temp=*it;
cout<<"a="<<temp.a<<",b="<<temp.b<<",\n";
cout<<"d="<<temp.d<<",c="<<temp.c<<"\n\n";
}
cout<<"Total Step:"<<result.size()-1<<endl<<endl;
}

#15

to mathe()　

缩进都没有了，程序很难看懂的，

感觉上你的算法好神奇啊，

先up一下，有时间再仔细研究研究；

#16

一.关于原问题有解(即,按游戏规则可达到目标状态)的充要条件：
设在四个角
a b
d c
上要从初始棋子数
1 0
0 0
达到目标棋子数
A B
D C
而需从四个角上去掉的总棋子数之和为
u v
x w
则有方程：
-u+v  +x=A-1
 u-v+w  =B
   v-w+x=C
 u  +w-x=D
上述方程有唯一解,为:
u=[-(A-1)+B+2C+D]/3
v=[(A-1)-B+C+2D]/3
w=[2(A-1)+B-C+D]/3
x=[(A-1)+2B+C-D]/3
1.若目标状态的棋子数就等于初始状态(即:A=1,B=C=D=0),
则原问题有零解 u=v=w=x=0
1.若目标状态的棋子数不等于初始状态,
则原问题有解的充要条件是:根据上述公式求出的u,v,w,x皆为整数,且u>=1,v>=0,w>=0,x>=0
(换句话说:原问题有解的充要条件是:u为正整数,而v,w,x皆为非负整数).
此条件很明显是必要条件.此条件也是充分条件的原因是(尽管我没严格证明)我找不出反例.
二.关于原问题的最优方案的见解:
找最优方案(最少的步数)需用逆推法(即:倒着走棋,从目标状态达到初始状态)!
(具体方法一时难以细述,待我不久编好程序并于下次贴上后各位即知.)

#17

#include <iostream.h> // Run in VC++ 6.0
#include <iomanip.h>
void main()
{ const int P=4,L=200;
int h,i,j,k,m,t,u,v,z,a[P],B[L][P];
char F[5][37]={"Too Many Steps!\n","No Solution!\n",
"Total Steps: ","Enter A,B,C and D (Minus for Quit): ",
"Successful!\n\n"};
do{ for(cout<<F[3],j=0;j<P;j++){ cin>>a[j]; if(a[j]<0) return;}
h=(a[0]<a[2]?a[0]:a[2])<(a[1]<a[3]?a[1]:a[3]);
for(k=-1;k<L-1;h=1-h)
{ for(k++,j=0;j<P;j++) B[k][j]=a[j];
if((z=a[h]<a[h+2]?a[h]:a[h+2])==0) break;
i=a[1-h]<=a[3-h]?1-h:3-h; m=(i+2)%P;
u=z<(t=a[m]-a[i]+1)?z:(z+t)/2;
a[h]-=u; a[h+2]-=u; a[i]+=u;
if((v=z-u)>0) for(k++,j=0;j<P;j++) B[k][j]=a[j];
a[h]-=v; a[h+2]-=v; a[m]+=v;
} if(a[0]!=1||a[1]+a[2]+a[3]>0){ cout<<F[k<L-1]; return;}
for(cout<<F[2]<<k<<endl;k>=0;k-=5,cout<<(k<0?F[4]:"\n"))
for(h=0;h<2;h++) for(i=0;i<5&&i<=k;i++)
{ for(j=0;j<2;j++) cout<<setw(4)<<B[k-i][h?3-j:j]<<" ";
cout<<(i==k?"":(h?"   /":" __\\"))<<(i<4&&i<k?"\t":"\n");
}
}while(1);
} /*
Enter A,B,C and D (Minus for Quit): 1000 2000 3000 4000
Total Steps: 27
   1    0  __\     0    1  __\     1    1  __\     1    2  __\     0    3  __   0    0    /     1    0    /     0    1    /     1    0    /     2    0    /

   2    3  __\     5    0  __\     5    5  __\     0   10  __\    10   10  __   0    2    /     0    5    /     5    0    /    10    0    /     0   10    /

  20    0  __\    20   19  __\     0   39  __\    39   39  __\    78    0  __   0   20    /    19    1    /    39    1    /     0   40    /     0   79    /

   1   77  __\     1  156  __\   157  156  __\   313    0  __\   313  312  __  77   79    /   156    0    /     0  156    /     0  312    /   312    0    /

   0  625  __\   625  625  __\  1250    0  __\  1250 1250  __\     0 2500  __ 625    0    /     0  625    /     0 1250    /  1250    0    /  2500    0    /

 500 2500  __\  3000    0  __\  1000 2000
2000  500    /  2000 3000    /  4000 3000
Successful!

Enter A,B,C and D (Minus for Quit): -1
Press any key to continue
*/

#18

格式本来好好的,一贴就全乱了.再试贴一次运算结果
Enter A,B,C and D (Minus for Quit): 1000 2000 3000 4000
Total Steps: 27
   1    0  __\     0    1  __\     1    1  __\     1    2  __\     0    3  __   0    0    /     1    0    /     0    1    /     1    0    /     2    0    /
   
   2    3  __\     5    0  __\     5    5  __\     0   10  __\    10   10  __   0    2    /     0    5    /     5    0    /    10    0    /     0   10    /
   
  20    0  __\    20   19  __\     0   39  __\    39   39  __\    78    0  __   0   20    /    19    1    /    39    1    /     0   40    /     0   79    /
   
   1   77  __\     1  156  __\   157  156  __\   313    0  __\   313  312  __  77   79    /   156    0    /     0  156    /     0  312    /   312    0    /
  
   0  625  __\   625  625  __\  1250    0  __\  1250 1250  __\     0 2500  __ 625    0    /     0  625    /     0 1250    /  1250    0    /  2500    0    /
 
 500 2500  __\  3000    0  __\  1000 2000
2000  500    /  2000 3000    /  4000 3000
Successful!

Enter A,B,C and D (Minus for Quit): -1
Press any key to continue