题目：
代码1(数组实现)：
//
// main.cpp
// DS-击鼓传花
//
// Created by wasdns on 16/11/9.
// Copyright © 2016年 wasdns. All rights reserved.
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <string>
using namespace std;int killman[1000]; //killer and alive manint main()
{
int n, m; cin >> n >> m; memset(killman, 0, sizeof(killman)); int killt = 1; //死亡情况，如果killt=总人数，结束游戏
killman[1] = -1; //第一位发言差，根据题目要求首杀 int rcd = 1, turn = 1; //rcd记录存活者，turn为指针
int cnt = 0; //cnt计数器，一旦为m，杀掉此时指针指向者 while (1)
{
if (turn > n) { //指针越界
turn %= n;
} if (killman[turn] == -1) { //此时指向的人已经死亡
turn++; continue;
} cnt++; //指向的人还活着，更新计数器 if (cnt == m) { //计数器计数为m，同时指针指向的人还活着
killman[turn] = -1; //杀死 killt++; //总死亡人数加一 rcd = turn; //rcd记录截止目前最后一位阵亡的同学 cnt = 0; //计数器置0 if (killt == n) break; //游戏结束
} turn++; //游戏还没有结束，指针后移
} cout << rcd << endl; //最后一位同学假死，存活 return 0;
}结果：
代码2(指针实现)：
//
// main2.cpp
// DS-击鼓传花
//
// Created by wasdns on 16/11/9.
// Copyright © 2016年 wasdns. All rights reserved.
//#include <cstdio>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;struct killman {
int num;
killman *next;
};/*
建立循环链表：
*/killman* CreatCircle(int n) { killman *k; k = new killman;
k -> next = NULL;
k -> num = 1; killman *p1, *p2; p1 = p2 = k; for (int i = 2; i <= n; i++)
{
p1 = new killman; p1 -> next = NULL;
p1 -> num = i; p2 -> next = p1;
p2 = p1;
} p1 -> next = k; return k;
}/*
根据题目要求，找到开始节点的前一个节点。
目的是为了删除第一个节点。
*/killman* FindKpre(killman *k)
{
killman *p;
p = k; while (p -> next != k) {
p = p -> next;
} return p;
}/*
杀人游戏主体：
*/int killgame(killman *k, int m)
{
int cnt = m; //计数器cnt，根据题目要求，初始置m killman *p1, *p2; //p1 为指向当前节点的指针；
//p2 为指向前一个节点的指针。
p1 = k;
p2 = FindKpre(k); //找到开始节点的前一个节点，进行删除操作 while (1)
{
if (cnt == m) { //计数器达到阈值时，删除当前节点 p1 = p1 -> next;
p2 -> next = p1; cnt = 1; //注意：删除之后，本质上进行了前移；
//计数器置1.
continue;
} if (p2 -> next == p2) break; //当出现回环(loop)的时候：
//说明只剩下当前节点，游戏结束。 cnt++; //计数器尚未溢出，指针前移，更新计数器。 p2 -> next = p1;
p2 = p1; p1 = p1 -> next;
} return p1 -> num; //返回游戏的赢家
}/*
Debug，输出环形链表：
*/void KPrint(killman *k) { killman *p;
p = k -> next; while (p != k) {
cout << "p " << p -> num << endl;
p = p -> next;
}}int main()
{
int n, m; cin >> n >> m; killman *k; k = CreatCircle(n); //KPrint(k); int rcd = 1; rcd = killgame(k, m); cout << rcd << endl; return 0;
}结果：
小结：
此题是经典的约瑟夫问题，采用ADT表，有两种实现方法：(1)指针实现 (2)数组实现。
需要注意的点是：
- 题目把第一个人直接出局
- 计数器和指针更新时的位置(更新指针之后马上更新计数器！)
- 循环结束条件
可以看到，使用环形链表的性能更优，但是实现相比数组而言更加复杂。
2016/11/9
