Joseph Problem

阅读量：5015 次

发布时间：2019-06-12

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

前言

　　这几天学习了队列，于是尝试了一下Joseph Problem，然后一直有一个地方没有通过，终于经点拨后，通过了。对于队列的使用还是加深了印象。建议如果队列的练手可以去尝试解决这个问题。

正文

Joseph Problem（35分）

铺垫：

假设有N个人围成一圈，然后第一个人把第二个人杀了，刀子给第三个人，第三个人把第四个人杀了，以此类推......

首先注意：难点1：围成一圈，我们会想用什么数据结构呢？这么多人，首先应该想到用数组对不对，可是怎么表示围成一圈呢？重点来了，其实我们可以不断的把前面的挪到后面不就相当于围成了圈吗？对不对？

难点二：前一个人把后一个杀了?普通的应该会想把这个被杀的人的元素去掉，然后前一个元素往后面移，可是这样就达不到围成圆圈的效果了，重点来了，就是把这个杀人的人一开始也杀了，对！没看错，是把它也杀了，然后再把它放到放到数组的最某端就可以了。

好，难点讲诉完毕。

题目内容：

實作Joseph problem.

假設一開始有N個人，編號1~N，

按照順序以順時針圍成一個圓圈。

遊戲開始時，編號1的人拿刀。

之後每一輪刀子會被往下傳M個人，

而當輪最後拿到刀子的人會將他的下一個人殺掉，

殺完後刀子會再傳給被殺的下一個人。

這樣一輪就算結束。

遊戲會進行許多輪，直到只剩下最後一個人。

範例1：N=5, M=2

第一輪：刀子傳給3號，4號被殺，刀子再傳給5號 (1 2 3 5)

第二輪：刀子傳給2號，3號被殺，刀子再傳給5號 (1 2 5)

第三輪：刀子傳給2號，5號被殺，刀子再傳給1號 (1 2)

第四輪：刀子傳給1號，2號被殺，最後1號存活。

範例2：N=4, M=3

第一輪：刀子傳給4號，1號被殺，刀子再傳給2號 (2 3 4)

第二輪：刀子傳給2號，3號被殺，刀子再傳給4號 (2 4)

第三輪：刀子傳給2號，4號被殺，最後2號存活。

输入格式:

輸入第一行為一個數字T，代表測資的筆數。

接下來會有T筆測資，每一筆測資一行，

會有兩個數字N,M，數字間以空格區隔。

數字範圍：

T < 1000

0 < N <= 1000

0 < M <= 1000

输出格式：

輸出一行數字，將每筆測資最後存活下來的人的編號加總。

输入样例：

5 2

4 3

8 4

输出样例：

时间限制：1000ms内存限制：32000kb

大家先尝试解一下。再看文章比较好！

先理解题意：看第一个例子：刀子传两个人后到了第三个人，把第四个人杀了。加上又是圆圈，所以就相当与把两个人杀了挪到后面，然后就是成了前面的问题了对不对？好，开始写代码。

首先我们考虑杀人这个动作。

1 int Dequeue() {2     int z;//记录哪个人被杀，不然要是没有记录，怎么去把它挪到后面3     z = ch[Head];4     Head = (Head + 1) % 1000;//就是把Head指向后一人就可以了，相当于这一圆圈的人没有它了5     Number_of_Items--;//总人数减一6     return z;7 }

再考虑插到后面去这个动作：

1 void Enqueue(int x) { 2     if(Number_of_Items == 0) {//如果数组是空的，重新定义队列的头和尾 3         Tail = Head = 0; 4         ch[0] = x;//然后把它加进去 5     } else { 6         Tail = (Tail + 1) % 1000;//队尾指向后面一个，用于存储新的人 7         ch[Tail] = x; 8     } 9     Number_of_Items++;//总人数加一10 }

接下来就是总体的设计了

scanf("%d %d",&a,&b);//输入总人数和要传的人数 　　　　　for(int i=1; i <= a; i++)            Enqueue(i);//把这几人放到数组里面去        for(int i=1; i <= a-1; i++) {//每一轮杀一个人，总共要杀n-1个人            for(int k=0; k < b%Number_of_Items; k++) {                j = Dequeue();                Enqueue(j);            }//每次把b个人挪到后面            j = Dequeue();            Dequeue();            Enqueue(j);//就像铺垫所说的，杀两个人，再把第一个人放到数组后面去。        }

注意：

1.增加数组元素时，注意要考虑当数组为空。

for(int k=0; k < b%Number_of_Items; k++) {                j = Dequeue();                Enqueue(j);            }

注意这段代码，就是这个地方卡了我很久，看到没，当b非常大的时候，运行时间要的非常久，这里已经有3个for循环了，所以想法设法降低算法复杂度。于是发现可以对b进行优化，这是关键点。

3.每一次进行加入数组元素时，总人数记得加一，删除数组元素时，总人数记得减一。

好，接下来写出总代码：

#include
     
      int ch[1000];int Head,Tail,Number_of_Items; void Enqueue(int x) {    if(Number_of_Items == 0) {        Tail = Head = 0;        ch[0] = x;    } else {        Tail = (Tail + 1) % 1000;        ch[Tail] = x;    }    Number_of_Items++;} int Dequeue() {    int z;    z = ch[Head];    Head = (Head + 1) % 1000;    Number_of_Items--;    return z;} int main() {    int n,j,a,b;    int answer;    int sum = 0;    scanf("%d",&n);    for(int i=0; i < n; i++) {        scanf("%d %d",&a,&b);        ch[1000] = 0;//注意每一次对数组的更新        Number_of_Items=0;//对总人数的更新        Tail = Head = 0;        for(int i=1; i <= a; i++)            Enqueue(i);        for(int i=1; i <= a-1; i++) {            for(int k=0; k < b%Number_of_Items; k++) {                j = Dequeue();                Enqueue(j);            }            j = Dequeue();            Dequeue();            Enqueue(j);        }        sum += ch[Head];    }    printf("%d",sum);    return 0;}

注意：每次数组用完之后，都得进行更新赋值为0，并且对总人数也得更新。