報數遊戲

版權聲明：您好，轉載請留下本人部落格的位址，謝謝 https://blog.csdn.net/hongbochen1223/article/details/46762581

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

（五）：運作結果

下面是程式的運作結果: