地狱男爵之博客无限
BlogJava
首页
新随笔
联系
聚合
管理
posts - 33, comments - 70, trackbacks - 0
约瑟夫环算法(循环链表解决)
问题:约瑟夫环
有编号从1到N的N个人坐成一圈报数,报到M的人出局,下一位再从1开始,
如此持续,直止剩下一位为止,报告此人的编号X。输入N,M,求出X。
约瑟夫环算法(循环链表解决).现在老师出的题还是那么....... 呵呵
. 留个念像吧
java实现:
public
class
Josephus
{
public
static
void
main(String[] args)
{
if
(args.length
<
2
)
{
System.out.println(
"
Input N and M.
"
);
return
;
}
int
n
=
Integer.parseInt(args[
0
]);
int
m
=
Integer.parseInt(args[
1
]);
int
point
=
0
,number
=
1
;
List
<
Integer
>
list
=
new
ArrayList
<
Integer
>
();
for
(
int
i
=
1
;i
<=
n; i
++
)
{
//
初始化链表
list.add(i);
}
while
(list.size()
>
1
)
{
if
(number
%
m
==
0
)
{
list.remove(point);
--
point;
}
++
point;
//
指针后移
++
number;
if
(point
>
list.size()
-
1
)
{
//
指针越界重新开始
point
=
0
;
}
}
System.out.println(list.get(
0
));
}
}
c实现:
#include
<
stdio.h
>
struct node
{
int
v;
struct node
*
next;
}
*
p,
*
head,h;
//
head是头指针,h是头结点
main()
{
int
n,m;
int
i;
puts(
"
请输入人数n和报数上限m :
"
);
scanf(
"
%d%d
"
,
&
n,
&
m);
h.next
=
NULL;
//
头结点的next为空
head
=&
h;
//
头指针指向头结点
p
=
head;
//
p也指向头结点
/**/
/*
下面的循环用来建立循环链表
*/
for
(i
=
1
;i
<=
n;i
++
)
{
p
->
next
=
(struct node
*
)malloc(sizeof(struct node));
p
=
p
->
next;
p
->
v
=
i;
if
(i
!=
n)
{
p
->
next
=
NULL;
}
else
{
p
->
next
=
head
->
next;
}
}
p
=
head;
p
=
p
->
next;
//
p指向第一个结点
m
%=
n;
//
当m>n时有用
while
(p
!=
p
->
next)
{
for
(i
=
1
;i
<=
m
-
2
;i
++
)
{
p
=
p
->
next;
}
printf(
"
%d
"
,p
->
next
->
v);
p
->
next
=
p
->
next
->
next;
p
=
p
->
next;
}
printf(
"
%d
"
,p
->
v);
}
posted on 2006-06-07 23:37
地狱男爵(hellboys)
阅读(13318)
评论(19)
编辑
收藏
FeedBack:
#
re: 约瑟夫环算法(循环链表解决)
2006-10-15 10:36 |
shaoshuai
挺好挺好
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2006-10-16 00:00 |
doyphine
你的程序有点问题,有待解决哟!!你自己代几个数进去看看就知道了,我只试了C的
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2006-10-16 19:43 |
有点傻
看不懂哦~
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2006-10-17 11:30 |
榆钱
你的程序的密码好像就是刚开始排列时每个人的序号,是吗??而且你的输出有问题,挺大的问题
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2006-10-17 11:39 |
hellboys
java的测试过,没问题。 c的只作参考(未测试过)。
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2006-10-23 22:24 |
tian
very good Thank you very much.
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)[未登录]
2008-01-20 14:15 |
hhh
我也觉得,虽然不同的语言,但算法流程应该相同。可是你的呢,两种语言都不一样~~~
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2008-03-27 21:06 |
22
根本就不对
C语言的!
回复
更多评论
#
约瑟夫环算法C++
2008-05-20 17:43 |
吕起民
enum{N = 10,M=7};
int main(int argc, char* argv[])
{
char array[N] = {1,2,3,4,5,6,7,8,9,10};
int nCount = N;
int i = 0;
while(nCount > 1)
{
i = (i+M-1)%nCount;
printf("%d\n",array[i]);
memcpy(array+i,array+i+1,nCount-i);
nCount --;
// array[nCount] = 0;//可省此行
}
printf("约瑟夫=%d\n",array[0]);
return array[0];
}
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2008-10-30 17:32 |
dove52208@126.com
呵呵 在#include <stdio.h>
后加上#include <stdlib.h>之后 C的就可以实现了!!
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2009-02-01 17:56 |
johnpzd
原文思路很经典,佩服!!!
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2009-07-17 11:47 |
s
hh
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2009-07-17 11:47 |
s
ddddddddddddddddddddd
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2009-10-10 23:01 |
冷如冰
C语言描述的不是很准确
如果n = 10,m = 3,则程序的输出可能就会出现问题。
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2009-10-29 21:46 |
wx
挺好的,c的漏粘include<stdlib.h>,因为有用到malloc函数。
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2010-03-17 11:39 |
teamoGod
其他的没问题,只有当m=1的时候不对。
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2010-06-09 21:03 |
huchuhan
哥们啥是链表?
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)[未登录]
2011-09-12 16:54 |
Sky
@huchuhan
看不懂
!
回复
更多评论
#
re: 约瑟夫环算法(循环链表解决)
2012-03-19 10:28 |
527055685@qq.com
约瑟夫环的变体-37个奴隶问题,我也用了循环链表去做
#include <stdio.h>
#include <stdlib.h>
#define MAX 111 //总的奴隶数
#define DIE 3 //数K个,第K个要被杀
typedef struct link{
int value; //用了保存奴隶的编号
struct link *next;
}* loop_link;
void fun(struct link *slave);
int main(void)
{
loop_link slave=NULL,current,head;
int i;
for(i=1;i<=MAX;i++)
{
current=malloc(sizeof(struct link));
current->value=i;
current->next=NULL;
if(slave==NULL)
{
slave=current;
head=slave;
}
else
{
slave->next=current;
slave->next=slave->next;
slave=slave->next;
}
}
slave->next=head; /*将最后一个奴隶指向第一个奴隶,最终在这里形成一个循环链表 */
slave=head;
fun(slave);
return 0;
}
void fun(struct link *slave)
{
int j;
struct link* current;
if(slave->value==slave->next->value)
printf("这个编号为%d的奴隶不用被杀\n",slave->value);
else
{
for(j=1;j<DIE;j++)
{
current=slave;
slave=slave->next;
}
current->next=slave->next;
current=slave;
slave=current->next;
free(current);
fun(slave);
}
}
回复
更多评论
新用户注册
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
知识库
C++博客
博问
管理
<
2010年6月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
常用链接
我的随笔
我的评论
我的参与
最新评论
随笔分类
bash
vim(1)
系统综合(12)
编程语言(c/c++ java python sql ......)(7)
随笔(6)
随笔档案
2010年11月 (1)
2009年3月 (2)
2008年12月 (1)
2008年11月 (1)
2008年6月 (1)
2007年12月 (1)
2007年11月 (1)
2007年4月 (2)
2007年3月 (1)
2006年11月 (1)
2006年10月 (1)
2006年9月 (2)
2006年8月 (1)
2006年7月 (2)
2006年6月 (6)
2006年5月 (3)
2006年4月 (5)
2006年3月 (1)
文章档案
2005年12月 (1)
相册
SARA--以后LP的标准?
恍惚的美丽(2007年的五一)
连接
差沙
我以前blog地址
聪明的猪(cleverpig)
最新随笔
1. Open MacVim tabs from command-line
2. 优化MySQL数据库性能的八种方法
3. Hadoop分布式文件系统(HDFS)的安全隐患
4. sssh v2.0 - 快速 ssh 登陆脚本
5. mod_python在 RHEL/CentOs 64 位编译上的问题
6. 我想应聘中国男子国家足球队主教练一职
7. Android中文文档v0.1 beta低调发布,期待更多同学来参加review
8. 欢迎访问Android中国
9. ActiveMQ4.1 +Spring2.0的POJO JMS方案 扩展,以更加实用(基于ss).二
10. ActiveMQ4.1 +Spring2.0的POJO JMS方案 扩展,以更加实用(基于ss)
搜索
最新评论
1. re: Mysql 集群简介和配置[未登录]
@dustin
动不动就说不稳定,人家岛国的有个很大很大的社交网站就是这么搞的。你有啥子证据说不稳定,服了你。
--菜鸟
2. re: 约瑟夫环算法(循环链表解决)
评论内容较长,点击标题查看
--527055685@qq.com
3. re: 约瑟夫环算法(循环链表解决)[未登录]
@huchuhan
看不懂
!
--Sky
4. re: Mysql 集群简介和配置
评论内容较长,点击标题查看
--tmeper
5. re: 约瑟夫环算法(循环链表解决)
哥们啥是链表?
--huchuhan
阅读排行榜
1. Mysql 集群简介和配置(61948)
2. 约瑟夫环算法(循环链表解决)(13318)
3. 妙解网络多台dhcp引起的IP冲突 (5862)
4. Compass - springside 中的应用(5403)
5. mod_python在 RHEL/CentOs 64 位编译上的问题(3637)
评论排行榜
1. 约瑟夫环算法(循环链表解决)(19)
2. Compass - springside 中的应用(18)
3. Mysql 集群简介和配置(7)
4. 不要一辈子靠技术生存(7)
5. 我想应聘中国男子国家足球队主教练一职(5)