posts - 28, comments - 53, 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) 阅读(4004) 评论(9) 编辑收藏

FeedBack:

# re: 约瑟夫环算法(循环链表解决)

2006-10-15 10:36 | shaoshuai

挺好挺好回复更多评论

# re: 约瑟夫环算法(循环链表解决)

2006-10-16 00:00 | doyphine

你的程序有点问题，有待解决哟！！你自己代几个数进去看看就知道了，我只试了Ｃ的回复更多评论

# 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];
} 回复更多评论

新闻频道新用户注册刷新评论列表

标题

姓名

主页