学习笔记之约瑟夫环的两种实现方法(数组&链表)

原 作者 张根 | 发表于 | 分类于 2014级

        传说在很久很久以前，罗马人占领乔塔帕特之后咱们的约瑟夫大大，哦不，是著名的犹太历史学家约瑟夫(Josephus)和他的朋友躲在一个洞中，当时洞中还有其他的39名犹太人，他们非常的傻(ai)逼(guo)，宁愿死也不要被俘虏，于是非常聪明的想出一个绝世妙计来进行车轮式自杀。他们手拉手围成一个圈，从第一个人开始报数，谁报到3就自杀，然后下一个人继续从1开始报数直到所有的人都自杀完。。。。然而约瑟夫大大和他的朋友不想就这样无缘无故的死去，于是把自己和朋友安排在第16个位置和第31个位置成功地躲过了一劫。。。

         那么。。。问题来了，我们怎样用程序来把自杀的顺序排出来呢？？疑问疑问疑问

         （ps:代码仅用来实现功能而并未优化。）

思路一：

        定义一个数组用下标来代表每一个人，初始化为0，用0来代表他们活着，1代表死亡，当数到他时就将他杀掉(内容置为1)并将下标输出来，最后输出所有的元素下标后程序结束。

#include <stdio.h>
#include <malloc.h>

int main(void)
{
	int m,i,cnt,j = 1,k = 0;
	int *pArr;
	printf("n = ");      //总个数输入提示
	scanf("%d",&cnt);    //输入总个数
	printf("m = ");      //数到m时自杀
	scanf("%d",&m);      //输入m
	pArr = (int *)malloc(cnt * sizeof(int));
	for (i = 0;i < cnt;i++)
	{
		pArr[i] = 0;  //初始化为0
	}
	i = 0;
	while(1)
	{
		if (i < cnt && 0 == pArr[i])    //i小于总个数且值为0（活着）
		{
			if (m == j)
			{
				pArr[i] = 1;          //置为1（杀掉）
				j = 0;
				printf("%d\t",i+1);//输出该人编号(因为下标是从0开始，所以是输出i+1而非i)
				k++;
				if (k == cnt)
					break;
			}
			j++;
		}
		else if(i == cnt)
			i = -1;
		i++;
	}
        printf("\n");

        return 0;
}
思路二  ：

       创建一个循环链表，把它的首节点和尾节点连起来，就像约瑟夫大大和他的基(nan)友们一样手牵手围成一个圈，然后数到一个就将一个free(杀)掉并将它数据域内的编号取出来直到所有基(nan)友被杀光时程序结束。

#include <stdio.h>
#include <malloc.h>

typedef struct node
{
	int no;
	struct node *pNext;
}NODE;

//创建长度为n的链表
NODE *create(int n)
{
	NODE *pHead,*pTail,*pNew;
	int i;
	pHead = (NODE *)malloc(sizeof(NODE));
	pTail = pHead;
	for (i = 1;i <= n;i++)
	{
		pNew = (NODE *)malloc(sizeof(NODE));
		pTail->pNext = pNew;
		pNew->no = i;
		pTail = pTail->pNext;
	}
	pTail->pNext = pHead->pNext;

	return pHead;
}

//打印第pos个元素的数据域并删除，pos从1开始
void pop(NODE *pHead,int pos)
{
	NODE *pPos,*pTemp;
	int i;
	pPos = pHead;
	for (i = 1;i < pos;i++)
		pPos = pPos->pNext;
	pTemp = pPos->pNext->pNext;
	printf("%d\t",pPos->pNext->no);
	free(pPos->pNext);
	pPos->pNext = pTemp;
}

int main(void)
{
	NODE *pHead,*pTemp;
	int n,m,i,k;
	printf("n = ");
	scanf("%d",&n);
	if (n > 0)
	{
		pHead = create(n);
		printf("m = ");
		scanf("%d",&m);
		pTemp = pHead;
		k = n;
		while(k)
		{
			for (i = 1;i < m;i++)
				pTemp = pTemp->pNext;
			pop(pTemp,1);
			k--;
		}
		printf("\n");
	}
	else
		printf("输入有误！\n");

	return 0;
}
       欧了，丢手绢游戏至此结束 大笑