魔术师发牌问题 解法
我自己也不造写得好不好撒有疑问或者建议请积极联系我撒{: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");
}
页:
[1]