约瑟夫问题（约瑟夫环）
题目：用循环链表模拟约瑟夫问题，把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
本帖最后由 兢兢 于 2013-7-4 02:44 编辑
[人数] = 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……
谢谢楼主分享 强烈支持楼主ing……我真的很感悟…… 真是难得给力的帖子啊。我只说两句…… 强烈支持楼主ing…… 强烈支持楼主ing…… 支持楼主 强烈支持楼主ing……
强烈支持楼主ing…… 强烈支持楼主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;
structcircular_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;
}
感谢楼主 感谢楼主啊 每人持有密码的高级约瑟夫环代码用循环链表实现：
#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;
}
# Python 3
number = int(input("Game number:"))
people = []
for i in range(number):
people += []
people, people = number - 1, 0
flag = 0
for deadnumber in range(number - 2):
for j in range(2):
flag = people
temp = people
temp2 = temp
people] = temp
people] = temp
people =
flag = temp2
print(people, people])
本帖最后由 圣狄雅哥 于 2018-1-29 21:12 编辑
学习了
页:
[1]