华师一附中OI组

标题: 反约瑟夫问题 [打印本页]
作者: admin    时间: 2020-7-11 07:54
标题: 反约瑟夫问题
初始的约瑟夫问题是：m个人围成一个圈，从第一个人开始报数，报到n就出圈，下次不再参与报数，求最后一个出圈的人的编号k，假设m=8,n=5,那么k=3。
反约瑟夫是已知m和k，求最小的n。
类似的题目还有P1145 https://www.luogu.com.cn/problem/P1145
作者: admin    时间: 2020-7-11 07:58
约瑟夫问题我们讲过，我以前给你们的写法如下，注意体会每句话的意思：
  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    时间: 2020-7-11 08:03
现在我们不是要求输出出圈的顺序，只要求输出最后一个出去的人，要怎么改呢？
直接把地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    时间: 2020-7-11 08:12
现在我们是已知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.                 {

  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    时间: 2020-7-11 08:12
最终代码如下：
  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.                 {

  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    时间: 2020-7-11 08:15
用函数的思想包装一下，设一个函数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    时间: 2020-7-11 08:40
最后扩展思考：
1、是不是每个人都有可能成为最后一个出去的人？
2、若不限定n最小，可能有多个n满足条件，这些n之间有什么关系？



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2