主要的约瑟夫环问题-白红宇

主要的约瑟夫环问题

阅读量：4635 次

发布时间：2019-06-09

本文共 1533 字，大约阅读时间需要 5 分钟。

n个人，编号为1~n。每次从1開始数，数到m的人出圈。最后一个出圈的人的编号。

f[1] = 0;for(int i = 2; i <= n; i++){    f[i] = ( f[i-1] + m)%i;}printf("%d\n",f[n]+1);

这里第一次出圈的人的编号是m，然后从1開始数，每次数到k的人出圈，问最后出圈的人的编号。

注意递推顺序

#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define _LL __int64#define eps 1e-12#define PI acos(-1.0)#define C 240#define S 20using namespace std;const int maxn = 100010;int main(){ int n,k,m; int f[10010]; while(~scanf("%d %d %d",&n,&k,&m)) { if(n == 0 && k == 0 && m == 0) break; int i; f[1] = 0; for(i = 2; i < n; i++) f[i] = (f[i-1]+k)%i; f[n] = (f[n-1]+m)%n; printf("%d\n",f[n]+1); } return 0;}

与上题类似，第一个出圈的是第一个人，之后出圈的是报数为m的人。求最小的m使得最后一个人的编号为2。

直接枚举m就可以，当求得最后一个人的编号为2时，m就是答案。

#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define _LL __int64#define eps 1e-12#define PI acos(-1.0)#define C 240#define S 20using namespace std;int f[155];int n;int solve(int m){ f[1] = 0; for(int i = 2; i < n; i++) f[i] = (f[i-1]+m)%i; f[n] = (f[n-1]+1)%n; if(f[n]+1 == 2) return true; return false;}int main(){ while(~scanf("%d",&n)&&n) { for(int m = 1; ; m++) { if(solve(m)) { printf("%d\n",m); break; } } } return 0;}