c-河内塔的实施-迭代程序

Question

我昨晚一直致力于在不使用递归的情况下实现河内塔。我在维基百科上找到了一个关于TOH的维基页面上相同主题的算法。我已经实现了它，它运行良好（对于奇数：目前）。但我对代码不满意，它有点笨重，因此我想对它进行修改，以便在考虑相同功能和算法的情况下减少实际的代码行数。

#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("  %dn",A[i]);
        }
    }
    if(B[0]==0)
        printf("nEmpty Bn");
    else
    {
        printf("nB Stack: n");
        for (i=btop; i>=1; i--)
        {
            printf("  %dn",B[i]);
        }
    }
    if(C[0]==0)
        printf("nEmpty Cn");
    else
    {
        printf("nC Stack: n");
        for (i=ctop; i>=1; i--)
        {
            printf("  %dn",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、错误概率以及便于理解。参见下面的display_stack()、move()、movement()
• 您的程序包含具有基本相同值的变量：A[0]=top，B[0]=btop，C[0]=ctop。通过删除top、btop和ctop，我们可以简化函数调用，减少LOC等
• 如果我们想要分配的内存（大部分）充满零，我们可以使用calloc()

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

#include<stdio.h>
#include<stdlib.h>
display_stack(int *stack, char name)
{
    int i;
    if (!*stack)
        printf("nEmpty %cn", name);
    else
    {
        printf("n%c Stack:n", name);
        for (i = *stack; i; --i) printf("  %dn", 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;
}