编程论坛 » 数据结构与算法 » 回溯法解决虫蚀问题

diaoxue 发表于 2007-12-9 10:07

回溯法解决虫蚀问题

我输出absum，知道不对了，有六位，还有七位的，应该是五位啊 ，帮忙看下，谢了
我输出absum，知道不对了，有六位，还有七位的，应该是五位啊 ，帮忙看下，谢了
[code=c]
/*ABCED+BDACE=EBBAA
key:10342
*/
#include <iostream.h>
int i=0;
const int n=5;
int a[n]={0,1,2,4,3};//ABCED 在x中的下标
int b[n]={1,3,0,2,4};//BDACE 在x中的下标
int absum[n]={0};
int c[n]={4,1,1,0,0};//EBBAA 在x中的下标
int x[n]={0,1,2,3,4};
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void Disp()
{
for(int j=n-1;j>0;j--)
{
  absum[j]+=(x[a[j]]+x[b[j]]);
  absum[j-1]+=(absum[j]/5);//进位
  absum[j]=absum[j]%5;
}
absum[0]+=(x[a[0]]+x[b[0]]);
for(int k=0;k<n;k++)
   cout<<absum[k];//应该是五位，怎么还输出六位，七位的啊
cout<<endl;
int flag=1;
for(j=0;j<n;j++)
{
  if(absum[j]!=x[c[j]])//得到结果
   flag=0;
}
if(flag)
{
  cout<<"Get the key^_^"<<endl;//输出
  cout<<"  ";
  for(int k=0;k<n;k++)
   cout<<x[a[k]];
  cout<<"+ ";
  for(k=0;k<n;k++)
   cout<<x[b[k]];
  cout<<"----------"<<endl;
  for(k=0;k<n;k++)
   cout<<x[c[k]];
  cout<<endl;
}
}
void BackTrack(int i)//回溯
{
if(i>=n)
  //cout<<"END"<<endl;
  Disp();
else
{
  for(int j=i;j<n;j++)
  {
   Swap(x[i],x[j]);
   BackTrack(i+1);
   Swap(x[i],x[j]);
  }
}
}
int main()
{
BackTrack(i);
return 0;
}[/code]

[[italic] 本帖最后由 diaoxue 于 2007-12-9 10:17 编辑 [/italic]]

diaoxue 发表于 2007-12-18 09:51

是不是注释写的不详细啊
大家指点下啊
我自己调试了好多次，都没找到原因

diaoxue 发表于 2008-1-10 21:49

终于搞定了，就是absum数组累加了，应该每次运算结束后清零了。
/*ABCED+BDACE=EBBAA
key:10342
*/
#include <iostream>
using namespace std;

int t=0;
const int n=5;
int a[n]={0,1,2,4,3};//ABCED 在x中的下标
int b[n]={1,3,0,2,4};//BDACE 在x中的下标
int absum[n]={0};
int sum[n]={0};
int c[n]={4,1,1,0,0};//EBBAA 在x中的下标
int d[n]={0,1,2,3,4};
int x[n]={0};
void Swap(int &a,int &b)
{
        int temp=a;
        a=b;
        b=temp;
}
bool Ok()
{
        int i,j;
        for(i=0;i<n;i++)
                x[i]=d[i];
        for(j=n-1;j>0;j--)
        {
                absum[j]+=(x[a[j]]+x[b[j]]);
                absum[j-1]+=(absum[j]/5);//进位
                absum[j]=absum[j]%5;
        }
        absum[0]+=(x[a[0]]+x[b[0]]);
        for(i=0;i<n;i++)
        {
                sum[i]=absum[i];
                absum[i]=0;
        }
//        for(int k=0;k<n;k++)
//                        cout<<sum[k]<<"\t";//应该是五位，怎么还输出六位，七位的啊
//        cout<<endl;
        for(j=0;j<n;j++)
        {
                if(sum[j]!=x[c[j]])//得到结果
                        return false;
        }
        return true;
}
void Disp()
{
/*        for(int i=0;i<n;i++)
                x[i]=d[i];
        //        cout<<d[i]<<"\t";
//        cout<<endl;
        for(int j=n-1;j>0;j--)
        {
                absum[j]+=(x[a[j]]+x[b[j]]);
                absum[j-1]+=(absum[j]/5);//进位
                absum[j]=absum[j]%5;
        }
        absum[0]+=(x[a[0]]+x[b[0]]);
        for(int k=0;k<n;k++)
                        cout<<absum[k]<<"\t";//应该是五位，怎么还输出六位，七位的啊
        cout<<endl;
        int flag=1;
        for(j=0;j<n;j++)
        {
                if(absum[j]!=x[c[j]])//得到结果
                        flag=0;
        }*/
//        if(flag)
        if(Ok())
        {
                cout<<"Get the key^_^"<<endl;//输出
                cout<<"  ";
                for(int k=0;k<n;k++)
                        cout<<x[a[k]];
                cout<<endl;
                cout<<"+ ";
                for(k=0;k<n;k++)
                        cout<<x[b[k]];
                cout<<endl;
                cout<<"----------"<<endl;
                cout<<"  ";
                for(k=0;k<n;k++)
                        cout<<x[c[k]];
                cout<<endl;
        }
}
void BackTrack(int t)//回溯
{
        if(t>=n)
        //        cout<<"END"<<endl;
                Disp();
        else
        {
                for(int j=t;j<n;j++)
                {
                        Swap(d[t],d[j]);
                        BackTrack(t+1);
                        Swap(d[t],d[j]);
                }
        }
}
int main()
{
        BackTrack(t);
        return 0;
}

查看完整版本: 回溯法解决虫蚀问题