3586 - 循环链表练习
有n只猴子，按顺时针方向围成一圈（开始时编号为1，2，……n），选大王。从第1号猴子开始报数1，2，3……，数到m号时该猴子退出到圈外，如此报数直到圈内只剩下一只猴子时，此猴便是大王。你的任务是从键盘读入n,m，程序判断输出最后的大王是几号？
Input
输入一行，n，m分别表示猴子数量和报的数
Output
输出选出的大王
Examples
Input
5 3
Output
4
Solution C
#include<stdio.h> #include<stdlib.h> typedef struct tagNODE { int num; int rec; struct tagNODE *next; }node,*linklist; void monkeylink(int n,linklist *head) { linklist temp,upd; int i; (*head)=(linklist)malloc(sizeof(node)); upd=(*head); for(i=1;i<=n;i++) { temp=(linklist)malloc(sizeof(node)); temp->num=i; temp->rec=1; upd->next=temp; temp->next=NULL; upd=temp; } temp->next=(*head)->next; } int cnt(linklist head, int m) { linklist temp; int i; temp=head; while(temp->next!=temp) { for(i=1;i<=m-1;i++) temp=temp->next; temp->next=temp->next->next; } return temp->num; } int main() { int n,m; linklist monkey,head; scanf("%d%d",&n,&m); monkeylink(n,&head); printf("%d",cnt(head,m)); return 0; }
Solution C++
#include <iostream> using namespace std; int main() { int m, n; scanf("%d %d", &n, &m); int index = 0; for (int i = 2; i <= n; ++i) index = (index + m) % i; printf("%d\n", index + 1); return 0; }