设为首页 加入收藏

TOP

josephus Problem 初级(使用数组)
2015-07-20 17:41:57 来源: 作者: 【 】 浏览:2
Tags:josephus Problem 初级 使用

问题描述:

这是一个很经典的问题,一桌人一起吃饭,比如有6个人,第一个人从1开始报数,后面的人报的数依次递增,当报出的数为某一个数时,报数的那个人出局,游戏继续。出局的那个人后面的还没有出局的人继续从1开始报数,直到所有的人出局为止。得出出局顺序。

比如有6个人,分别为1,2,3,4,5,6 。报数到3的人出局,则出局顺序应该是:3,6, 4, 2, 5, 1

解决方案:

可以采取对数组置标志位解决,将其置为0表示已出局,则遍历到它的时候,不需要增加计数。置标志位在实际开发中也是比较常见的一种思路。

代码:

#include 
  
   
/*total people number*/
#define ALL 100	
/*people leave when count to left_counter*/
#define left_counter 3
/*people array*/
int people[ALL];

/*init people array*/
void initPeople()
{
	int i = 0 ;
	for (i = 0; i < ALL; i++)
	{
		people[i] = i+1;
	}
}

/*print people array*/
void printPeople()
{
	int i = 0;
	for (i = 0; i < ALL; i++)
	{
		printf("%d ",people[i]);
	}
	printf("\n");
}

int main(void)
{
	initPeople();
	int left = ALL;		/*init total left number*/
	int counter = 0;	/*init counter*/
	int i = 0;		/*init array index*/
	while (1)
	{
		if (0 != people[i])
		{
			counter++;
		}
		/*if counter == left_counter , peopler out, set people[i] = 0
 		  counter = 0; 
		  left--;
		**/
		if (counter == left_counter)
		{
			left--;
			printf("%d is out\n", people[i]);
			counter = 0;
			people[i] = 0;
			printPeople();
		}		
		/*if no people left, problem solved*/
		if (0 == left)
		{
			printf("problem finished!\n");
			break;
		}
		/*increase index*/
		i++;
		if (i == ALL)
		{
			i = 0;
		}	
	}
	return 0;
}

  

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇poj 1007 DNA Sorting (求逆序数.. 下一篇LeetCode――Trapping Rain Water

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·MySQL 安装及连接-腾 (2025-12-25 06:20:28)
·MySQL的下载、安装、 (2025-12-25 06:20:26)
·MySQL 中文网:探索 (2025-12-25 06:20:23)
·Shell脚本:Linux Sh (2025-12-25 05:50:11)
·VMware虚拟机安装Lin (2025-12-25 05:50:08)