約瑟夫環問題小記

約瑟夫環問題小記

約瑟夫環是一個數學的應用問題，已知n個人（以編号1,2,3...n分别表示）圍坐在一張圓桌周圍。從編号為k的人開始報數，數到m的那個人出圈；他的下一個人又開始從1開始報數，數到m的那個人又出圈；依次規律重複下去，直到剩餘最後一個勝利者。

1）數組求解：

#include <stdio.h>
#include <stdlib.h>
#define N 1000000 //記錄玩遊戲最大人數
int flag[N] = {0};

int main(){
    int n = 0, m = 0;
    scanf("%d %d", &n, &m); //輸入玩遊戲人數和計數m
    int i = 0;
    int count = 0; //記錄已經出圈的人數
    int num = 0; //報數器
    for (i = 1; i <= n; i++) {
        flag[i] = 1; //所有人入局
    }
    while (count < n-1) {
        for (i = 1; i <= n; i++) {
            if (1 == flag[i]) {
                num++;
                if (num == m) {
                    printf("%d\n", i);
                    count++;  //出局人數+1;
                    flag[i] = 0; //标記出局狀态
                    num = 0;
                }
                if (count == n-1) {
                    break;
                }
            }
        }
    }
    for (i = 1; i <= n; i++) {
        if (1 == flag[i]) {
            printf("最終勝利者編号: %d\n", i);
        }
    }
    return 0;
}
           

2）循環連結清單求解：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int number; //資料域，存儲編号數值
    struct node *next; //指針域，指向下一個節點
}Node;

Node* createNode(int x) {
    Node *p;
    p = (Node*)malloc(sizeof(Node));
    p->number = x; //将連結清單節點的資料域指派為編号
    p->next = NULL;
    return p;
}

/*建立循環連結清單，存放整數1到n*/
Node* createJoseph(int n) {
    Node *head, *p, *q;
    int i;
    for(i = 1;  i <= n; i++) {
        p = createNode(i); //建立連結清單節點，并完成指派
        if (i == 1) //如果是頭結點
            head = p;
        else //不是頭結點，則指向下一個節點
            q->next = p;
            q = p;
    }
    q->next = head; //末尾節點指向頭結點，構成循環連結清單
    return head;
}

/*模拟運作約瑟夫環，每數到一個數，将它從環形連結清單中删除，并列印出來*/
void runJoseph(int n, int m) {
    Node *p, *q;
    p = createJoseph(n); //建立循環連結清單形式的約瑟夫環
    int i;
    while (p->next != p) { //循環條件，目前連結清單數目大于1
        for(i = 1; i < m-1; i++) { //開始計數
            p = p->next;
        }
        //第m個人出圈
        q = p->next;
        p->next = q->next;
        p = p->next;
        printf("%d--", q->number); //輸出出局的編号
        free(q);
    }
    printf("\n最終勝利者編号：%d\n", p->number);
}

/*主函數， n:總人數, m:第幾個出局*/
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    runJoseph(n, m);
    return 0;
}
           

3）遞歸求解：

#include <stdio.h>

int Joseph(int n, int m) {
    if (n <= 1 || m <= 1) //設定遊戲人數限定值
        return -1;

    if (n == 2) { //設定邊界值
        if (m % 2 == 0)
            return 1;
        else
            return 2;
    } else {
        return (Joseph(n-1, m) + m-1) % n+1;//遞歸調用
    }
}

int main() {
    int n, m, x;
    scanf("%d %d", &n, &m);
    x = Joseph(n, m);
    printf("最終勝利者編号：%d\n", x);
    return 0;
}
           

4）循環疊代求解：

#include <stdio.h>
/*計算約瑟夫環問題的疊代法函數*/
int Joseph(int n, int m) {
    int i;
    int x, y;
    if(n <= 1 || m <= 1)
        return -1;
    if (m % 2 == 0)
        y = 1;
    else
        y = 2;
    for (i = 3; i <= n; i++) {
        x = (y-1 + m) % i + 1;
        y = x;
    }
    return y;
}

int main() {
    int n, m, x;
    scanf("%d %d", &n, &m);
    x = Joseph(n, m);
    printf("最終勝利者編号：%d\n", x);
    return 0;
}