這幾天學習了隊列，於是嘗試了一下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
輸出格式：
輸出一行數字，將每筆測資最後存活下來的人的編號加總。
輸入樣例：
3
5 2
4 3
8 4
輸出樣例：
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.增加數組元素時，注意要考慮當數組為空。
2.
for(int k=0; k < b%Number_of_Items; k++) {
j = Dequeue();
Enqueue(j);
}
注意這段代碼，就是這個地方卡了我很久，看到沒，當b非常大的時候，運行時間要的非常久，這裡已經有3個for循環了，所以想法設法降低算法復雜度。於是發現可以對b進行優化，這是關鍵點。
3.每一次進行加入數組元素時，總人數記得加一，刪除數組元素時，總人數記得減一。
好，接下來寫出總代碼：
#include<stdio.h>
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，並且對總人數也得更新。
這題卡到的地方主要是如何降低算法復雜度，對其中一些變量進行優化。我也是經別人點撥才明白了這裡的優化，還得多多學習。
2016-03-06 14:14:02
