E12af14edd1f14a4b7f081ebf547885f
约瑟夫环求解

1 问题描述

  约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出圈;他的下一个人又从1开始报数,数到m的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。

  例如:有10个人围成一圈进行此游戏,每个人编号为1-10,。若规定数到3的人出圈。则游戏过程如下。

(1)开始报数,第一个数到3的人为3号,3号出圈。
  1, 2, [3], 4, 5, 6, 7, 8, 9, 10。
(2)从4号重新从1开始计数,则接下来数到3的人为6号,6号出圈。
  1, 2, [3], 4, 5, [6], 7, 8, 9, 10。
(3)从7号重新从1开始计数,则接下来数到3的人为9号,9号出圈。
  1, 2, [3], 4, 5, [6], 7, 8, [9], 10。
(4)从10号重新从1开始计数,由于10个人称环形结构,则接下来数到3的人为2号,2号出圈。
  1, [2][3], 4, 5, [6], 7, 8, [9], 10。
(5)从4号重新从1开始计数,则接下来数到3的人为7号,7号出圈。
  1, [2][3], 4, 5, [6][7], 8, [9], 10。
(6)从8号重新从1开始计数,则接下来数到3的人为1号,1号出圈。
  [1][2][3], 4, 5, [6][7], 8, [9], 10。
(7)从4号重新从1开始计数,则接下来数到3的人为8号,8号出圈。
  [1], [2], [3], 4, 5, [6], [7], [8], [9], 10。
(8)从10号重新从1开始计数,则接下来数到3的人为5号,5号出圈。
  [1], [2], [3], 4, [5], [6], [7], [8], [9], 10。
(9)从10号重新从1开始计数,则接下来数到3的人为10号,10号出圈。
  [1], [2], [3], 4, [5], [6], [7], [8], [9], [10]
(10)最终剩余4号,4号为胜利者。

2 数组求解

2.1 解题思想

  用数组求解的基本思想就是用一个一维数组去标识这n个人的状态,默认全为1,也就是都在圈子内,当数到m的人出圈之后,标识置为0(就是出圈了),同时报数器清0,下一个人要从1开始。在每次报数之前要判断他是否在圈子内(也就是他的标识是否为1),如果在圈子里面才会继续报数。定义一个变量记录出圈的人数, 出圈的人数等于 n-1时,则游戏结束。

2.2 代码实现

#include<stdio.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) {//此人数到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]) {//输出赢家,标识为1
            printf("The last one is : %d\n", i);
        }
    }

    return 0;
}

3 循环链表求解

3.1 解题思想

  约瑟夫环问题可以转化为循环链表的数据结构来求解。可以将每个人看做链表的单个节点,每个节点之间通过链表的next指针连接起来,并且将链表末尾节点指向头节点就形成的环,由链表构成的环形结构在数据结构中称为循环链表。

3.2 代码实现

```

include

include

/声明一个链表节点/
typedef struct node
{
int number;//数据域,存储编号数值
struct node *next;//指针域,指向下一个节点
}Node;

/创建链表节点的函数/
Node* CreatNode(int x)
{
Node p; p = (Node)malloc(sizeof(Node));
p->number = x;//将链表节点的数据域赋值为编号
p->next = NULL;
return p;
}

/创建环形链表,存放整数1到n/
Node* CreatJoseph(int n)
{
Node head,p,*q;
int i;
for(i = 1; i <= n; i++) { p = CreatNode(i);//创建链表节点,并完成赋值 if(i == 1)//如果是头结点 head = p; else//不是头结点,则指向下一个节点 q->next = p;
q = p;
}
q->next = head;//末尾节点指向头结点,构成循环链表

top Created with Sketch.