华师一附中OI组

标题: 约瑟夫问题 [打印本页]

---

作者: admin    时间: 2019-1-1 12:00
标题: 约瑟夫问题
约瑟夫问题和斐波那契数列一样也是数学界的经典问题，里面有很多的数学原理和算法实现。
基本的约瑟夫问题是：有8个人围成一圈，编号分别为1-8，那么第8个人后面是第1个人。从第1个人开始，依次报数，报到5的那个人就出圈，下面的人又从1开始报数，同样报到5就出圈，请问出圈的顺序。

---

作者: admin    时间: 2019-1-1 12:04

最直观的做法是模拟大法：用整数数组a(10)表示a(1)-a(8)八个人，若此人还在圈内设a(i)=1；若是已经出去了，则a(i)=0，这是一般的通用表示方法。这样当a(i)=1时候，s=s+a(i)就相当于s+1，报了下一个数，当a(i)=0时候，s=s+a(i)就不变，相当于第i个人出去了没有报数。实际上人还在只是没有参与统计。
用s表示现在报道了几，那么s==5的时候这个人要出去，下一个人要从0开始报。
每人报数完了之后下一个人接着报，i=i+1，但是第8个人之后接着的是第1个，所以if (i>8) i=1;
用k表示出圈的人的个数，那么对于此题应该是k<=7就做，第8个人出去后就不玩了。所以主程序可以写 while(k<=7)
循环初值些i=s=k=0 ；这个要体会一下。

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=10;
   
4. int a[mm];
   
5. int i,k,s; ///i表示人的编号 s表示人的报数 k表示出去了几个人
   
6. 
   
7. int main()
   
8. {
   
9.     for (i=1; i<=8; i++) a[i]=1; ///起始都是1
   
10.     i=k=s=0;
    
11.     while (k<=7)
    
12.     {
    
13.         i++;if (i>8) i=1;  ///第8个人后面是第1个
    
14.         s=s+a[i];
    
15.         if (s==5) {k++;///出去了一个
    
16.         a[i]=0; ///再不统计
    
17.         cout<<i<<' ';
    
18.         s=0;///下面又重新开始
    
19.         }
    
20.     }
    
21.     return 0;
    
22. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2