分享
 
 
 

面试系列2--约瑟夫环问题(Josephus)

王朝other·作者佚名  2006-06-15
窄屏简体版  字體: |||超大  

原题:

用户输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,直至全部输出。写出C程序。(约瑟夫环问题 Josephus)

提示:

由于当某个人退出圆圈后,报数的工作要从下一个人开始继续,剩下的人仍然是围成一个圆圈的,可以使用循环表,由于退出圆圈的工作对应着表中结点的删除操作,对于这种删除操作频繁的情况,选用效率较高的链表结构,为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断,链表不带头结点。所以,对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p,并根据具体情况移动。

为了记录退出的人的先后顺序,采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以,所以定义一个整型一维数组。如:int quit[n];n为一个根据实际问题定义的一个足够大的整数。

代码:

/********************************************************************

created: 2006/06/14

filename: C:\Documents and Settings\Administrator\桌面\tmpp\josephus.c

file path: C:\Documents and Settings\Administrator\桌面\tmpp

file base: josephus

file ext: c

author: A.TNG

version: 0.0.1

purpose: 实现 Josephus 环问题

用户输入M,N值,从1至N开始顺序循环数数,每数到M输出该数值,

直至全部输出。写出C程序。(约瑟夫环问题 Josephus)

*********************************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <malloc.h>

/* 结构体和函数声明 */

typedef struct _node_t

{

int n_num;

struct _node_t *next;

} node_t;

node_t *node_t_create(int n);

node_t *node_t_get(node_t **pn, int m);

/* 功能函数实现 */

/*

* name: node_t_create

* params:

* n [in] 输入要构造的链表的个数

* return:

* 返回构造成功的环形单向链表指针

* notes:

* 构造节点数量为 n 的环形单向链表

*

* author: A.TNG 2006/06/14 17:56

*/

node_t * node_t_create(int n)

{

node_t *p_ret = NULL;

if (0 != n)

{

int n_idx = 1;

node_t *p_node = NULL;

/* 构造 n 个 node_t */

p_node = (node_t *) malloc(n * sizeof(node_t));

if (NULL == p_node)

return NULL;

else

memset(p_node, 0, n * sizeof(node_t));

/* 内存空间申请成功 */

p_ret = p_node;

for (; n_idx < n; n_idx++)

{

p_node->n_num = n_idx;

p_node->next = p_node + 1;

p_node = p_node->next;

}

p_node->n_num = n;

p_node->next = p_ret;

}

return p_ret;

}

/*

* name: main

* params:

* none

* return:

* int

* notes:

* main function

*

* author: A.TNG 2006/06/14 18:11

*/

int main()

{

int n, m;

node_t *p_list, *p_iter;

n = 20; m = 6;

/* 构造环形单向链表 */

p_list = node_t_create(n);

/* Josephus 循环取数 */

p_iter = p_list;

m %= n;

while (p_iter != p_iter->next)

{

int i = 1;

/* 取到第 m-1 个节点 */

for (; i < m - 1; i++)

{

p_iter = p_iter->next;

}

/* 输出第 m 个节点的值 */

printf("%d\n", p_iter->next->n_num);

/* 从链表中删除第 m 个节点 */

p_iter->next = p_iter->next->next;

p_iter = p_iter->next;

}

printf("%d\n", p_iter->n_num);

/* 释放申请的空间 */

free(p_list);

system("PAUSE");

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有