河內塔的實施 - 迭代程序

Question

昨晚我一直在實施河內塔而不使用遞歸。我在維基頁面wiki上找到了關於同一主題的維基百科上的算法。 我已經實現了它，它工作正常（對於奇數：現在）。但是我對代碼不滿意，它的體積很大，因此我想以某種方式對代碼進行修改，以便實際的代碼行可以通過相同的功能和算法減少。

#include<stdio.h> 
#include<math.h> 
#include<stdlib.h> 

display(int *A, int *B, int *C, int atop , int btop ,int ctop) 
{ 
    int i; 
    if(A[0]==0) 
     printf("\nEmpty A"); 
    else 
    { 
     printf("\nA Stack :\n"); 
     for (i=atop; i>=1; i--) 
     { 
      printf(" %d\n",A[i]); 
     } 
    } 

    if(B[0]==0) 
     printf("\nEmpty B\n"); 
    else 
    { 
     printf("\nB Stack: \n"); 
     for (i=btop; i>=1; i--) 
     { 
      printf(" %d\n",B[i]); 
     } 
    } 

    if(C[0]==0) 
     printf("\nEmpty C\n"); 
    else 
    { 
     printf("\nC Stack: \n"); 
     for (i=ctop; i>=1; i--) 
     { 
      printf(" %d\n",C[i]); 
     } 
    } 

} 


int main() 
{ 
    int step=0; 
    int n,i,*A,*B,*C,atop,btop,ctop,count=0; 
    int max=1; 


    printf("\nInput # disks"); 
    scanf("%d",&n); 

    for(i=0; i<n; i++) 
    { 
     max*=2; 
    } 
    max=max-1; 
    printf("\n Max is :%d",max); 
    A= (int *)malloc(sizeof(int)*(n+1)); 
    B= (int *)malloc(sizeof(int)*(n+1)); 
    C= (int *)malloc(sizeof(int)*(n+1)); 
    A[0]=B[0]=C[0]=0; 
    atop=btop=ctop=0; 
    for(i=n; i>0; i--) 
    { 
     atop++; 
     A[0]++; 
     A[atop]=i; 
     B[atop]=0; 
     C[atop]=0; 
    } 

    display(A,B,C,atop,btop,ctop); 


    do 
    { 
     count+=1; 
     step=(step%3)+1; 


     switch(step) 
     { 

     case 1://move between pegs A and C 

      printf("\n%d count:",count); 
      if(count%2 ==1)//move of disk 1 
      { 
       if(A[atop]==1) 
       { 

        ctop++; 
        C[ctop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        C[0]++; 
        A[0]--; 
        printf("\nDisk %d: A->C",C[ctop]); 
       } //i is on A 
       else if(C[ctop]==1)//1 is on b 
       { 

        atop++; 
        A[atop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        A[0]++; 
        C[0]--; 
        printf("\nDisk %d: C->A",A[atop]); 

       } 
      }//Movement of disk #1 

      else if(count %2 ==0) 
      { 
       if(ctop !=0 && A[atop]>C[ctop]) 
       { 
        //C[0]--; 
        atop++; 
        A[atop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        C[0]--; 
        A[0]++; 
        printf("\nDisk %d: C->A",A[atop]); 
       } 
       else if (ctop ==0) 
       { 
        ctop++; 
        C[ctop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        C[0]++; 
        A[0]--; 
        printf("\n disk %d:A->C",C[ctop]); 
       } 
       else if(atop !=0 && C[ctop]>A[atop]) 
       { 

        ctop++; 
        C[ctop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        C[0]++; 
        A[0]--; 
        printf("\nDisk %d: A->C",C[ctop]); 

       } 
       else if(atop==0) 
       { 
        atop++; 
        A[atop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        C[0]--; 
        A[0]++; 
        printf("\nDisk %d: C->A",A[atop]); 
       } 

      }//Movement of Disk non1 


      break; 


     case 2://move between pegs A and B 

      printf("\n%d count:",count); 
      if(count%2 ==1)//move of disk 1 
      { 
       if(A[atop]==1) 
       { 

        btop++; 
        B[btop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        B[0]++; 
        A[0]--; 
        printf("\nDisk %d: A->B",B[btop]); 
       } //i is on A 
       else if(B[btop]==1)//1 is on b 
       { 

        atop++; 
        A[atop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        A[0]++; 
        B[0]--; 
        printf("\nDisk %d: B->A",A[atop]); 

       } 
      }//Movement of disk #1 

      else if(count %2 ==0) 
      { 
       if(btop !=0 && A[atop]>B[btop]) 
       { 
        //B[0]--; 
        atop++; 
        A[atop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        B[0]--; 
        A[0]++; 
        printf("\nDisk %d: B->A",A[atop]); 
       } 
       else if (btop ==0) 
       { 
        btop++; 
        B[btop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        B[0]++; 
        A[0]--; 
        printf("\n disk %d:A->B",B[btop]); 
       } 
       else if(atop !=0 && B[btop]>A[atop]) 
       { 

        btop++; 
        B[btop]=A[atop]; 
        A[atop]=0; 
        atop--; 
        B[0]++; 
        A[0]--; 
        printf("\nDisk %d: A->B",B[btop]); 

       } 
       else if(atop==0) 
       { 
        atop++; 
        A[atop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        B[0]--; 
        A[0]++; 
        printf("\nDisk %d: B->A",A[atop]); 
       } 

      }//Movement of Disk non1 


      break; 

     case 3://move between pegs C and B 

      printf("\n%d count:",count); 
      if(count%2 ==1)//move of disk 1 
      { 
       if(C[ctop]==1) 
       { 

        btop++; 
        B[btop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        B[0]++; 
        C[0]--; 
        printf("\nDisk %d: C->B",B[btop]); 
       } //i is on C 
       else if(B[btop]==1)//1 is on b 
       { 

        ctop++; 
        C[ctop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        C[0]++; 
        B[0]--; 
        printf("\nDisk %d: B->C",C[ctop]); 

       } 
      }//Movement of disk #1 

      else if(count %2 ==0) 
      { 
       if(btop !=0 && C[ctop]>B[btop]) 
       { 
        //B[0]--; 
        ctop++; 
        C[ctop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        B[0]--; 
        C[0]++; 
        printf("\nDisk %d: B->C",C[ctop]); 
       } 
       else if (btop ==0) 
       { 
        btop++; 
        B[btop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        B[0]++; 
        C[0]--; 
        printf("\n disk %d:C->B",B[btop]); 
       } 
       else if(ctop !=0 && B[btop]>C[ctop]) 
       { 

        btop++; 
        B[btop]=C[ctop]; 
        C[ctop]=0; 
        ctop--; 
        B[0]++; 
        C[0]--; 
        printf("\nDisk %d: C->B",B[btop]); 

       } 
       else if(ctop==0) 
       { 
        ctop++; 
        C[ctop]=B[btop]; 
        B[btop]=0; 
        btop--; 
        B[0]--; 
        C[0]++; 
        printf("\nDisk %d: B->C",C[ctop]); 
       } 

      }//Movement of Disk non1 


      break; 


     default: 
      printf("Some Error!"); 
     }//switch end 
//  display(A,B,C,atop,btop,ctop); 
    } 
    while((count <=max) && (C[0]!=n)); 

    printf("\n"); 
    //display(A,B,C,atop,btop,ctop); 
      display(A,B,C,atop,btop,ctop); 

    return 0; 
} 

請幫助我。

Answer 1

• #include<math.h>在您的程序中不需要。
• 不需要圍繞單個語句的塊大括號。
• 一行代碼的理想聚合可以產生較少的代碼行，而不會損害可讀性（有時甚至可以改進它）。
• 通過將重複的類似代碼段提取到新的參數化函數中，我們還可以減少LOC，錯誤概率以及便於理解。參看即G。 display_stack()，move()，movement()以下。
• 您的程序包含具有基本相同值的變量：A [0] = atop，B [0] = btop，C [0] = ctop。通過放棄atop，btop和ctop，我們可以簡化函數調用並減少LOC等。
• 如果我們想要分配的內存（大部分）填充零，我們可以使用calloc()。

這是您的程序的修改版本。

#include<stdio.h> 
#include<stdlib.h> 

display_stack(int *stack, char name) 
{ 
    int i; 
    if (!*stack) 
     printf("\nEmpty %c\n", name); 
    else 
    { 
     printf("\n%c Stack:\n", name); 
     for (i = *stack; i; --i) printf(" %d\n", stack[i]); 
    } 
} 

display(int *A, int *B, int *C) 
{ 
    display_stack(A, 'A'); 
    display_stack(B, 'B'); 
    display_stack(C, 'C'); 
} 

void move(int *fromstack, char fromname, int *tostack, char toname) 
{ 
    tostack[++*tostack] = fromstack[*fromstack]; 
    fromstack[*fromstack] = 0; // actually unneeded; makes debugging easier 
    --*fromstack; 
    printf("\n disk %d:%c->%c", tostack[*tostack], fromname, toname); 
} 

void movement(int *X, char Xnm, int *Y, char Ynm, int countm2) 
{ 
    if (countm2 == 1)//move of disk 1 
    { 
     if (X[*X] == 1) move(X, Xnm, Y, Ynm); //i is on X 
     else 
     if (Y[*Y] == 1) move(Y, Ynm, X, Xnm); //1 is on Y 
    }//Movement of disk #1 
    else 
    if (countm2 == 0) 
    { 
     if (*Y != 0 && X[*X] > Y[*Y]) move(Y, Ynm, X, Xnm); 
     else 
     if (*Y == 0)     move(X, Xnm, Y, Ynm); 
     else 
     if (*X != 0 && Y[*Y] > X[*X]) move(X, Xnm, Y, Ynm); 
     else 
     if (*X == 0)     move(Y, Ynm, X, Xnm); 
    }//Movement of Disk non1 
} 

int main() 
{ 
    int step=0; 
    int n,i,*A,*B,*C,count=0; 
    int max=1; 

    printf("\nInput # disks"); 
    scanf("%d",&n); 

    for (i=0; i<n; i++) max*=2; 
    max=max-1; 
    printf("\n Max is :%d",max); 
    A = calloc(1+n, sizeof *A); 
    B = calloc(1+n, sizeof *B); 
    C = calloc(1+n, sizeof *C); 
    for (i=n; i>0; i--) A[++*A]=i; 

    display(A, B, C); 

    do 
    { 
     count+=1; 
     step=(step%3)+1; 
     switch (step) 
     { 
     case 1://move between pegs A and C 
      printf("\n%d count:",count); 
      movement(A, 'A', C, 'C', count%2); 
      break; 

     case 2://move between pegs A and B 
      printf("\n%d count:",count); 
      movement(A, 'A', B, 'B', count%2); 
      break; 

     case 3://move between pegs C and B 
      printf("\n%d count:",count); 
      movement(C, 'C', B, 'B', count%2); 
      break; 

     default: 
      printf("Some Error!"); 
     }//switch end 
    } while (count<=max && C[0]!=n); 

    printf("\n"); 
    display(A, B, C); 

    return 0; 
}