使用双向循环链表解决 约瑟夫环问题-数据结构和算法

2019
0 80

约瑟夫环问题描述

        有m个人,围成一个环,编号为 1、2、3、、、m,从第一个人开始循环报数(从1开始数),假设数到n的那个人出局,然后从下一个人继续数数(从1开始数),数到n出列,以此循环,最后那个人为胜利者,求胜利者的编号,以及出局者的顺序。

解决方案

        使用双向循环链表

        测试数据 m=9,n=5

        输出:5 1 7 4 3 6 9 2 8

代码(c++描述) 

Node.h

#pragma once
class Node
{
public:
	int index;
	Node * prve;
	Node * next;
	Node(int index);
	~Node();
};

CircularList.h

#pragma once
#include "Node.h"
class CircularList
{
public:
	Node * root;//头节点
	Node * last;//尾节点
	int size=0;
	CircularList();
	~CircularList();

	void addNode(int num);//添加 num 个节点,编号为(0-num)
	Node * removeNode(Node * n);//删除节点
	void prinft();//打印节点

	int begin(int n);

};

Node.cpp

#include "Node.h"
#include <iostream>
Node::Node(int index)
{
	this->next = NULL;
	this->index = index;
}
Node::~Node()
{
}

CircularList.cpp

#include "CircularList.h"
#include "Node.h"
#include <iostream>
using namespace std;
//构造函数
CircularList::CircularList()
{
}
//析构函数
CircularList::~CircularList()
{
}
//添加节点
void CircularList::addNode(int num)
{
	root = new Node(1);
	last = root;
	for (int i=2;i<=num;i++)
	{
		Node * n = new Node(i);
		last->next = n;
		n->prve = last;
		last = n;
	}
	size = num;
}
//打印节点
void CircularList::prinft()
{
	Node * n = root;
	while (n != NULL)
	{
		cout << n->index << "\t";
		n = n->next;
	}
	cout << endl;
}
//删除节点
Node * CircularList::removeNode(Node * n)
{
	Node * node = n->next;
	n->prve->next = node;
	node->prve = n->prve;
	n->next = NULL;
	n->prve = NULL;
	cout << n->index<<" ";
	delete(n);
	size--;
	return node;
}

//找出最后一个节点
int CircularList::begin(int n)
{
	cout << "出局人的顺序是:" << endl;
	//形成循环链表
	if (last == NULL) 
	{
		return -1;
	}
	else 
	{
		last->next = root;
		root->prve = last;
	}
	int i = 1;//当前数字
	Node * node = root;//当前节点
	while (size>1)
	{
		if (i==n)
		{
			i = 1;
			node = removeNode(node);
		}
		else 
		{
			i++;
			node = node->next;
		}
	}
	cout << node->index << endl;
	return node->index;
}

Test.cpp

#include <iostream>
#include "CircularList.h"

void main()
{
	CircularList * c = new CircularList();
	c->addNode(9);//人数(编号从1开始)
	c->begin(5);//数到5的人删除(从1开始)
	system("pause");
}

留言(0)
加载更多
猜你喜欢
  • ofc 节点的添加删除(c#语言)

    节点的添加删除(c#语言)
  • blog -求

    描述 给定一个int类型一维组 a[],一个int类型的值 b。编写一个程序,判断组中有没有两个(a[i],a[j])的等于b,如果存在,返回两个在a组中的下(return new int[]={1,2}
  • blog --完全二叉树的权值

    描述:思路: 示完全二叉树,先序遍历的方式遍历每一层的节点,一个组储存每一层的,因为规模小于100000所以一个容量为17的组即可。计完每一层的,再比较层最小之最大的那一层。代码:packa
  • blog 冒泡排序 -

    思想: 每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 变量i遍历整个组,变量j遍历i后面的组,每次交换i比j大的元素,使得i遍历过的组元素有序,直至整个组被
  • ofc vue使v-model(绑定)自动收集

    vue使v-model(绑定)自动收集
  • blog 快速排序 -

    思想 将待排序集合以该集合中随机的一个为分界点分成左右两个集合,一次排序使其右边的集合的全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述排序操作,直到递归集合没有,递归束完成排序。 描述 现有待排序
  • blog 插入排序 -

    思想: 把所有需要排序的分成两个集合,一个是待排序集合,一个是已排序的集合,每次从未排序集合顺序或随机拿取一个,把它加入到已排序集合使其有序,直到未排序集合中的被取走完,束 public class Test
  • blog -反转-递归

    反转 有一个单t如下: t = 1->2->3->4->5->6->7->8->9 写一个方反转t如下: 1<-2<-3<-4<-5<
  • blog 最小生成树Kruskal-

    最小生成树其应         什么是最小生成树:一个有 n 个点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个点,并且有保持图连通的最少的边。最小生成树可以krus
  • blog 选择排序 -

    思想: 对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完 描述: 变量i遍历整个组,变量j遍历i后面的组,每次遍历i初始k=i,每次发现a[k]比a[