BFS（二）：數的變換

【例1】整數變換（POJ 3278 “Catch That Cow”）

      給定兩個整數a和b（0 ≤a，b≤100,000），要求把a變換到b。變換規則為：（1）目前數加1；（2）目前數減1；（3）目前數加倍。

      編寫程式求從a到b最少需要的變換次數。

      例如，從5變換到17，最少需要4歩，具體過程為：5-10-9-18-17。

      （1）程式設計思路。

      用數組que[100001]模拟隊列，隊頭指針front和隊尾指針rear的初始值均為0。

      定義數組visit[100001]标記某數是否産生并記錄該數産生所需的最少變換步數。初始時，所有元素值均為-1，visit[i]=-1表示整數i未變換出來，visit[i]=n表示整數i從初始數開始經過n次變換得到。

      為體會visit數組的作用，我們以整數5開始變換為例說明。由于5是初始數，是以置visit[5]=0。

      由于按3種變換規則，5可以變換為4,6和10，是以置visit[4]=visit[6]=visit[10]=visit[5]+1=1，即4、6和10這3個數通過1次變換得到；4可以變換為3、5（visit[5]!=-1，已通路過不再處理）和8，是以置visit[3]=visit[8]=visit[4]+1=2，即3和8可以通過2次變換得到。……

      （2）源程式。

#include <iostream>  

using namespace std;   

int main()  

{  

    int a, b,front,rear,t,i;  

    int que[100001]={0},visit[100001];  

    cin>>a>>b;  

    for (i=0;i<=100000;i++)

          visit[i]=-1;

    front = 0, rear = 0;  

    que[rear++] = a;     // 初始元素a 入隊

    visit[a] = 0;  

    while (front != rear)  

    {  

        t = que[front++];  

        if (t == b)  

        {  

            cout<<visit[t]<<endl;  

            break;

        }  

        if (t > 0 && visit[t-1]==-1)  

        {  

            visit[t-1] = visit[t]+1;  

            que[rear++] = t-1;  

        }  

        if (t < 100000 && visit[t+1]==-1)  

        {  

            visit[t+1] = visit[t]+1;  

            que[rear++] = t+1;  

        }  

        if (t <= 50000 && visit[t*2]==-1)  

        {  

            visit[t*2] = visit[t]+1;  

            que[rear++] = t*2;  

        }  

    }

    return 0;  

}

【例2】質數變換（POJ 3126 “Prime Path”）

      給定兩個四位質數a和b，要求把a變換到b。變換的過程要求：（1）每次變換出來的數都是一個四位質數；（2）每一步變換所得的質數與前一步得到的質數隻能有一個位不同。

      編寫程式求從a到b最少需要的變換次數，無法變換則輸出Impossible。

      例如，從1033變換到8179最少需要6歩，具體變換過程為1033、1733、3733、3739、3779、8779、8179。

      （1）程式設計思路。

      定義數組char prime[10000];來進行質數的判斷，prime[x]=‘1’表示整數x是質數，prime[x]=‘0’表示整數x不是質數。采用篩法建構質數判定表prime[10000]。 

      在整數x進行變換時，可分别對x的千位、百位、十位和個位進行 （可用循環for (i=0;i<4;i++) 處理），每位上可由0~9這10種選擇（可用循環 for (j=0;j<10;j++)處理）。即數的變換可以采用一個二重循環處理。若變換出的整數num如果是一個4位數（num>=1000），且沒有通路過（visit[num]=-1），還是質數（prime[num]='1'），則将産生的整數num入隊。

      （2）源程式及運作結果。

#include <iostream> 

using namespace std;

char prime[10000];

void GetPrime()              // 用篩法建構質數判定表 

{

      int i,j;

      for (i=2;i<10000;i++)

              prime[i]='1';

       for(i=2;i<10000;i++)    

       {

             if (prime[i]=='1')

                     for (j=2*i;j<10000;j+=i)

                            prime[j]='0';

         }

        prime[1]='0'; 

}

void BFS(int k,int m)

{

    int visit[10000],que[10000],a[4]={1,10,100,1000};

    int front,rear,i,j,s,x,y,num;

    for (i=1000;i<10000;i++)

              visit[i]=-1;

    front=rear=0;

    que[rear++]=k;              // k入隊  

    visit[k]=0;

    while(front!=rear)

    {

           s=que[front++];         // 隊頭元素出隊

           if (s==m)

           {

                     cout<<visit[s]<<endl;

                     return;

           }

           for (i=0;i<4;i++)

          { 

              for (j=0;j<10;j++)

              {

              x=s/(a[i]*10);     

              y=s%a[i];

              num=x*a[i]*10+j*a[i]+y;

              if (num>1000 && visit[num]==-1 && prime[num]=='1')  

                       {   

                 que[rear++]=num;     // 變換後的質數入隊

                 visit[num]=visit[s]+1;

                       }

                  }

              }

       }

    cout<<"Impossible"<<endl;

}

int main()

{  

    int n,k,m;

    GetPrime();

    cin>>n; 

    while (n--) 

    { 

        cin>>k>>m; 

        BFS(k,m); 

    } 

    return 0;

}

posted on 2019-07-08 11:53 aTeacher 閱讀(...) 評論(...) 編輯 收藏