反约瑟夫问题

admin

初始的约瑟夫问题是：m个人围成一个圈，从第一个人开始报数，报到n就出圈，下次不再参与报数，求最后一个出圈的人的编号k，假设m=8,n=5,那么k=3。
反约瑟夫是已知m和k，求最小的n。
类似的题目还有P1145 https://www.luogu.com.cn/problem/P1145

admin

约瑟夫问题我们讲过，我以前给你们的写法如下，注意体会每句话的意思：

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j,lst;
   
5. int main()
   
6. {
   
7.         int m=8,n=5;  
   
8.         for (i=1;i<=m;i++) a[i]=1;///初始都在圈内
   
9.         i=s=j=0;
   
10.         while (j<=m-1)
    
11.         {
    
12.                 i++;
    
13.                 if (i>m) i=1;///围圈
    
14.                 s=s+a[i];///报数
    
15.                 if (s==n) {
    
16.                         a[i]=0;//出圈
    
17.                         s=0;
    
18.                         cout<<i<' ';
    
19.                         j++;///+1
    
20.                 }
    
21.         }
    
22.         return 0;
    
23. }
    
24. /// m=8 n=5 k=3
    

复制代码

admin

现在我们不是要求输出出圈的顺序，只要求输出最后一个出去的人，要怎么改呢？
直接把地18行的cout<<i挪到renturn 0 的前面就行了吧！这个逻辑体会下。

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j;
   
5. int main()
   
6. {
   
7.         int m=8,n=5;
   
8.         for (i=1; i<=m; i++) a[i]=1; ///初始都在圈内
   
9.         i=s=j=0;
   
10.         while (j<=m-1)
    
11.                 {
    
12.                         i++;
    
13.                         if (i>m) i=1;///围圈
    
14.                         s=s+a[i];///报数
    
15.                         if (s==n)
    
16.                                 {
    
17.                                         a[i]=0;//出圈
    
18.                                         s=0;
    
19.                                         ///cout<<i<<' ';
    
20.                                         j++;///+1
    
21.                                 }
    
22.                 }
    
23.         cout<<i<<' ';
    
24.         return 0;
    
25. }
    
26. /// m=8 n=5 k=3
    

复制代码

admin

现在我们是已知m和k，求最小的n，是不是可以用穷举法，让n从1开始循环，依次求出k，当符合条件的时候，就不再做了。
那么第7行，就不是n=5，改成for（n=1;n<=m;n++）,第8到第23行都要被放在n的这个循环里面去。

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j;
   
5. int main()
   
6. {
   
7.         int m=8,n;
   
8.         for (n=1; n<=100; n++)
   
9.                 {
   
10. 
    
11.                         for (i=1; i<=m; i++) a[i]=1; ///初始都在圈内
    
12.                         i=s=j=0;
    
13.                         while (j<=m-1)
    
14.                                 {
    
15.                                         i++;
    
16.                                         if (i>m) i=1;///围圈
    
17.                                         s=s+a[i];///报数
    
18.                                         if (s==n)
    
19.                                                 {
    
20.                                                         a[i]=0;//出圈
    
21.                                                         s=0;
    
22.                                                         ///cout<<i<<' ';
    
23.                                                         j++;///+1
    
24.                                                 }
    
25.                                 }
    
26.                         cout<<i<<' ';
    
27.                 }
    
28.         return 0;
    
29. }
    
30. /// m=8 n=5 k=3
    

复制代码

现在是依次求出了n=1，2，3，4，5***100时最后一个出去的人，那么在cout<i的地方加一个判断，符合条件就不再做了就行，比较严密的的做法是类似质数判断，再设一个变量b，简单的做法是直接在那里break，但是记住break只能跳出一层循环，千万注意。

admin

最终代码如下：

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j;
   
5. int main()
   
6. {
   
7.         int m=8,n,k=3;
   
8.         bool b=1;
   
9.         for (n=1; n<=m& b==1; n++)
   
10.                 {
    
11. 
    
12.                         for (i=1; i<=m; i++) a[i]=1; ///初始都在圈内
    
13.                         i=s=j=0;
    
14.                         while (j<=m-1)
    
15.                                 {
    
16.                                         i++;
    
17.                                         if (i>m) i=1;///围圈
    
18.                                         s=s+a[i];///报数
    
19.                                         if (s==n)
    
20.                                                 {
    
21.                                                         a[i]=0;//出圈
    
22.                                                         s=0;
    
23.                                                         ///cout<<i<<' ';
    
24.                                                         j++;///+1
    
25.                                                 }
    
26.                                 }
    
27.                         if (i==k) b=0;
    
28.                 }
    
29.         cout<<n;
    
30.         return 0;
    
31. }
    
32. /// m=8 n=5 k=3
    

复制代码

admin

用函数的思想包装一下，设一个函数int ysf（m，n），表示输入m和n的时候求出k，那么程序就会变得更清晰易读：

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j;
   
5. int ysf(int m,int n)
   
6. {
   
7.         for (i=1; i<=m; i++) a[i]=1; ///初始都在圈内
   
8.         i=s=j=0;
   
9.         while (j<=m-1)
   
10.                 {
    
11.                         i++;
    
12.                         if (i>m) i=1;///围圈
    
13.                         s=s+a[i];///报数
    
14.                         if (s==n)
    
15.                                 {
    
16.                                         a[i]=0;//出圈
    
17.                                         s=0;
    
18.                                         ///cout<<i<<' ';
    
19.                                         j++;///+1
    
20.                                 }
    
21.                 }
    
22.         return i;
    
23. }
    
24. int main()
    
25. {
    
26.         int m=8,n,k=3;
    
27.         n=1;
    
28.         while (ysf(m,n)!=k) n++;
    
29.         cout<<n;
    
30.         return 0;
    
31. }
    
32. /// m=8 n=5 k=3
    

复制代码

admin

最后扩展思考：
1、是不是每个人都有可能成为最后一个出去的人？
2、若不限定n最小，可能有多个n满足条件，这些n之间有什么关系？