`
bcyy
  • 浏览: 1809547 次
文章分类
社区版块
存档分类
最新评论

约瑟夫环,杀人游戏(静态循环链表实现)

 
阅读更多

觉得用静态循环链表最划算了。

1、动态链表要动态分配,指针移来移去,释放指针等等,弄得很烦,容易出错。

2、用循环链表是当然的了。

// DS: 似循环静态链表

#include <iostream>
#include <cstdio>
//#include <cstdlib>
using namespace std;

int Kill_You( const int sum = 1, const int distance = 1, const int start = 1)
{   //  一共参加自杀的人数有 sum 个,每 distence 个人就杀一个,从第 start 个人开始报数;
	//  返回留下的那个人的位序
	int pi = start - 1;
	int pj = 0;

	int *S = (int *)malloc( sum * sizeof(int) );	//不设头结点
	if (!S)
		cout << "Error!" << endl;
	for (int i = 0; i < sum; i++)	// 为人编号,第一个人为0
		S[i] = i + 1;
	S[sum - 1] = 0;	//  尾结点与首元结点接上
	
	cout << "依次杀掉:" << endl;
	for (int count1 = sum - 1; count1--; )
	{
		for (int count2 = distance - 1; count2--; )
		{
			pj = pi;	//  pj跟踪pi,以便删除结点
			pi = S[pi];
		}
		cout << pi + 1 << ' ';
		//  杀掉下标是pi的那个人,即删除该结点
		S[pj] = S[pi];	// pj是pi的前一个值
		pi = S[pi];
	}
	free(S);
	cout << endl;
	return pi + 1;
}

int main()
{
	int s;  // s 表示总人数
	int d;  // d 表示每d个人就杀掉一个(杀掉说出d的那个人)
	int k;  // k 表示第k个人开始报数
	while (1)
	{
		cout << "请输入人数(正整数):" << endl;
		cin >> s;
		cout << "请输入报数(正整数):" << endl;
		cin >> d;
		cout << "从第几个人开始报数:" << endl;
		cin >> k;
		printf( "留下第%d个人\n\n", Kill_You (s, d, k) );
	}
	
	return 0;
}


p.s. 没事多写写注释,挺好。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics