第k人-白红宇

第k人

阅读量：2038 次

发布时间：2019-04-28

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

题解：经典的约瑟夫环问题

详细信息参考

C++版本一

/**@Author:   STZG*@Language: C++*/#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   //#define DEBUGusing namespace std;typedef long long ll;const int N=10000;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,m;int yuesefu(int n,int m){ if(n == 1){ return 0; //这里返回下标,从0开始，只有一个元素就是剩余的元素0 } else{ return (yuesefu(n-1,m) + m) % n; //我们传入的n是总共多少个数 }}int main(){#ifdef DEBUG freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout);#endif scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); cout<
                   
                    <

C++版本二

题解：

用数组模拟当前还在圈内的人的编号。

记录下次要报1 的人在当前圈内的下标x,(x+k-1)%n 就是下次要出圈的人的下标，然后把这个数从数组中删除，最后剩下的人就是答案。

#include
   
    using namespace std;const int N = 1005;int num[N];int main(){//    freopen("data.in","r",stdin);//    freopen("check1.out","w",stdout);    int T;    cin >>T;    while(T--){        int n,k;        scanf("%d %d",&n,&k);        for(int i = 0;i < n;i ++) num[i] = i;        int now = 0;        while(n>1){            now += k-1;            now %= n;            for(int i = now;i < n-1;i ++){                num[i] = num[i+1];            }            n--;        }        printf("%d\n",num[0]+1);    }    return 0;}

C++版本三

#include
   
    using namespace std;typedef long long ll;const int N=1e5+5;const int MOD=1e9+7;vector
    
      t;int main(void){//    freopen("data.in","r",stdin);//    freopen("check1.out","w",stdout);    int T;    cin >> T;    while(T--){        int n,k;        cin >> n >> k;        t.clear();        for(int i=1;i<=n;i++)   t.push_back(i);        int st=0;        while((int)t.size()>1){            int id=(st+k-1)%((int)t.size());//            cout <
     
      <<" "<
      
       <

C++版本四

#include
   
    using namespace std;const int N = 1005;int num[N], r[N], l[N];int main(){//    freopen("data.in","r",stdin);//    freopen("check1.out","w",stdout);    int T;    scanf("%d", &T);    while(T--){        int n,k;        scanf("%d%d",&n,&k);        for(int i = 0;i < n;i ++) num[i] = i + 1, r[i] = i + 1, l[i] = i - 1;        r[n - 1] = 0, l[0] = n - 1;        int now = 0, up;        while(n > 1){            up = k % n;            if(!up) up = n;            n--;            for(int i = 1; i < up; ++i)  now = r[now];            r[l[now]] = r[now];            l[r[now]] = l[now];            now = r[now];        }        printf("%d\n",num[now]);    }    return 0;}

转载地址：http://lyzof.baihongyu.com/

你可能感兴趣的文章