joseph.cpp

时间复杂度为O(nlogn)的Joseph排列问题的计算程序。程序的运行时间与m无关。在一分钟之内可以计算n=10^6,m任意的Joseph排列问题.

//////////////////////////////////////////////////////////////////////////
// 时间复杂度为O(nlogn)的Joseph排列问题
// 刘金义－－辽宁石油化工大学工程软件研究所
// [e-mail]
//////////////////////////////////////////////////////////////////////////
#include <stdio.h>

struct Node 
{
	int num;
	Node *prev, *next;
};

void Joseph(int n)
{
	Node *head = 0, *tail = 0;

	for(int i=1; i<=n; i++)
	{
		Node *newnode = new Node;
		newnode->num = i;
		newnode->prev = tail;
		if(tail)
			tail->next = newnode;
		tail = newnode;
		if(!head)
			head = newnode;
	}
	tail->next = head;
	head->prev = tail;
	Node *p = head->next->next;
	i = n;
	while(i>0)
	{
		printf("%d ", p->num);
		
		p->prev->next = p->next;
		p->next->prev = p->prev;
		Node *pnext = p->next;
		delete p;
		if(p!=pnext)
			p = pnext->next->next;

		i--;
	}
}

main()
{
	int n;
	printf("Input the number:");
	scanf("%d", &n);
	Joseph(n);
}