2

昨晚我一直在不使用递归实现河内塔。我在 Wikipedia 上找到了关于TOH的 wiki 页面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;
}

请帮帮我。

4

1 回答 1

1
  • #include<math.h>在您的程序中不需要。
  • 不需要围绕单个语句的块大括号。
  • 在一行中合理地聚合代码会产生更少的代码行数，而不会损害可读性（有时甚至会提高它的可读性）。
  • 通过将重复的相似代码部分提取到一个新的参数化函数中，我们还可以减少 LOC、错误概率并促进可理解性。参照。例如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;
}
于 2015-05-07T13:20:10.667 回答