约瑟夫环问题

2020-03-31

总阅读量次

问题描述

N个人在一起做游戏，他们制定了一下规则：
1、首先，所有参加游戏的人按顺序编号为1、2、3…N； 2、接下来每个人心里产生一个数字，这个数字称为序号为 N的人的密码P； 3、所有参加游戏的人按照编号站成一个圈，为游戏设置初始密码K，从编
号为 1的人这里开始报数，报到 K的人退出队伍，然后将自己心中的密码 K2说出
来，由下一个人继续从 1开始报数，报到 K2的人退出队伍，以此类推；
4、当只剩下一个人时，游戏结束。
在用户输入了人数N、每个人的密码P和初始
密码K的情况下，自动完成上面的游戏过程，输出先后离开队伍的人的序号序列，最后输出剩下的人的编号

采用数组实现

问题描述

输入：
人数N（规定最大人数为100）
每个人的密码key
初始密码K

输出：
先后离去的人的编号numNo
最后剩下的人的编号numNo

处理过程：
提示并存储用户输入的人的总数N
提示并存储用户输入的初始密码K
提示并存储用户输入的每一个人的密码key
遍历用户存储的人的密码的同时计数器自增
满足条件时进行相关操作，输出离开的人的编号
循环退出后输出最后剩下的人的编号
退出程序

流程设计

process

模块介绍

存储：
采用int类型的值存储人数N，初始密码K
采用结构体数组存储每个人的编号personNo、密码
personKey和未离开的人数personNum

实现：
循环遍历数组的每个元素，符合条件的元素输出，直
至数组中只有一个有效元素，再输出这个元素

源代码

#include <iostream>
#define NUM_MAX 100
using namespace std;

//用结构体数组存放参与游戏的人的信息
struct person{
    int personNo[NUM_MAX];
    int personKey[NUM_MAX];
    int personNum;
}person;

int main()
{
    int N,K,i = 0;
	//接受用户输入的人的数量
    cout << "please input the amount of people:" << endl;
    cin >> N;
    //判断用户输入是否合法
    if(N > 100 || N <= 0){
        cout << "please input the range of number is 1 to 100 !" << endl;
        return 0;
    }
	//根据用户输入的信息初始化结构体数组
    for(;i < N;i ++){
        cout << "please input the " << i + 1 << " person's key:" << endl;
        cin >> person.personKey[i];

        person.personNo[i] = i + 1;

    }

    person.personNum = N;
	//接受用户输入的初始密码
    cout << "please input the primitive key:" << endl;
    cin >> K;

    int counts = 1;
    i = 0;

	//剩下一人时退出循环
    while(person.personNum != 1){
    //报的号码与密码一致并且这个人还未退出游戏时，此人离开游戏，密码为此人密码，标志置零。人数自减一，从1开始报数
        if(counts == K && person.personNo[i] != 0){
            cout << "the person's No left is: " << person.personNo[i] <<endl;
            K = person.personKey[i];
            person.personNo[i] = 0;
            person.personNum --;
            counts = 1;
        }
//报的号码与密码不一样并且此人还未退出游戏时，继续报数
        else if(person.personNo[i] != 0){
            counts ++;
        }
//控制报数循环进行
        i = (i + 1) % N;
    }

    i = 0;
//依据标志判断此人是否是最后剩下的人
    for(;i < N;i ++){
        if(person.personNo[i] != 0){
            cout << "Last one is: " << person.personNo[i] <<endl;
            break;
        }

    }

    return 0;
}

测试样例

1.personNum最小值：
test1

2.Illegal input：

test2
test3

3.用例1：

test4 ) test5

用例2：
test6

用例3：
test7

采用链表实现

由于篇幅的原因，此处只粘贴源代码读者可自行测试（笔者亲测可行，如果发现问题请在评论区指出或者私信笔者，笔者将感激不尽）

源代码

#include <iostream>
#include <malloc.h>

using namespace std;

//指针节点结构体数组
typedef struct linkNode{
    int personNo;
    int personKey;
    linkNode* next;
    linkNode* pre;
}node,*Link;

//创建双向的课循环的链表
Link createLink(int n){

    //h设置为链表的头指针，然后执行相应的初始化
    node* h = (node*)malloc(sizeof(node));
    h ->next = NULL;

    //创建链表时应该先创建一个始终指向链表末尾的指针，并且这个指针目前应该
    //指向头指针的,所以初始化的时候应该将头指针的地址赋值给末尾指针r
    node* r;
    r = h;

    for(int i = 0;i < n;i ++){
        //这里为新的节点申请内存空间
        node* n = (node*)malloc(sizeof(node));
        //给新的节点赋值
        n ->personNo = i + 1;
        //输入每个人的key
        cout << "please input the " << i + 1 << " person's key:" << endl;
        cin >> n ->personKey;
        //新的节点此时应该是链表的最后一个节点，所以它的next指针应该指向空
        n ->next = h ->next;
        //新节点的pre指针指向上一个元素
        n ->pre = r;
        //现在将尾指针的next指针指向这个新的节点，也就是将这两个节点连接起来
        r ->next = n;
        //最后，再将尾指针r指向这个新的节点
        r = n;

    }

    //双循环链表
    h->next->pre = r;


    //循环结束后，返回这个链表的头指针h即可
    return h;
}



int main()
{
      int N,K;

    cout << "please input the amount of people:" << endl;
    cin >> N;

    if(N <=0)
        cout << "your input is illegal！" << endl;

    Link L = createLink(N);


    cout << "please input the primitive key:" << endl;
    cin >> K;

    int counts = 1;

    node* t = L ->next;
    node * p = L ->next;

//剩余人数为1时退出循环
    while( N != 1){
        if(counts == K){
            if(p ->personNo == t ->personNo){
                t = p ->next;
            }


            cout << "the No of person's left: " << p->personNo << endl;
            K = p ->personKey;


            node* s = p;

            s ->pre ->next = s->next;
            s ->next ->pre = s->pre;
            //最后释放被删除节点的空间就行
            free(s);

            counts = 1;
            N --;
        }
        else
        counts ++;

        p = p ->next;
    }


    cout << "the last one:" << t ->personNo << endl;



    return 0;
}