1
Joseph Problem（35分）
题目内容：
實作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
#include <stdio.h> #include <stdlib.h> #define ERROR NULL typedef int ElementType; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; Position Find(List L, ElementType X); List Insert(List L, ElementType X, Position P); List Delete(List L, Position P); int main() { int N, n, m; int ans = 0; scanf_s("%d", &N); while (N--) { List L; L = NULL; scanf_s("%d %d", &n, &m); for (int i = n; i >=1; i--) { L = Insert(L, i, L); } PtrToLNode p, q, temp; p = L; while (p->Next) { //printf("%d ", p->Data); p = p->Next; } p->Next = L; q = L; while (q->Next != q) { for (int i = 1; i <=m; i++) { q = q->Next; } temp = q->Next; q->Next = temp->Next; free(temp); q = q->Next; } ans += q->Data; //printf("%d\n", q->Data); } printf("%d\n", ans); } List Insert(List L, ElementType X, Position P) { PtrToLNode Current; PtrToLNode p = (PtrToLNode)malloc(sizeof(struct LNode)); if (P == L) // 如果要插入的元素就是头节点 { p->Data = X; p->Next = L; L = p; return L; } Current = L; while (Current&&Current->Next != P) { Current = Current->Next; } if (Current == NULL) { printf("Wrong Position for Insertion\n"); return ERROR; } p->Data = X; p->Next = Current->Next; Current->Next = p; return L; } Position Find(List L, ElementType X) { PtrToLNode p = L; while (p) { if (p->Data == X) return p; p = p->Next; } return ERROR; } List Delete(List L, Position P) { PtrToLNode p = L; PtrToLNode temp; if (p == P) // 如果删除的是头节点 { L = L->Next; free(p); return L; } while (p&&p->Next != P) { p = p->Next; } if (p == NULL) // 如果找不到要删除的节点 { printf("Wrong Position for Deletion\n"); return ERROR; } temp = p->Next; p->Next = temp->Next; free(temp); return L; }
