计机羊咩咩 发表于 2014-10-12 09:41:57

魔术师发牌问题 解法

我自己也不造写得好不好撒有疑问或者建议请积极联系我撒{:1_1:}
希望下列源码能帮助到各位(最好拉到编译器debug分析光看代码看不到啥)
下面是魔术师发牌问题:
人工倒推的方法是:在桌子上放13空盒子排成一圈,从1开始顺序编号,将黑桃A放入1号盒子中,从下一个空盒子开始对空的盒子计数,当数到第二个空盒子时,将黑桃2放入空盒子中,然后再从下一个空盒子开始对空盒子计数,顺序放入3、4、5...,直到放入全部3张牌。注意在计数时要跳过非空的盒子,只对空盒子计数。最后牌在盒子中的顺序,就是魔术师手中原来牌的顺序。

魔术师发牌问题其实是约瑟夫问题的另一面   解法相似!

源代码:
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX 13

typedef struct List
{
        int Num;
        int Size;
        struct List *Next;
}LIST;

LIST *CreateList(void);
void Magic(LIST *Tail);
void DestroyList(LIST *Head);
int main(void)
{
        LIST *Tail;
        Tail = CreateList();
        Magic(Tail);
        DestroyList(Tail);
        return 0;
}

LIST *CreateList(void)
{
        //此函数创建环链表后返回链尾!
       
        LIST *Head,*Tail,*Temp;
        int Count = 1;
        if (NULL == (Temp = malloc(sizeof(LIST))))
        {
                printf("Creating failure!\n");
                exit(1);
        }

        Head = Temp;
        Head->Num = FALSE;
        Head->Size = Count++;
        while (Count <= MAX)                     //1开始13结束刚好13个数
        {
                if (NULL == (Temp->Next = malloc(sizeof(LIST))))
                {
                        printf("No more memory!\n");
                        exit(1);
                }

                Temp = Temp->Next;
                Temp->Num = FALSE;
                Temp->Size = Count++;
        }
        Tail = Temp;
        Temp->Next = Head;
        printf("Creating completed!\n");

        return Tail;
}

void Magic(LIST *Tail)
{
        LIST *Flag = Tail,*Head = Tail->Next;
        int Gap = 1;

        while (Gap <= MAX)
        {
                for (int Turn = 1; Turn < Gap; Turn++)
                {
                        Head = Head->Next;
                        while(FALSE != Head->Num)            //关键1!!!
                                Head = Head->Next;               //排除已存在值的节点,从下一个不存在值得节点开始计算!
                }
                Head->Num = Gap++;                //间距增加
                while (FALSE != Head->Num && Gap <= MAX)    //关键2!!!   不加Gap <= MAX的话当链表填满后会出现死循环
                        Head = Head->Next;                // 获取下一个空值的节点
        }
       
        Head = Flag->Next;
        while (Flag != Head)                   //这个循环不会输出最后一个节点的信息
        {
                printf("%d(%d) ",Head->Num,Head->Size);
                Head = Head->Next;
        }
        printf("%d(%d)\n",Head->Num,Head->Size);      //输出最后一个节点的信息
}

void DestroyList(LIST *Head)            //释放环链表通用函数
{
        LIST *Flag = Head, *Temp = Head->Next;

        while (1)
        {
                if (Flag == Temp)break;
                else if (NULL == Flag || NULL == Temp)
                {
                        printf("There is no loop chain!\n");
                        exit(1);
                }
                Temp = Temp->Next->Next;
                Flag = Flag->Next;
        }

        Flag = Head;
        Temp = Head = Head->Next;         //从“标记”节点的下一个节点开始循环释放

        while (Flag != Head)
        {
                Head = Head->Next;
                free(Temp);
                Temp = Head;
        }
        free(Flag);
        printf("\nRelease completed!\n");
}



大个的糖果 发表于 2014-11-1 06:42:33

页: [1]
查看完整版本: 魔术师发牌问题 解法