问题：

　　n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。

　　例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。

　　给定n个人，请你编程计算出最后胜利者标号数。

输入：

　　第一行为人数n 

　　第二行为报数k

输出：

　　最后胜利者标号数

 

输入样例：

　　10

　　4

输出样例：

　　5

 

 

解法：

　　解法分为两种，一种是模拟，可以用循环链表，也可以用数组；另一种是通过递推得出公式。

 

一、模拟

　　链表模拟：

　　

1 #include 
     
       2 using namespace std; 3 typedef struct List{ 4     int data; 5     struct List *next; 6 }LinkList; 7 int main(){ 8     LinkList *L,*r,*s; 9     L = (LinkList *)malloc(sizeof(LinkList));10     r = L;11     int n,i,k;12     cin>>n>>k;13     for(i=1;i<=n;i++){14         s = (LinkList *)malloc(sizeof(LinkList));15         s->data = i;16         r->next = s;17         r=s;18     }19     r->next = L->next;//循环链表20     LinkList *p;21     p=L->next;22     while(p->next!=p){23         for(i=1;i
      
       next;//每k个数死一个人 25         }26         p->next=p->next->next;//将该节点从链表上删除27         p=p->next; 28     } 29     cout<
       
        data<
       
      
     

 

 

 

 

 

　　数组模拟：

 　　

1 #include 
     
       2 using namespace std; 3 int main(){ 4     int n,k,a[1001]; 5     cin>>n>>k; 6     int dead=0,num=0; 7     for(int i=1;i<=n;i++){ 8         a[i]=i; 9     } 10     for(int i=1;;i++){11         if(i>n)i=i%n;//如果大于总人数就从头开始 12         if(a[i]>0)num++;//如果当前这个人没有死，就报数 13         if(k==num&&dead!=n-1){14             num=0;15             a[i]=0;16             dead++;17         }else if(k==num&&dead==n-1){18             cout<
      
       <
      
     

 

 

二、递推

递推过程：

　　①第一个被删除的数为（m-1）%n;  

　　②设第二次的开始数字为k，

　　做下映射：（即将数字的排列计算还是从0开始）

　　k--->0

　　k+1--->1 

　　k+2--->2

　　---  ---

　　k-2--->n-2 

 

　　此时剩下n-1个人 ，假如我们已经知道了n-1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为(x+k)%n（要注意的是这里是按照映射后的序号进行的）

　　其中k=m%n。

　　代入 

　　（x+k）%n

　　<=>(x+(m%n))%n

　　<=>(x%n + (m%n)%n)%n

　　<=> (x%n+m%n)%n  

　　<=> (x+m)%n 

 

　　③第二个被删除的数为 （m-1）%n-1

　　④假设第三轮的开始数字为o，那这n-2个数构成的约瑟夫环为o,o+1,o+2,...,o-3,o-2。

　　映射 

　　o--->0 

　　o+1--->1  

　　o+2--->2

  　　---  ---  

　　o-2--->n-3  

　　这是一个n-2个人的问题。假设最后胜利者为y，那么n-1个人时，胜利者为(y+o)%(n-1)，其中o等于m%(n-1)。

　　代入可得(y+m)%(n-1)  

　　要得到n-1个人问题的解，只需要得到n-2个人问题的解，倒退下去。只有一个人时，胜利者就是编号0.小面给出递推式：

  　　f(1)=0;

  　　f(i)=(f[i-1]+m)%i;(i>1) 

这个公式的思想：

　　现在假设n=10

　　0 1 2 3  4 5 6 7 8 9 

　　k=3 

　　第一个人出列后的序列为：

 　　0 1 3 4 5 6 7 8 9 

　　即:  3 4 5 6 7 8 9 0 1（1式） 

 

　　我们把该式转化为: 0 1 2 3 4 5 6 7 8 (2式) 

 

　　则你会发现: （(2式)+3）%10 则转化为(1式)了 。

 

　　也就是说，我们求出9个人中第9次出环的编号，最后进行上面的转换就能得到10个人第10次出环的编号了。

　　设f(n,k,i)为n个人的环，报数为k，第i个人出环的编号，则f(10,3,10)是我们要的结果。

 

　　当i=1时，  f(n,k,i) = (n+k-1)%n

　　当i!=1时，  f(n,k,i)= ( f(n-1,k,i-1)+k )%n

 

 

1 #include
     
      2 int main(){3     int n, m,i,s=0;4     scanf("%d%d",&n,&m);5     for(i=2;i<=n;i++)6         s=(s+m)%i;7     printf("%d", s+1);8     return 0;9 }
     

 

 

说一下：

　　for(i=2;i<=n;i++)

　　        s=(s+m)%i;

 

　　这个式子：

　　首先从2开始，因为1个人的时候报的数字的人为0号，结果已经确定了。不需要从i=0开始，要注意的是序列从0开始编号的，所以最后的输出结果也要加1。

　　s表示的是上一轮的结果，m代表是每多少个人出列一次，i代表当前已经出列了多少个人。

　　整个式子就是根据上一个的出列数和已经出列的人数来算的。

 

 

 

转载请注明地址：

觉得有帮助的话可以点一下推荐，thanks