正文

理解约瑟夫环,学会用到链表2013-03-28 10:28:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/javaxx/54152.html

分享到:

以下是本人的一些分享,我热爱编程,希望能多交编程的爱好者,如果你也是其中一名,那么请加好友,大家关注一下,下面的文章是自己觉得一些有用的东西,留下来给自己当笔记,当然也希望能帮助到你,首先感谢你的阅读~!
据说著名犹太历史学家 Josephus有过以下的故事:他参与并记录了公元66-70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住邱达伯特城,在坚持了47天之后,城市失守,沦陷后,他和40名英勇的将士退到附近一个洞穴躲藏起来。大家都表决说宁死不降,于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由大家排成一个圈,报数决定的,他有预谋地把自己安排在最后一个报数的位置,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。

通常我们解决这个问题的时候,都会用到链表, 解决问题的核心步骤如下:(程序的基本算法)

1.建立一个具有n个链结点,无头结点的循环链表;

2.确定第1个报数人的位置;

3.不断地从链表中删除链结点,直到链表为空。

但是一个初学者如何去解决这个问题呢?

我们可以用的方法也很多,比如说:

1,用数组标记法,先初始化为0,然后每个自杀的人的数值改为1,循环遍历判断到最后一个被标记完为止;

2,用数组记录所有的人,然后每个报到相应数字的打印出来,然后删除掉,后面的往前移动,循环到剩下最后一个为止;

 或者用递归,递推等等,在这里,我简单介绍一下上面第二个方法,以便初学者容易理解这个打印的过程。

#include <stdio.h>

#include <stdlib.h>

int main(void)

{

int k = -1;

int m = 0;

int n = 0;

printf("请输入N M :");

scanf("%d %d", &n, &m);

int a[n];

int i = 0;

for ( i = 0; i < n; i++ )

{

a[i] = i+1;

}

printf("\n");

int q = 0;

for ( ;; )

{

k = k + m;

if ( k >= n )

{

k = k % n;

}

printf("%d ", a[k]);

int j = 0;

for( j = k; j < n-1; j++ )

{

a[j] = a[j+1];

}

n--;

k--;

if ( n < 1 )

{

break;

}

}

printf("\n");

return 0;

}
我们在通过不间断地学习,才能获取真正的知识,从来不满足现在所拥有的知识,不断进取是根本,在编程的世界里也是这样,我喜欢获得新的知识,为获得新的知识兴奋,希望你也是一样,学无止境!!!
更多知识请参阅广州达内,或咨询广州达内老师

阅读(1571) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册