[数据结构与算法] 数据结构与算法实验题1 Josephus环问题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构与算法实验题1 Josephus环问题 -> 正文阅读

[数据结构与算法]数据结构与算法实验题1 Josephus环问题

1.问题描述

设编号为1,2, ……,n的n 个人按顺时针方向围坐一圈，约定编号为k (1≤k≤n) 的人按顺时针方向从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。试设计算法求出n个人的出列顺序。

2.基本要求

程序运行时，首先要求用户指定人数n,第一个开始报数的人的编号k及报数上限值m。然后，按照出列的顺序打印出相应的编号序列。

3.提示与分析

1)由于报到m的人出列的动作对应着数据元素的删除操作，而且这种删除操作比较频繁，因此单向循环链表适于作为存储结构来模拟此过程。而且，为了保证程序指针每一次都指向一个具体的数据元素结点，应使用不带头结点循环链表作为存储结构。相应地，需要注意空表和非空表的区别。

2)思路:创建一个含有n个结点的单循环链表，然后由第一个结点起从1开始计数(此时假设k-1)，计到m时，对应结点从链表中删除，接下来从被删除结点的下一个结点重新开始从1开始计数，计到m时，从链表中删除对应结点，如此循环，直至最后一个结点从链表中删除，算法结束。

4.选作内容

1) 在顺序结构上实现本算法。需要考虑如何实现循环的顺序结构。
2) m不再固定。假设n个人每人持有一个密码(正整数)，从编号为k的人开始从1开始顺序报数，报到m的人出列，此时将他的密码作为新的m值，从他顺时针方向上的下一个人开始重新从1报数，报到m的人出列，而后将他的密码作为新的值，如此循环下去，直到所有人全部出列为止。
3)显示仿真的运行界面。（这个完全不会，等会了再写）

代码1（单循环链表实现，无头结点）：

#include<iostream>

using namespace std;

typedef struct List {
	int num;
	struct List* next;
}Node;

List* creatList() {
	List* newList = (List*)malloc(sizeof(struct List));
	newList->next = newList;
	newList->num = 1;

	return newList;
}

void push_back(List* list, int num) {
	Node* curNode = list;

	List* newNode = (List*)malloc(sizeof(struct List));
	newNode->num = num;

	while (curNode->next != list) {
		curNode = curNode->next;
	}

	curNode->next = newNode;
	newNode->next = list;
	
}

//这个print函数我是用来检验链表的数据是否正确插入的
void print(List* list) {   
	Node* curNode = list->next;

	while (curNode != list) {
		printf("%d ", curNode->num);
		curNode = curNode->next;
	}
	putchar('\n');
}


void j_find(List* list,int m,int k,int n) {
	//从编号为k的人开始
	//数到m的人出列

	Node* preNode = list;
	Node* curNode = list->next;

	while (curNode->num != k) {
		preNode = preNode->next;
		curNode = curNode->next;
	}

	while (n) {
		
		for (int i = 0; i < m-1 ; i++) {
			preNode = preNode->next;
			curNode = curNode->next;
		}

		printf("%d ", curNode->num);
		n--;
		preNode->next = curNode->next;
		curNode = curNode->next;
	}
}

int main() {
	List* newList = creatList();

	int n, k, m;
    cout << "请输入n,m,k:";
	cin >> n >> k >> m;
    if (n < 0 || k < 0 || m<0 || k>n) {
		cout << "你输入的数据有误！";
		return 0;
	}
    
	for (int i = 2; i <= n; i++) {
		push_back(newList,i);
	}
//	print(newList);
	j_find(newList, m, k,n);
}

分析：

首先是单循环链表的定义，和普通链表没啥区别：

typedef struct List {
	int num;    
	struct List* next;
}Node;

然后是创建一个新的链表，因为是没有头结点的，所以我在创建的时候就把创建的这个结点中的值定为了1。n的值肯定是大于等于1的嘛。

List* creatList() {
	List* newList = (List*)malloc(sizeof(struct List));
	newList->next = newList;
	newList->num = 1;

	return newList;
}

尾插法：

void push_back(List* list, int num) {
	Node* curNode = list;

	List* newNode = (List*)malloc(sizeof(struct List));
	newNode->num = num;

	while (curNode->next != list) {  //找到链表尾
		curNode = curNode->next;
	}

	curNode->next = newNode;
	newNode->next = list;
	
}

最关键的是这个函数：

我的思路是先定义两个指针，用于删除操作；然后找到我们开始的位置k；然后有n个人，所以我们要输出n次，用n来控制while循环的次数；while循环内首先进行移动，即开始报数，最后curNode指针指向的结点就是我们要删除的节点。

void j_find(List* list,int m,int k,int n) {
	//从编号为k的人开始
	//数到m的人出列

	Node* preNode = list;        //用于删除操作
	Node* curNode = list->next;

	while (curNode->num != k) {  //找到开始的位置k
		preNode = preNode->next;
		curNode = curNode->next;
	}

	while (n) {
		
		for (int i = 0; i < m-1 ; i++) {  //开始报数
			preNode = preNode->next;
			curNode = curNode->next;
		}

		printf("%d ", curNode->num);
		n--;
		preNode->next = curNode->next;
		curNode = curNode->next;
	}
}

代码2（单循环链表实现，有头结点）：

#include<iostream>

using namespace std;

typedef struct List {
	int num;
	struct List* next;
}Node;

List* creatList() {
	List* newList = (List*)malloc(sizeof(struct List));
	newList->next = newList;

	return newList;
}

void push_back(List* list, int num) {
	Node* curNode = list;

	List* newNode = (List*)malloc(sizeof(struct List));
	newNode->num = num;

	while (curNode->next != list) {
		curNode = curNode->next;
	}

	curNode->next = newNode;
	newNode->next = list;
	
}

void print(List* list) {
	Node* curNode = list->next;

	while (curNode != list) {
		printf("%d ", curNode->num);
		curNode = curNode->next;
	}
	putchar('\n');
}


void j_find(List* list,int m,int k) {
	//从编号为k的人开始
	//数到m的人出列


	Node* preNode = list;
	Node* curNode = list->next;

	while (curNode->num != k) {
		preNode = preNode->next;
		curNode = curNode->next;
	}

	while (list->next!=list) {
		
		for (int i = 0; i < m-1 ; i++) {
			if (curNode->next != list) {
				preNode = preNode->next;
				curNode = curNode->next;
			}
			else {
				preNode = preNode->next->next;
				curNode = curNode->next->next;
			}
		}

		printf("%d ", curNode->num);
		preNode->next = curNode->next;
		curNode = curNode->next;
	}
}

int main() {
	List* newList = creatList();

	int n, k, m;
	cout << "请输入n,m,k:";
	cin >> n >> k >> m;
    if (n < 0 || k < 0 || m<0 || k>n) {
		cout << "你输入的数据有误！";
		return 0;
	}
    
	for (int i = 1; i <= n; i++) {
		push_back(newList,i);
	}
	//print(newList);
	j_find(newList, m, k);
}

有头结点与无头结点的不同之处在于以下几个方面：

1.创建链表，就是普通的创建链表，不再给头结点数据：

List* creatList() {
	List* newList = (List*)malloc(sizeof(struct List));
	newList->next = newList;

	return newList;
}

2.在输入数据方面，无头结点的话i是从2开始，有头结点是从1开始

for (int i = 1; i <= n; i++) {
	push_back(newList,i);
}

3.在核心函数这里，少了一个参数n，因为while的循环条件可以变为list->next!=list；然后在for循环也就是报数这里，有一种情况是curNode指针可能会移动到头结点这里，但是头结点没有数据，不能删除，所以当我们将要移动时，判断一下，如果curNode将要移动到头结点，那么我们移动两步。

void j_find(List* list,int m,int k) {
	//从编号为k的人开始
	//数到m的人出列

	Node* preNode = list;
	Node* curNode = list->next;

	while (curNode->num != k) {
		preNode = preNode->next;
		curNode = curNode->next;
	}

	while (list->next!=list) {
		
		for (int i = 0; i < m-1 ; i++) {  //报数
			if (curNode->next != list) {
				preNode = preNode->next;
				curNode = curNode->next;
			}
			else {
				preNode = preNode->next->next;
				curNode = curNode->next->next;
			}
		}

		printf("%d ", curNode->num);
		preNode->next = curNode->next;
		curNode = curNode->next;
	}
}

9.28更新：昨天晚上我想了一个小时没想出来，今天想出来了

选做内容1：

?在顺序结构上实现本算法。需要考虑如何实现循环的顺序结构。

因为书上的循环队列那里，用的%解决的队列的假溢出，所以在这里我也想用%来解决这个问题。

我一开始的思路是输入n个数，然后找出来要输出的数，然后把他输出，然后删除他，删除后移动数组，也就是数组长度减一。但是后来在实现方面发现了很多问题。因为在删除后，进行数组的移动时，数组的下标也会变化，数组长度变化后，我们%的数也要变化，这样给我造成了很大的困难。

所以我想到的解决办法是用一个符号（-1）来标记已经输出的数，下次再遇到这个数就跳过：

代码3：

#include<iostream>
#define MAX 1000  //数组容量 
using namespace std;

int a[MAX];

int main() {
	int n, m, k;
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		a[i] = i;
	}
	a[0] = n;   //保存人数 

	int temp = k, next, flag;   //temp是指向当前节点，next指向当前节点的下一节点 

	while (a[0]) {
		flag = m - 1;     //我们要从当前节点向前数m-1个人 ，控制下面的循环次数 
		while (flag) {
			next = (temp + 1) % (n + 1);   //获得next的值 
			if (next == 0) {
				next++;
			}
			if (a[next] == -1) {  //如果下一节点输出过，那么我们移动后并不算，因为下一节点已经“出去”了 
				temp = (temp + 1) % (n + 1);
				if (temp == 0) {
					temp++;
				}
			}
			else if (a[next] != -1) {     //如果下一节点的值没有输出过，那么我们指向下一节点 
				flag--;             //移动次数减一 
				temp = (temp + 1) % (n + 1);
				if (temp == 0) {
					temp++;
				}
			}

		}

		printf("%d ", a[temp]);   //输出 
		a[temp] = -1;             //将下一节点标记为-1，就是“出去”了 
		a[0]--;

		while (a[temp] == -1) {          //将指针移动到下一个开始的位置 
			temp = (temp + 1) % (n + 1);
		}
		if (temp == 0) {
			temp++;
		}

		if (a[0] == 1) {
			printf("%d ", a[temp]);
			a[0]--;
		}
	}
}

分析：

首先数组下标为0的地方我们保存数组长度，因为这样第一个人也就是a[1]，第二个人就是a[2],这样下标和人的编号是一致的，方便运算。

cin>>n>>m>>k;
	
for(int i=1;i<=n;i++){
	a[i]=i;
}
a[0]=n;   //保存人数

然后定义一个当前指针temp，用于输出，还有一个当前指针的下一个结点的指针next，用于判断下一结点的值是否输出过。

flag是用来控制我们数的数的次数，也就是我们输入的m

int temp=k,next,flag;   //temp是指向当前节点，next指向当前节点的下一节点

下面语句中flag要等于m-1是因为我们temp指向的结点在报数中就是1，所以我们后面再找m-1个人就行

while(a[0]){
	flag=m-1;     //我们要从当前节点向前数m-1个人 ，控制下面的循环次数

核心代码：

while (a[0]) {
flag = m - 1;     //我们要从当前节点向前数m-1个人 ，控制下面的循环次数 
while (flag) {
	next = (temp + 1) % (n + 1);   //获得next的值 
	if (next == 0) {
		next++;
	}

	if (a[next] == -1) {  //如果下一节点输出过，那么我们移动后并不算，因为下一节点已经“出去”了 
		temp = (temp + 1) % (n + 1);
		if (temp == 0) {
			temp++;
		}
	}
	else if (a[next] != -1) {     //如果下一节点的值没有输出过，那么我们指向下一节点 
		flag--;             //移动次数减一 
		temp = (temp + 1) % (n + 1);
		if (temp == 0) {
			temp++;
		}
	}

}

首先我们要获得下一个结点的值，下一个结点的值有三中可能：

1.没有被输出的数（值非-1的数）

2.被输出了的数（值为-1的数）

3.下标为0的结点，保存着数组长度

当下标为0时，是保存数组长度的地方，要跳过这里，所以：

if (next == 0) {
	next++;
}

然后是next指针和temp指针的移动：

next = (temp + 1) % (n + 1);   //获得next的值

if (a[next] == -1) {  //如果下一节点输出过，那么我们移动后并不算，因为下一节点已经“出去”了 
	temp = (temp + 1) % (n + 1);
	if (temp == 0) {
		temp++;
	}
}

next指针是试探下一个数，所以可以直接移动，但是temp指针是指向的是没有输出过的结点，所以要判断一下，如果是下一个结点是-1，那么就移动到和next指针一样的位置，但是不进行操作。

next指针接着向下试探，如果试探的结点没有输出过，那么temp指针就指向next针，并进行输出，并且报数总数flag减一，数组长度也要减一，把这个地方的值变成-1。

else if (a[next] != -1) {     //如果下一节点的值没有输出过，那么我们指向下一节点 
	flag--;             //移动次数减一 
	temp = (temp + 1) % (n + 1);
	if (temp == 0) {
		temp++;
	}
}
printf("%d ", a[temp]);   //输出 
a[temp] = -1;             //将下一节点标记为-1，就是“出去”了 
a[0]--;

做完这一次操作，我们就要寻找下一次报数的结点：

while (a[temp] == -1) {          //将指针移动到下一个开始的位置 
	temp = (temp + 1) % (n + 1);
}
if (temp == 0) {
	temp++;
}

最后，这段代码是处理数组中只剩一个数的情况。只剩最后一个数，我们直接输出就行。

如果不加这个判断的话，我们就会遍历这个数组两次。也能得出正确结果，就是会慢。

if (a[0] == 1) {
	printf("%d ", a[temp]);
	a[0]--;
}

总结：

其实这个方法在输出一半的数之后，会不断遍历数组，做很多无用功。（可能会有更好的方法，但是我只能想出这个笨办法，我想了总共得有4小时QAQ）?

还是链表好使

选做内容2：

m不再固定。假设n个人每人持有一个密码(正整数)，从编号为k的人开始从1开始顺序报数，报到m的人出列，此时将他的密码作为新的m值，从他顺时针方向上的下一个人开始重新从1报数，报到m的人出列，而后将他的密码作为新的值，如此循环下去，直到所有人全部出列为止。

代码4（固定的密码，每个人的编号就是他的密码）：

其实和代码1差不多，就是在结构体中多了一个密码code部分，在尾插中多赋值一下，然后在j_find函数的报数中，报数的循环次数用code的值代替就行。

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct List{
	int data,code;
	struct List* next;
}Node;

List* creatList(){
	List* newList=(List*)malloc(sizeof(struct List));
	newList->data=1;
	newList->code=1;
	newList->next=newList;
	
	return newList;
}

void push_back(List* list,int data){
	Node* curNode=list;
	
	while(curNode->next!=list){
		curNode=curNode->next;
	}
	
	Node* newNode=(List*)malloc(sizeof(struct List));
	newNode->data=data;
	newNode->code=data;
	
	curNode->next=newNode;
	newNode->next=list;
}

void print(List* list,int n){
	Node* curNode=list;
	while(n--){
		printf("%d %d ",curNode->data,curNode->code);
		curNode=curNode->next;
	}
	putchar('\n');
}

void j_find(List* list,int k,int n){
	Node* temp=list->next;
	Node* pre=list;
	
	while(temp->data!=k){
		pre=pre->next;
		temp=temp->next;
	}
	
	int code;
	while(n){
		code=temp->code;
		
		for(int i=0;i<code-1;i++){
			pre=pre->next;
		    temp=temp->next;
		}
		printf("%d ",temp->data);
		n--;
		pre->next=temp->next;
		temp=temp->next;
	}
}

int main(){
	int n,k;
	cin>>n>>k;
	
	List* newList=creatList();
	
	for(int i=2;i<=n;i++){
		push_back(newList,i);
	}
	//print(newList,n);
	
	j_find(newList,k,n);
}

代码5（可以自己定义每个人的密码）：

在代码4的基础上多加了一个getCode函数，进行code的输入。

#include<iostream>
#include<stdlib.h>
using namespace std;

typedef struct List{
	int data,code;
	struct List* next;
}Node;

List* creatList(){
	List* newList=(List*)malloc(sizeof(struct List));
	newList->data=1;
	newList->next=newList;
	
	return newList;
}

void push_back(List* list,int data){
	Node* curNode=list;
	
	while(curNode->next!=list){
		curNode=curNode->next;
	}
	
	Node* newNode=(List*)malloc(sizeof(struct List));
	newNode->data=data;
	
	curNode->next=newNode;
	newNode->next=list;
}

void print(List* list,int n){
	Node* curNode=list;
	while(n--){
		printf("%d %d ",curNode->data,curNode->code);
		curNode=curNode->next;
	}
	putchar('\n');
}

void getCode(List* list,int n){
	Node* curNode=list;
	
	int code;
	while(n--){
		printf("节点的值是%d，它的密码是：\n",curNode->data);
		cin>>code;
		curNode->code=code;
		curNode=curNode->next;
	}
}

void j_find(List* list,int k,int n){
	Node* temp=list->next;
	Node* pre=list;
	
	while(temp->data!=k){
		pre=pre->next;
		temp=temp->next;
	}
	
	int code;
	while(n){
		code=temp->code;
		
		for(int i=0;i<code-1;i++){
			pre=pre->next;
		    temp=temp->next;
		}
		printf("%d ",temp->data);
		n--;
		pre->next=temp->next;
		temp=temp->next;
	}
}

int main(){
	int n,k;
	cin>>n>>k;
	
	List* newList=creatList();
	
	for(int i=2;i<=n;i++){
		push_back(newList,i);
	}
	//print(newList,n);
	getCode(newList,n);
	
	j_find(newList,k,n);
}