1748:约瑟夫问题

by admin on 2020年1月5日

犹太人有这样的故事:罗马人占领乔塔帕特后,39个犹太人与约瑟夫及他的朋友躲到一个洞里,犹太人决定宁愿死也不要被敌人逮到,于是决定了一个自杀方式,41个人排成一个圈,由第1个人开始报数,每报数到第3个,该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。

超过五分钟才写出来,主要是最后怎么实现循环忘了i =
(++i)%n。而且和面向对象的思路搞混了

总时间限制: 1000ms 内存限制: 65536kB
描述
约瑟夫问题:有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

输入
每行是用空格分开的两个整数,第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是:

0 0

输出
对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0
样例输出
5
1
7

用循环队列求解约瑟夫问题:设有n个人站成一圈,其编号为1~n。从编号为1的人开始按顺时针方向1、2、……循环报数,数到m的人出列,然后从出列这的下一个人重新开始报数,数到m的人又出列,如此重复进行,直到n个人都出列为止。要求输出这n个人的出列顺序。并用相关数据进行测试。如何写?

/*
*给定正整数k(<14),n=2k个人分别分成前后两组,编号为1—k,
和k+1—n,要求计算最小的m,按约瑟夫规则,最先出局者为后面k个人;
*/

现在假设您不幸参与了这个游戏,共有N个人,如何让自己成为最后一个报数者,成功逃生。假设有41个人,您需要排在多少位才能逃生。

 1 //今天新写的 ,有些垃圾 
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int vis[100];
 7 
 8 int main()
 9 {
10     int i,j,k;
11     int m,n,s=0;
12     cin>>m>>n;
13     memset(vis,0,sizeof(vis));
14     
15     int cnt = 0;
16     int temp = 0;
17     int num = 0;
18     for(i=0; i<n; i = (++i)%n)
19     {
20         if(vis[i])
21             continue;
22         cnt++;
23         if(m==cnt)
24         {//在这用一个临时变量保存n的值,每次减一,当n是1的时候输出;不过这时候只能采用第二种输出方式了 
25             vis[i] = 1;
26             cnt = 0;
27         }
28         for(j=0; j<n; j++)
29             if(!vis[j])
30             {
31                 num++;
32                 temp = j;
33             }
34         if(1==num)
35             break;
36         else
37             num=0;
38         if(n==i)
39             i = 0;
40     
41     }
42 
43     for(i=0; i<n; i++)
44         if(!vis[i])
45             cout<<i<<endl;
46     cout<<temp<<endl;
47     while(1);
48     return 0;
49     
50 }

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int i,j,k;
 8     int m,n,s=0;
 9     cin>>m>>n;
10     for(i=2; i<=n; i++)
11         s=(s+m)%i;
12     int ans = s;
13     cout<<"胜者编号:"<<ans<<endl;//从0开始  
14     while(1);
15     return 0;
16 }

约瑟夫问题的递推公式是f[1]=0,f[i]=(f[i-1]+m)mod i。不过是一个“数据结构之指针和链表”里面的问题,所以还是先用链表和指针解决。因为要移除中间元素,所以需要一个双向链表,这里用一个数组来模拟:

 1 #include<stdio.h>
 2 int joseph(int k){
 3     int m,t,a=1,b,i,n;
 4     while(1){
 5         for(b=1;b<=k;b++){
 6             m=a*k+b,t=0,n=2*k;
 7             for(i=1;i<=k;i++){
 8                 t=(t+m-1)%n;
 9                 if(t<k)
10                     break;
11                 n--;
12             }
13             if(i>k)
14                 return m;
15         }
16         a+=2;
17     }
18     return 0;
19 }
20 int main(){
21     int k;
22     scanf("%d",&k);
23     printf("%d\n",joseph(k));
24     return 0;
25 }

代码如下:

 

1、构建结构和数组:

 

#include <stdio.h>
#define N 41       //也可以通过scanf函数赋值

int main()
{
    int j=0,k=0;
    int a[N];             //定义数组,并为每个人生命值赋为1
    for(int i=0;i<41;i++)
    {
        a[i]=1;
    }

    i=0;
    while(k<N-1)          //当自杀人数到N-1时退出
    {
        if(a[i]==1)
        {
            j++;
            if(j%3==0)    //报数为3的人自杀
            {
                a[i]=0;   
                k++;      //统计已经自杀的人数
            }
        }
        i++;
        if(i==N+1)
            i=0;
    }

    for(i=0;i<41;i++)    //找出最后一个人的位置
    {
        if(a[i]==1)
            printf("你应该站在第%d人的位置",i+1);
    }

    return 0;
}
 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int vis[310];
 5 
 6 void joseph(int n,int m)
 7 {
 8     int i,j,k;
 9     int cnt=0,count=0;
10     memset(vis,0,sizeof(vis));//0表示未选中
11     for(i=1;count<n-1;i=i%n+1)//循环 n-1次 
12     {
13         if(vis[i]==0)
14         {
15            // vis[i]=1;
16             cnt++;            
17         }
18         if(m==cnt)
19         {
20             vis[i]=1;//出圈 
21             cnt=0;
22             count++;
23         }
24     }
25     for(j=1;j<=n;j++)
26     if(vis[j]==0)
27     {
28         printf("%d\n",j);
29         break;
30     }
31 }   
32 
33 int main()
34 {
35 
36     int m,n;
37     while(scanf("%d%d",&n,&m),n||m)
38         joseph(n,m);
39     return 0;
40 }
struct node{
    int id;
    node *pre;
    node *next;
}lst[302];

 

2、初始化数组元素的id:

    for(m=1;m<=302;m++){
        lst[m].id=m;
    }

3、初始化数组元素的指针:

    for(i=1;i<=n;i++){
        lst[i].next=&lst[i+1];
        lst[i].pre=&lst[i-1];
    }
    lst[n].next=&lst[1];
    lst[1].pre=&lst[n];

4、查询需要删除的元素,直到当前元素和下一个元素都指向同一个元素:

    node *cur=&lst[1];
    while(cur->next!=cur){
        for(i=2;i<=m;i++){            
            cur=cur->next;
        }
        cur->pre->next=cur->next;
        cur->next->pre=cur->pre;
        cur=cur->next;
    }

此时,cur->id就是那个猴子王的初始编号。多组数据步骤2只需要进行一次,然后重复步骤3、4就可以了。但无论如何,这种方法的时间复杂度明显大于直接用数学方法进行求解,并且编码也多出很多。完整代码如下:

#include<iostream>
#include<cstring>
using namespace std;
struct node{
    int id;
    node *pre;
    node *next;
}lst[302];

int getking(int n,int m){
    int i;
    //1、设置前后指针
    for(i=1;i<=n;i++){
        lst[i].next=&lst[i+1];
        lst[i].pre=&lst[i-1];
    }
    lst[n].next=&lst[1];
    lst[1].pre=&lst[n];
    //2、查询
    node *cur=&lst[1];
    while(cur->next!=cur){
        //2.1、向后数到m
        for(i=2;i<=m;i++){            
            cur=cur->next;
        }
        //2.2、更新前后元素指针和当前数1的
        cur->pre->next=cur->next;
        cur->next->pre=cur->pre;
        cur=cur->next;
    }
    return cur->id;
}
int main(){
    int m,n;
    //初始化数组里的编号
    for(m=1;m<=302;m++){
        lst[m].id=m;
    }
    //获得输入并求解
    cin>>n>>m;
    while(m!=0 && n!=0){
        cout<<getking(n,m)<<endl;
        cin>>n>>m;
    }
}

然后,我们来考虑一下不模拟报数过程来求解,当一个人出局之后,剩下n-1人继续这个游戏,直到剩余1人。递推:1人时进行这个游戏,他不会出局的,两人呢?剩下的人是下次还能报数的那个,谁下次还能报数?同样,考虑3个人的情况,可以得出递推公式。核心代码如下:

    s=0;
    for(i=2;i<=n;i++){
       s=(s+m)%i;
    }
    cout<<s+1;

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图