Question

C语言编程问题：约瑟夫问题求解

这个问题是以弗拉维奥•约瑟夫命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫和另外一个人是最后两个留下的人。约瑟夫说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。问题可以定义如下：

有n个囚犯站成一个圆圈，准备处决。首先从第一个人开始报数，将报数为k的人杀掉，再从下一个开始报数，并杀掉报数为k的人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

Answer 1

用一个循环链表就可以完成了！
#include<stdio.h>

struct node{
int data;
struct node *next;
}node,*list,*p,*r;

void JOSEPHU(int n,int k,int m)
{
int i,j;
list=NULL;
for(i=1;i<=n;i++)
{
p=(struct node*)malloc(sizeof(node));
p->data=i;
if(list==NULL)
list=p;
else
r->next=p;
r=p;
}
p->next=list; /*建立一个循环链表*/

p=list;
for(i=1;i<=n+1;i++)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n"); /*打印链表,并检查循环链表是不输入正确*/
p=list;
i=1;
while(p&&i<k)
{ r=p;
p=p->next;
++i;
}
for(i=1;i<n;i++)
{
for(j=1;j<m;j++)
{ r=p;
p=p->next;
}
printf("The out=%d\n",p->data);
r->next=p->next;
}
}
void main()
{
int x, y, z;
printf("input the lenth n\n");/*n,k,m分别代表总的人数，第一个报数的人，间隔的人数*/
scanf("%d",&x);
printf("input the start k\n");
scanf("%d",&y);
printf("input the m\n");
scanf("%d",&z);
JOSEPHU(x,y,z);
}

Answer 2

#include
#include
/*n表示最初有多少个人，m表示报数到多少的人离开，函数Joseph返回最后剩下的人的编号*/
int Joseph(int n, int m)
{
int count = n; /*count表示当前圈内剩下的人数*/
int num=0; /*num表示当前报的数*/
int i,j; /*i表示当前报数的人对应的下标*/
int *a, remain;
/*动态申请连续的n个存储单元用来存放每个人的编号，将空间首地址赋值给a*/
a = (int *)malloc(sizeof(int));
for(i=0; i<n; i++) a[i] = i+1; /*a[i]保存第i个人的编号*/
i = 0; /*从下标为0的人开始报数*/
while(count>1) /*如果剩余人数大于1则循环*/
{
num++;
if(num == m) /*报数到m的人离开*/
{
/*将下标为i的元素删除*/
for(j=i+1; j<count; j++) a[j-1] = a[j];
count--; /*当前剩余人数减1*/
num = 1; /*下一个人重新从1开始报数*/
}
i = m%count; /*计算下一个要报数的人的下标*/
}
remain = a[0]; /*最后只剩下一个人，将其编号赋值给remain*/
return remain;
}
来源http://zhidao.baidu.com/question/57933683.html?si=2

30个人围成一个圆圈，从第一个开始依次报数，每数到第9个就将他扔入大海，如此循环直到仅余15个人，问怎样排法才能使每次投入大海的都是非教徒。
#include "stdio.h"
void main()
{
int i,k,quit_num,a[30],*p;
p=a;
for(i=0;i<30;i++)
*(p+i)=i+1;
printf("the position of feijiaotu are:\n");
quit_num=0;
k=0;
i=0;
while(quit_num<15)
{if(*(p+i)!=0)k++;
if(k==9)
{printf("%5d",*(p+i));
quit_num++;
*(p+i)=0;
k=0;
}
i++;
if(i==30)i=0;
}
printf("\nthe position of jiaotu are:\n");
for(i=0;i<30;i++)
if(*(p+i)!=0)printf("%5d",*(p+i));
}

来源http://zhidao.baidu.com/question/42805958.html?si=5

Answer 3

这个算法应该比较经典，等高手解答。
我的想法的是，两数列不断交替筛选。

Answer 4

数组就可以解决了