C程序設計例解(08)

2019-11-17 05:40:41

字體：大中小

來源：轉載

供稿：網友

07. 有2*n個盒子排成一行，其中有兩個相鄰的空盒，有n-1個盒子有符號'A'，有n-1個盒子有符號'B'。例如，n=5，并有初始配置如下：
ABBA..ABAB
試編制程序，將輸入的盒子排列狀態按以下交換規則將全部‘A’放到全部‘B’的左邊，不管相鄰兩空盒的位置。交換規則是任意兩個非空相鄰盒子的內容可移入兩個空盒中，但移動時不得變更兩符號的前后次序。編寫程序輸入初始配置后，找出達到目標要求的最少交換次數的方案。
解：
    從一種盒子排列出發，將其中兩個非空相鄰盒子中的內容移入空盒的每一種移動，會使盒子產生新的排列狀態，采用試探法窮舉所有可能的移動找問題的解。首先將盒子初始排列存入移動步聚表，然后是試探和回溯循環。循環工作內容有：檢查當前排列，若當前排列是要求的最終狀態，則將達到該狀態的移動步聚保存，并回溯去找更少移動步數的解。在試探超過限定的深度或當前狀態的所有可能移動都已試探窮盡情況下回溯；否則對當前狀態取其當前移動方法產生新的后繼狀態存入移動步聚表，并繼續向前試探。為能從某種排列出發，通過移動產生更接近目標要求的排列，對移動方法的選取作如下規定：
    。擦過無意義的往返移動；
    。不把兩個相鄰的同為符號‘A’的盒子向后移；
    。不把兩個相鄰的同為符號‘B’的盒子向前移；
    。不把兩個盒子移入到這樣的位置，移入后其首尾沒有一個與相鄰的盒子相同。
試探回溯找解算法如下：
算法---試探回溯找解
{
    輸入初始排列；
    初始狀態存入移動步聚表；
    設置其它初值；
    d=0;        /*當前試探深，或當前狀態位置*/
    do
    {
        if(當前狀態為盒子排列的終態)
        {
            保存解；
            記錄當前解的試探深度；
            回溯；
            if(取盡所有可能的解)break;
        }
        if(試探深度超過設定值，或取盡當前狀態的所有選擇)
        {
            回溯；
            if(取盡所有可能的選擇)break;
        }
        else
        {
            求新狀態的空盒位置；
            取當前狀態的移動方法和當前狀態；
            設定當前狀態的下一個移動方法；
            擦過各種不希望的方法；
            生成新狀態；
            試探深度增1；
        }
    }while(1);
    if(找到解)
        輸出解；
}

程序代碼如下：
#include<stdio.h>
#include<string.h>
#define N 30
#define DEPTH 15
char b[2*N+1];
strUCt node
{
    int empty;        /*兩空盒的開始位置*/
    char s[2*N+1];    /*盒子排列*/
    int no;           /*下一個移動開始的位，或稱移動方法*/
}q[DEPTH];            /*移動步聚表*/
char result[DEPTH][2*N+1];    /*存放解*/
char *s;
int best,empty,i,j,n,an,bn,sn,c,d;
void main()
{
        scanf("%d",&n);
    printf("Enter initial state./n");    /*輸入初始狀態*/
    for(an=bn=sn=i=0;i<2*n;)
    {
        c=getchar();
        if(c==' ')
        {
            if(sn)continue;        /*強制兩空白符連續出現*/
            sn=1;
            empty=i;
            b[i++]='_';
            b[i++]='_';
        }
        if(c=='A'c=='a')
        {
           if(an==n-1)continue;    /*限制A的個數*/
           an++;b[i++]='A';
        }
        if(c=='B'c=='b')
        {
            if(bn==n-1)continue;    /*限制B的個數*/
            bn++;b[i++]='B';
        }
    }
    b[2*n]='/0';
    strcpy(q[0].s,b);        /*初始狀態存入移動步聚表*/
    q[0].empty=empty;
    q[0].no=0;
    best=DEPTH-1;            /*設定試探深度*/
    d=0;
    do
    {
        for(s=q[d].s; *s!='B';s++);
        for(;*s&&*s!='A';s++);
        if(*s=='/0')            /*當前狀態為盒子排列的終態*/
        {
            for(j=0;j<=d;j++)        /*保存解*/
                strcpy(result[j],q[j].s);
            best=d;        /*記錄當前解的試探深度*/
            d--;            /*回溯*/
            while(d>=0&&q[d].no==2*n-1)d--;
            if(d<0)break;        /*取盡所有可能的選擇*/
        }
        if(d>=bestq[d].no==2*n-1)
        {
            d--;        &n