约瑟夫问题、魔术师发牌问题

• 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
• 然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

//n个人围圈报数，报m出列，最后剩下的是几号？
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}node;

node *create(int n)
{
    node *p = NULL, *head;
    head = (node*)malloc(sizeof (node ));
    p = head;
    node *s;
    int i = 1;

    if( 0 != n )
    {
        while( i <= n )
        {
            s = (node *)malloc(sizeof (node));
            s->data = i++;    // 为循环链表初始化，第一个结点为1，第二个结点为2。
            p->next = s;
            p = s;
        }
        s->next = head->next;
    }

    free(head);

    return s->next ;
}

int main()
{
    int n = 41;
    int m = 3;
    int i;
    node *p = create(n);
    node *temp;

    m %= n;   // m在这里是等于2

    while (p != p->next )
    {
        for (i = 1; i < m-1; i++)
        {
            p = p->next ;
        }

        printf("%d->", p->next->data );

        temp = p->next ;                //删除第m个节点
        p->next = temp->next ;
        free(temp);

        p = p->next ;
    }

    printf("%d\n", p->data );

    return 0;
}

• 问题描述：魔术师利用一副牌中的13张黑牌，预先将他们排好后叠放在一起，牌面朝下。对观众说：“我不看牌，只数数就可以猜到每张牌是什么，我大声数数，你们听，不信？现场演示。”魔术师将最上面的那张牌数为1，把他翻过来正好是黑桃A，将黑桃A放在桌子上，第二次数1,2，将第一张牌放在这些牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上这样依次进行将13张牌全部翻出，准确无误。
• 问题：牌的开始顺序是如何安排的？

// 发牌顺序计算
void Magician(linklist head)
{
    linklist p;
    int j;
    int Countnumber = 2;

    p = head;
    p->data = 1;  //第一张牌放1

    while(1)
    {
        for(j=0; j < Countnumber; j++)
        {
            p = p->next;
            if(p->data != 0)  //该位置有牌的话,则下一个位置
            {
                p = p->next;
                j--;
            }
        }

        if(p->data == 0)
        {
            p->data = Countnumber;
            Countnumber ++;

            if(Countnumber == 14)
                break;
        }
    }
}