报数游戏

（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");
}

（五）：运行结果

下面是程序的运行结果:

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>

版权声明：本文为博主原创文章，未经博主允许不得转载。