Question

一道面试智力题，跪求答案

船上有N个人，船被海盗劫了，海盗给出一个数字K，让所有人站一排并逐个报数，报到K的被扔下海，然后下一位从1开始报数，报到K的再被扔下海，如此反复直到所有人都被扔下海。求被扔下海的人的序列。
例如：N＝3， K＝5 序列是231。
不能用数组或队列等数据结构，要用公式求解。

Answer 1

什么是约瑟夫问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该 人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。
通俗讲解：智取奖品问题：
许多人围成一个圈报数，报到一个特定的数的人退出，一支循环下去。
约瑟夫就是猴子选大王，猴子报数，最后选出大王。

求解约瑟夫问题递归算法（c语言版）

（1）建立具有几个结点的单循环链表，其数据域值为生成结点时的顺序号。
（2）用计数扫描过的结点，当j=m-1时，说明其直接后继结点就是出列结点，先输出其获数据域值，再删除该结点，再从被删结点的下一个结点重新开始计数。如此重复上述步骤，直到仅剩最后一个结点，再将该结点出列。
例如：
#include <stdio.h>
typedef struct node {
int data;
struct node *next;}Lnode;
Lnode *create(int n){
int i;
Lnode *h,*p,*r=(Lnode*)malloc(sizeof(Lnode);
r->data=n;h=r;
for(i=n-1;i>0;i--){
p=(Lnode *)malloc(sizeof(Lnode));
p->data=i;
h=p;}
r->next=h;
return h;
}

void jeseph(Lnode *p,int m){
Lnode *q; int j=0;
printf("outqueue order:");
do{
j++;
if (j==m-1){
q=p->next;
p->next=q->next;
printf("%d",q->data);
j=0;free(q);}
while(p->next!=p);
printf（“%d\n",p->data);
free(p);
}
void main()
{Lnode *h ;
int m,n;
printf ("\n input n,m=");
scanf("%d,%d",&n,&m);
h=create(n);
jeseph(h,m);
}

Answer 2

我等着看答案呢。没有看到公式。

Answer 3

一种数列问题

Answer 4

29秒
A、B过去：3秒
A回来：1秒
D、E过去：12秒
B回来：3秒
A、C过去：6秒
A回来：1秒
A、B过去：3秒