约瑟夫环问题小记

约瑟夫环问题小记

约瑟夫环是一个数学的应用问题，已知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;
}