排队 约瑟夫环_约瑟夫小游戏下船java语言怎么停下来

最后幸存的那位的原来的号码

方法一、二模拟了整个游戏过程最后得到结果，费时又费力

方法三：如果将问题更改为：

m个人编号为（0~(m-1)) 从0 报数，报数为(x-1)的人退出，然后继续； 知道只剩下一个人；

如果从x%m重新编号

假设s是子问题的解，那么s'=(s+x)%m;       //(s+x)得到它原来的编号

从而可以用递推的方式求解

递推公式为：

f[1]=0;

f[i]=(f[i-1]+x)%i;

用循环列表实现：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
       int num;
       struct node *next;
}Node;
 
int main()
{
       int n,m,x;
       int i,j;
       scanf("%d",&n);
       while(n--)
       {
              scanf("%d%d",&m,&x);
			  if(x==1)
				  printf("%d\n",m);
              else{
			  Node *head,*p,*tail,*ptr;
              head=(Node *)malloc(sizeof(Node));    //头链表
              head->num=1;
              head->next=head;
              tail=head;
 
 
              for(i=2;i<=m;i++)
              {
                     p=(Node *)malloc(sizeof(Node)); //建立循环链表
                     p->num=i;
                     p->next=head;
                     tail->next=p;
                     tail=p;
              }
 
 
			  
			  i=1;
			  p=head;
			  
			  while(p->next!=p){    //寻找x节点，并删除
				  i++;
				  ptr=p->next;
				  if(i==x){
					  p->next=ptr->next;
					  free(ptr);
					  i=1;
				  }
				  
				  p=p->next;
				  
			  }
			  
			  printf("%d\n",p->num);
			  }
 
       }
       return 0;
 
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define maxn 1000
int a[maxn];
int main(void){
	int n,m,x;
	int count;
	scanf("%d",&n);
	while(n--){
		memset(a,0,sizeof(a));      //用0表示未退出，1表示退出
		int i,j=0;
		scanf("%d%d",&m,&x);
		int k=m;
		for(i=k;i>1;i--){
			count=1;
	
		while(1){
			if(a[j%k]!=1){
				if(count==x){
					a[j%k]=1;  //编号为j%k的退出
					
					break;
				}
				else
					count++;
			}
				j++;
			}
		}
		for(i=0;i<m;i++){
			if(!a[i])          //寻找唯一一个0；
				printf("%d\n",i+1);
		}
 
		
	}
	return 0;
}

用递归实现：

#include <stdio.h>
 #include<stdlib.h>
  int main()
  {
     int m,x,i,s,n;
     scanf("%d",&n);
     while(n--)
     {
        while(scanf("%d%d",&m,&x))
        {   s=0;
            for (i=2;i<=m;i++) s=(s+x)%i;
           printf ("%d\n", s+1);
        }
     }
 
     return 0;
 }