约瑟夫问题（约瑟夫环）

小甲鱼

题目：用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出。

故事情节：

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

视频讲解：http://blog.fishc.com/1959.html


源代码参考：http://bbs.fishc.com/thread-25337-1-1.html

兢兢

[人数] = 100
[数数] = 3
Dim b()
ReDim b([人数])
For i=1 to [人数]
   b(i) = 1
Next
i=1
n = [人数]
m=1
While (n > 1)
    While (i<=[人数])
    If b(i) =1 Then
        If m mod [数数] = 0 Then
            b(i)=0
           n = n - 1
          s=s & "→" & i
         End If
        m = m + 1
    End If
    i = i + 1
Wend
i = 1
Wend
msgbox s,vbokonly,"排除顺序"
For i = 1 To [人数]  '查找最后一个数字
        If b(i) = 1 Then
                msgBox  "最后剩下的数是" & i,vbokonly,"约瑟夫环"
        End If
Next

青春@无限

强烈支持楼主ing……

Mr.

谢谢楼主分享

Dokgo.小浪_

强烈支持楼主ing……我真的很感悟……

Dokgo.小浪_

真是难得给力的帖子啊。我只说两句……

じO-联合

强烈支持楼主ing……

じO-联合

强烈支持楼主ing……

安静的渴

支持楼主

1205191816

强烈支持楼主ing……

被忧伤腐蚀

强烈支持楼主ing……

everest

强烈支持楼主ing……

安吉

/*编号为1~N的N个人按顺时针方向坐一圈，每个人持有一个密码（正整数，可以自由输入），
开始人选一个正整数作为报数上限值M，从第一个人按顺时针方向自1开始顺序报数，报到M时
停止报数。报M的人出列，将他的密码作为新的M值，从他顺时针方向上的下一个人开始从1报数，
如此下去，直至所有人出列*/
#include<stdio.h>
#include<stdlib.h>

typedef struct circular_linked_list{
        int password;
        int index;
        struct  circular_linked_list *next;
} Node;

Node * Creat (int n);

int main()
{
        int i,n,m;
        Node *p, *temp;
        printf("输入一个正整数n，代表有n个人围成一个圈。\n");
        scanf("%d",&n);
        p=Creat(n);
        printf("输入一个正整数M，代表第一个人报数的上限值。\n");
        scanf("%d",&m);

    m=m>n?m%n:m;
        while(p->next!=p)
        {
                for(i=1;i<m-1;i++)
                        p=p->next;
                printf("%d->",p->next->index);
                m=p->next->password;
        m=m>n?m%n:m;
                temp=p->next;
                p->next=temp->next;
                free(temp);
                p=p->next;
        }
        return 0;
}
Node *Creat(int n)
{
        int i;
        Node *head, *p, *s;
        head = (Node *)malloc(sizeof(Node));
        p=head;
        printf("输入N个正整数，代表每个人手中的密码\n");
        for(i=0;i<n;i++)
        {
                s=(Node *)malloc(sizeof(Node));
                scanf("%d",&s->password);
                s->index=i+1;
                p->next=s;
                p=s;
        }
        s->next=head->next;
        free(head);
        return s->next;
}

yinjia哈哈

感谢楼主

yinjia哈哈

感谢楼主啊

铭记太阳

每人持有密码的高级约瑟夫环代码用循环链表实现：

#include<stdio.h>
#include<stdlib.h>
#define NUM 10
#define START 2
struct Date
{
    int number;
    int password;
    struct Date *next;
};

void ListInsert(struct Date **pt,int num,int pass)
{
    struct Date *tmp=NULL,*middle=NULL;
    tmp=(struct Date *)malloc(sizeof(struct Date));
    if(tmp==NULL)   exit(1);
    tmp->number = num;
    tmp->password = pass;
    if((*pt)!=NULL)
    {        
        middle = *pt;
        *pt = tmp;
        tmp->next = middle;
    }
    else
    {
        tmp->next=NULL;
        (*pt)=tmp;
    }
//    printf("插入成功！\n");
}

void ListPrint(struct Date *pt)
{
    while(pt!=NULL) 
    {
            printf("%d--%d\n",pt->number,pt->password);
        pt = pt->next;
    }
    putchar('\n');
}
void ListCircle(struct Date **pt)
{
    struct Date *rear=*pt;
    while(rear->next!=NULL)
        rear=rear->next;
    rear->next=*pt;
}

void JosephusHard(struct Date *pt)
{
    struct Date *kill,*previous;
    unsigned code=START; 
    int i=0,FLAG=0; 
    printf("kill game start!\n");
    printf("start code is: %d\n\n",START);   

    while((pt->next)!=pt)
    {
        if(code<1) 
        {
            printf("the code is error\n");
            exit(1);
        }
        else if(code==1)
        {
            FLAG=1;
            goto specialsec;
        }
        else if(code==2)
        {
             ;   
        }
        else
        {
                for(i=code-2;i>0;--i)
                    pt=pt->next;
        }
        kill=pt->next;
        code=kill->password;
        pt->next=kill->next;
        printf("kill No.%d\t",kill->number);
        printf("next code is %d\n\n",code);
        free(kill);
        pt=pt->next;

specialsec:
        if(FLAG)
        {
            FLAG=0;        //重置FLAG
            previous=pt;
            while(previous->next!=pt)
            {
                previous=previous->next;        
            }
            kill=pt;            
            pt=previous;
            code=kill->password;
            pt->next=kill->next;
            printf("kill No.%d\n",kill->number);
            printf("next code is %d\n",code);
            free(kill);
            pt=pt->next;
        }


    
    }
    printf("kill game over, No.%d survive!\n",pt->number);

}

int main()
{
    struct Date *pt=NULL;
    for(int i=NUM ;i>0;i--)
        ListInsert(&pt,i, NUM+1-i);
    ListPrint(pt);
    ListCircle(&pt);

    JosephusHard(pt);
    return 0;
}

Theen

# Python 3
number = int(input("Game number:"))
people = []
for i in range(number):
    people += [[i - 1, i + 1, i + 1]]
people[0][0], people[number - 1][2] = number - 1, 0

flag = 0
for deadnumber in range(number - 2):
    for j in range(2):
        flag = people[flag][2]
    temp = people[flag]
    temp2 = temp[2]
    people[temp[0]][2] = temp[2]
    people[temp[2]][0] = temp[0]
    people[flag] = [0, 0, 0]
    flag = temp2

print(people[flag][1], people[people[flag][2]][1])

圣狄雅哥

学习了

lils76