技术宅的结界

 找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 181|回复: 0
收起左侧

【C】约瑟夫环的双向链表解法

[复制链接]

7

主题

11

帖子

261

积分

用户组: 中·技术宅

UID
6266
精华
5
威望
37 点
宅币
121 个
贡献
30 次
宅之契约
0 份
在线时间
5 小时
注册时间
2020-9-26
发表于 2020-11-1 21:58:21 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有帐号?立即注册→加入我们

x
本帖最后由 new_starter 于 2020-11-1 22:01 编辑

约瑟夫环问题起源于一个犹太故事。
传说罗马人攻占了乔塔帕特,41个人藏在山洞中躲过了这场浩劫。这41人中包括历史学家Josephus约瑟夫和他的一个朋友。剩余的39人为了表示绝不屈服于罗马人于是决定集体自杀。所有这41人围成圈由第一个人开始顺时针报数,每报数为3的人就立刻自杀,然后再由下一个人重新开始报数,仍然是每报数为3的人就立刻自杀,直到所有人都死亡为止。
约瑟夫和他的朋友并不想自杀。于是约瑟夫想到了一个计策,他们两人同样参与到自杀方案中,但是最后却躲过了自杀。
下面的程序给出了约瑟夫环的解法,注意该程序需要StoneValley库的支持:
[C] 纯文本查看 复制代码
#include <stdio.h>
#include "../src/svstring.h"

// Function: cbftvs_print_list
// Desc:     Print item number in linked-list.
// Param:    pitem: pointer to each node in a list. param: N/A.
// Return:   CBF_CONTINUE only.
int cbftvs_print_list(void * pitem, size_t param)
{
	printf("%ld, ", *(long *)((P_NODE_D)pitem)->pdata);
	DWC4100(param);
	return CBF_CONTINUE;
}

// Function: main
// Desc:     Program entry.
// Param:    N/A.
// Return:   0: no error. 1: allocation failure.
int main(void)
{
	char c;
	long i, j;
	LIST_D jring;
	P_NODE_D pnew, pnode;
	const char * sfx[] = { "m", "ms", "is", "are" };
	strInitLinkedListDC(&jring);
	pnode = jring;
	printf("# A solution to Josephus's ring. <"); svPrintVersion(); printf("> #\n");
Lbl_Start:
	do
	{
		printf("How many items will be there in a ring? ");
		scanf("%ld", &j);
	}
	while (j < 1);
	for (i = 1; i <= j; ++i)
	{
		if (NULL == (pnew = strCreateNodeD(&i, sizeof(long))))
		{
			puts("Error! Allocation failure while building ring.");
			strFreeLinkedListDC(&jring, FALSE);
			return 1; /* Allocation failure. */
		}
		if (NULL != pnode)
		{
			pnode->ppnode[NEXT] = pnew;
			pnew->ppnode[PREV] = pnode;
		}
		else
			jring = pnew;
		pnode = pnew;
	}
	/* Make a ring. */
	pnode->ppnode[NEXT] = jring;
	jring->ppnode[PREV] = pnode;
	do
	{
		printf("\tNow, there %s %ld ite%s in the ring.\nWhich number would you like \
to choose to delete ite%s sequentially? ", sfx[(j > 1) + 2], j, sfx[j > 1], sfx[j > 1]);
		scanf("%ld", &i);
	}
	while (i < 1);
	for ( ;; )
	{
		pnode = strLocateItemDC_R(jring, i - 1);
		if (jring != pnode)
		{
			jring = pnode->ppnode[NEXT];
			strRemoveItemLinkedListDC(pnode);
			printf("\tRemove: %ld\n", *(long *)pnode->pdata);
			strDeleteNodeD(pnode);
		}
		else
			break;
	}
	if (NULL != pnode)
	{
		printf("The rest of ite%s in the ring %s labeled with: ",
		sfx[jring != jring->ppnode[NEXT]], sfx[(jring != jring->ppnode[NEXT]) + 2]);
		strTraverseLinkedListDC_X(jring, NULL, cbftvs_print_list, 0, FALSE); puts("\b\b.");
	}
	strFreeLinkedListDC(&jring, FALSE);
	pnode = NULL;
	do
	{
		fflush(stdin);
		printf("Would you like to continue playing(Y/n)? ");
		scanf("%c", &c);
		switch (c)
		{
		case 'Y': case 'y': goto Lbl_Start;
		case 'N': case 'n': return 0;
		}
	}
	while (c != 'Y' && c != 'y' && c != 'N' && c != 'n');
	return 0;
}

程序运行结果如下:
Capture.PNG
该程序的核心是strLocateItemDC_R函数,使用该函数可以向前、向后定位循环双向链表上的任意一个节点。

评分

参与人数 1威望 +10 宅币 +10 贡献 +10 收起 理由
0xAA55 + 10 + 10 + 10 支持!

查看全部评分

本帖被以下淘专辑推荐:

回复

使用道具 举报

本版积分规则

QQ|申请友链||Archiver|手机版|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图  

GMT+8, 2020-11-28 04:03 , Processed in 0.097578 second(s), 35 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表