约瑟夫问题求解(C++)

 

设有n 个人站成一圈，每个人持有一个密码（正整数) 。现从第t 个人开始，按顺时针方向“1,2,3,4, …”循环报数，数到m1 （第t 个人所持密码）的人出列，然后从出列者的下一个人重新开始报数，数到m2 （刚出列者所持密码）的人又出列，如此重复进行，直到n 个人都出列为止。

问题是 ：对于任意给定的n 个人的原始排列顺序，求出n 个人的出列顺序。

输入数据从文本文件中读取。该文件有两行：第1 行只有一个整数，表示报数的起始位置；第2 行是n 个所持密码。

输出结果显示在屏幕上。

例如，从文本文件读取数据

2

5 6 3 2 2 4

屏幕显示

1 6 5 3 4 2

程序如下：

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
// 节点类
class Node {
public:
	// 构造函数
	Node(int x, int num, Node * node = NULL) {
		stride = x;
		next = node;
		number = num;
	}
	int stride, number;		/* stride约瑟夫问题的m值，number是人的序号 */
	Node *next;
};
// 循环链表
class CircleList {
public:
	// 构造函数
	CircleList() {
		first = last = NULL;
		length = 0;
	}
	// 在链表的末尾插入新节点
	void insertLast(int stride, int number) {
		if (first == NULL) {
			first = last = new Node(stride, number);
			first->next = first;
		}
		else {
			last->next = new Node(stride, number, first);
			last = last->next;
		}
		length++;
	}
	// 删除node的下一个节点
	void removeNext(Node * node) {
		Node *temp = node->next;
		if( first == last) 
			first = last = NULL;
		else
			node->next = node->next->next;
		delete temp;
		length--;
	}
	// 根据序号查找节点
	Node *getNode(int rank) {
		Node *t = first;
		for(int i = 1; i < rank; i++ ) {
			t = t->next;
		}
		return t;
	}
	Node *first, *last;
	int length;
};
int main() {
	CircleList list;
	int start = 0;
	string filename;
	
	// 打开文件
	cout<<"请输入文件名：（此处为data.txt）"<<endl;
	cin>>filename;
	ifstream fin(filename.c_str());
	if (!fin) {
		cout<<"无法打开文件!"<<endl;
		return 0;
	}
	// 从文件读取数据
	char ch;
	char element[10];
	int ii = 0;	/* 计数器 */
	
	fin.get(ch);
	while(ch != '\n') {
		element[ii++] = ch;
		fin.get(ch);
	}
	element[ii] = '\0';
	start = atoi(element);
	ii = 0;
	while( !fin.eof() ) {
		fin.get(ch);
		while(ch != ' ' && ch != '\t' && ch != '\n') {
			element[ii++] = ch;
			fin.get(ch);
		}
		element[ii] = '\0';
		int e = atoi(element);
		if(e != 0)
			list.insertLast(e, list.length+1);
		ii = 0;
	}
	// 开始模拟约瑟夫的过程
	Node *begin = list.getNode(start);
	int stride = begin->stride;;
	Node *prev;
	while (list.length != 0) {
		prev = begin;
		for(int i = 2; i < stride; i++){
			prev = prev->next;
		}
		stride = prev->next->stride;
		cout<<prev->next->number<<" ";
		list.removeNext(prev);
		begin = prev->next;
	}
	cout<<endl;
	getchar();
	getchar();
	return 0;
}