报数游戏

（1）：问题提出 设由n个人站成一个圈，分别编号1,2,3,4….n。从第一个人开始报数每次报数为m的人被从圈中推出，其后的人再次从1开始报数，重复上述过程， 直至所有人都从圈中退出。要求程序由用户输入整数m和n，求这n个人从圈中推出的先后顺序。 （2）：解决思路 可利用链表求解这个问题，先由n形成一个有n个表元组成的环，其中n个表元依次置值1~n。然后，从环的第一个表元出发，连续掠过m-1个表元，第m-1个表元的后继表元是第m个表元，将该表元从环中退出。接着再次从下一个表元出发，重复以上过程，直至环中表元都退出为止。 （三）：代码实现 ~~~ #include <stdio.h> #include <stdlib.h> /** * 设由n个人站成一个圈，分别编号1,2,3,4....n。从第一个人开始报数 * 每次报数为m的人被从圈中推出，其后的人再次从1开始报数，重复上述过程， * 直至所有人都从圈中退出。要求程序由用户输入整数m和n，求这n个人从圈中 * 推出的先后顺序。 * */ //定义一个循环链表 struct LinkedList{ int number; struct LinkedList *next; }; //输出链表 void print(struct LinkedList *ll){ struct LinkedList *current = ll; do{ printf("%d\t",current->number); current = current->next; } while(current != ll); printf("\n"); } int main() { int m,n; int i; printf("Please input the m and n(dividded by ','):\n"); scanf("%d,%d",&n,&m); struct LinkedList *pre = (struct LinkedList *)malloc(sizeof(struct LinkedList)); struct LinkedList *current = pre; current->number = 1; //分配内存并赋值 for(i = 2;i <= n;i++){ current->next = (struct LinkedList *)malloc(sizeof(struct LinkedList)); current = current->next; current->number = i; } current->next = pre; pre = current; while(n){ for(i = 1; i < m;i++) //忽略那些没用的 pre = pre->next; current = pre->next; printf("%d\t",current->number); //打印出相关信息 pre->next = current->next; //删除打印出的信息 free(current); n--; } return 0; } ~~~ （四）：相关知识 下面是我定义的一个关于循环链表的代码,大家可以看一下： ~~~ #include <stdio.h> #include <stdlib.h> //越界 #define OUT 0 //成功 #define SUCCESS 1 /** * 设由n个人站成一个圈，分别编号1,2,3,4....n。从第一个人开始报数 * 每次报数为m的人被从圈中推出，其后的人再次从1开始报数，重复上述过程， * 直至所有人都从圈中退出。要求程序由用户输入整数m和n，求这n个人从圈中 * 推出的先后顺序。 * */ //定义一个循环链表 struct LinkedList{ int number; struct LinkedList *next; }; //链表初始化 struct LinkedList * initLL(struct LinkedList *ll){ ll = (struct LinkedList *)malloc(sizeof(struct LinkedList)); ll->next = ll; return ll; } //判断循环链表是否为空 int isEmpty(struct LinkedList *ll){ return ll->next == ll ? 1 : 0; } //返回链表中元素的个数 int size(struct LinkedList *ll){ struct LinkedList *current = ll; int count = 0; while(current->next != ll){ current = current->next; count++; } return count; } //向链表中添加一个元素 void add(struct LinkedList *ll,int data){ struct LinkedList *temp = ll; while(temp->next != ll) temp = temp->next; struct LinkedList *llAdd = (struct LinkedList *)malloc(sizeof(struct LinkedList)); llAdd->number = data; temp->next = llAdd; llAdd->next = ll; } //向指定位置添加元素 //即在position之后添加一个元素 int insert(struct LinkedList *ll,int position,int data){ if(size(ll) < position) return OUT; int i = 0; struct LinkedList *temp = ll; for(i = 0;i < position;i++){ temp = temp->next; } struct LinkedList *llAdd = (struct LinkedList *)malloc(sizeof(struct LinkedList)); llAdd->number = data; llAdd->next = temp->next; temp->next = llAdd; return SUCCESS; } //删除指定位置的元素 int removeAt(struct LinkedList *ll,int position){ if(size(ll) < position) return OUT; struct LinkedList *current = ll; struct LinkedList *pre ; int i = 0; for(i = 0;i < position;i++){ pre = current; current = current->next; } //data = current->number; printf("%d\t",current->number); pre->next = current->next; free(current); return SUCCESS; } //输出链表 void print(struct LinkedList *ll){ struct LinkedList *current = ll->next; while(current != ll){ printf("%d\t",current->number); current = current->next; } printf("\n"); } ~~~ （五）：运行结果 下面是程序的运行结果: