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

只有注册用户登录后才能发表评论。


网站导航:
 
<2008年1月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

随笔分类

随笔档案

文章档案

相册

连接

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜