密钥

【题目描述】密钥

输入正确的两个一元多项式的和后，上古文明遗迹的超合金门上忽然全息投影出了一圈围坐着的n只猴子以及一个整数m，据说这是设计者受猴子选大王问题的启发而设计的。这n只猴子按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数，报到m的猴子出局，再从刚出局猴子的下一个位置重新开始报数，如此重复，直至剩下一只猴子，它的编号就是密钥。

现设计编写一个基于链表的程序，实现如下功能：

（1）要求由用户输入开始时的猴子数n、报的最后一个数m。

（2）找出最后一只猴子的编号，即密钥。

【算法分析】

我们可以建立具有n个结点的循环单链表（链表尾指向链表头，形成一个环），表头结点为head，然后由指针q指向表头结点，开始循环，直到该链表中只有一个结点（q→next==q）为止。在循环过程中，由计数器count计数扫描过的结点个数，当count累加至m-1时，说明下一个结点便是要出队的结点，故删除该结点，这样，链表中的结点个数越来越少，直到只有一个结点，它的编号就是密钥。参考程序如下。