精华内容
下载资源
问答
  • 不带有头结点的循环单链表解决约瑟夫环问题 不带有头结点的循环单链表解决约瑟夫环问题
  • 这个算法使用的是循环单链表解决约瑟夫环的问题,代码如下: package CircleLinkedlist; /*六月三十号,使用循环单链表实现约瑟夫环*/ public class CircleLinkedlistDemo { public static void main(String[] ...

    这个算法使用的是循环单链表解决约瑟夫环的问题,代码如下:

    package CircleLinkedlist;
    
    
    /*六月三十号,使用循环单链表实现约瑟夫环*/
    
    public class CircleLinkedlistDemo {
    		public static void main(String[] args) {
    			
    			// 测试一把看看构建环形链表,和遍历是否 ok
    			CircleLinkedlist circleSingleLinkedList = new CircleLinkedlist();
    			circleSingleLinkedList.create(5);// 加入 5 个小孩节点
    			circleSingleLinkedList.showChild();
    			//测试一把小孩出圈是否正确
    			circleSingleLinkedList.countBoy(1, 2,5);
    			
    		}
    		
    		
    }
    
    
    /*创建循环的单链表的节点*/
    class Child{
    	private int id;     //这个节点的id
    	
    	private Child next;   //指向下一个节点的指针
    
    	public int getId() {
    		return id;
    	}
    
    	public void setId(int id) {
    		this.id = id;
    	}
    
    	public Child getNext() {
    		return next;
    	}
    
    	public void setNext(Child next) {
    		this.next = next;
    	}
    	
    	@Override
    	public String toString() {
    		return "Child [id=" + id + "]";
    	}
    	
    
    	public Child(int id) {
    		this.id = id;
    	}
    	
    }
    
    
    /*创建这个循环单链表*/
    class CircleLinkedlist{
    	
    	private Child first=null;  //第一个节点没有数据
    	
    	/*根据用户输入的数据,创建一个环形的单链表*/
    	public void create(int nums) {
    		if(nums<1) {
    			System.out.println("用户输入的不正确");
    			return;
    		}
    		
    		Child cur=null;  //这个是一个辅助的指针,构建环形链表
    		
    		for(int i=1;i<=nums;i++) {  
    			Child child=new Child(i);
    			
    			if(i==1) {
    				first=child;
    				first.setNext(first);
    				cur=first;
    			}
    			else {
    				cur.setNext(child);
    				child.setNext(first);
    				cur=child;
    			}
    		}
    	}
    	
    	/*遍历当前的环形链表*/
    	public void showChild() {
    		if(first==null) {
    			System.out.println("没有任何节点");
    			return;
    		}
    		
    		Child cur=first;
    		
    		while(true) {
    			System.out.printf("小孩的编号 %d \n", cur.getId());     
    			
    			if(cur.getNext()==first) {
    				break;
    			}
    			
    			cur=cur.getNext();
    		}
    	}
    	
    	
    	/*根据用户的输入开始的人的编号,需要报几个数,圈内有多少人,然后依次给出链表的人的编号*/
    	public void countBoy(int startNo,int countNum,int nums) {
    		if(first==null||startNo<1||startNo>nums) {
    			System.out.println("输入有误,请重新输入");
    			return;
    		}
    		
    		Child help=first; 
    		while(true) {
    			if(help.getNext()==first) {   //使得指针指向最后一个节点,以便与help可以连接中断的指针
    				break;
    			}
    			
    			help=help.getNext();
    		}
    		
    		//当某一个编号的小孩开始报数的时候,让first和help的指针同时移动k-1次
    		for(int j=0;j<startNo-1;j++) {
    			first=first.getNext();
    			help=help.getNext();
    		}
    		
    		
    		//小孩开始报数,让first和help同时开始移动,移动m-1次,然后出圈
    		while(true) {
    			if(help==first) {
    				break;
    			}
    			 
    			for(int j=0;j<countNum-1;j++) {   //此时first指针指向了这个要出圈的小孩节点
    				first=first.getNext();
    				help=help.getNext();
    			}
    			
    			System.out.printf("小孩%d 出圈\n", first.getId());
    			
    			first=first.getNext();
    			help.setNext(first);
    		}
    		
    		    System.out.printf("最后留在圈中的小孩编号%d \n", first.getId());
    	}
    	
    }
    
    展开全文
  • 运用循环单链表解决约瑟夫环问题

    千次阅读 2018-04-05 11:02:22
    //首尾相接,构造一个循环单链表   int n=c;   p=head;  cout输出运算前的结点(运算的起始位点):";  while(n--)   {   cout<<p->data,";   p=p->next;   }   cout ;  }    void josephus::...
    #include <iostream>  
    
    using namespace std;  
    struct node //构造结点
    {  
        node(int a):data(a),next(NULL){}  //为结点初始化(分配空间)   
        int data;  
        node *next;  
    };   
    class josephus  
    {  
    public:  
        josephus(int x,int y,int z):a(x),b(y),c(z) //构造函数的初始化表列
        {  
    create();  
            output();  
        }        
        void create();  //链表的初始化
        void output();  //输出数值  
    private:  
        node *head;//循环链表的头节点  
        int a;     //链表节点个数  
        int b;     //第一个序号  
        int c;     //报数出局的数  
    };  
    void josephus::create()  
    {  
        node *pre=NULL;  
        node *cur=NULL;  
        node *p=new node(1);  
        head=p;  
        cur=p;  
        for(int i=2;i<=a;i++) //为单链表初始化
        {  
            p=new node(i);  
            pre=cur;  
            cur=p;  
            pre->next=cur;  
        }  
        cur->next=head;                    //首尾相接,构造一个循环单链表    
        int n=c;  
        p=head;  
    cout<<"输出运算前的结点(运算的起始位点):"<<endl;
        while(n--)  
        {  
            cout<<p->data<<",";  
            p=p->next;  
        }  
        cout << endl;  
    }  
      
    void josephus::output()  
    {  
        node *pre=NULL;  
        node *cur=head;  
        b;  
        while(b--)                            //寻找第b个数(开始数值)  
        {  
            pre=cur;  
            cur=cur->next;  
        };
    cout<<"依次输出被删除的数值:"<<endl;
        while(a--)                           //输出链表中所有的结点值
        {
    for(int n=0;n<5;n++)             //控制输出函数的行数
    {
    int s=c-1;  
    while(s--)                    //寻找间隔c的值
    {
    pre=cur;  
    cur=cur->next;  
    }  
    node *p=cur;  
    cout<<p->data<<"  ";  
    cur=cur->next;                //删除此次输出的结点 
    pre->next=cur;  
    delete p;    
    }
    cout<<endl;
    };
    cout<<endl;
    }  
      
    int main()  
    {
        josephus josephus(100,5,5);  //自定义初始化数值

        return 0;  

    }  


    展开全文
  • 约瑟夫环(Josephus)由来: 约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提处的,他参加并记录了公园66-70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在...

    约瑟夫环(Josephus)由来:

    约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提处的,他参加并记录了公园66-70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷后,他和40名顽强的将士在附近的一个山洞避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,决定了一个自杀方式。他们41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。约瑟夫有预谋地将朋友和自己安排在第16个和第31个位置,逃过了这场死亡游戏,并一起投降了罗马。

    约瑟夫问题具体描述是:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个。例如N=5,M=3,被杀掉的顺序是:3,1,5,2,4。

    实验结果如图:

    约瑟夫问题:

    实验完整代码如下:

      1 #include <stdio.h>
      2 #include <malloc.h>
      3 /*常量定义*/
      4 #define OK 0
      5 #define Err_Memory -1
      6 #define Err_InvalidParam -2
      7 typedef int Status;
      8 
      9 /*节点结构定义*/
     10 typedef int ElemType;
     11 typedef struct node{
     12     ElemType id;
     13     struct node *next;
     14 } *LinkList, ListNode;
     15 
     16 Status CreateList(LinkList Head, int n)
     17 {
     18     ListNode *p, *s;
     19     int i;
     20 
     21     if (!Head)
     22         return Err_InvalidParam;
     23 
     24     Head->next = Head;
     25     p = Head;
     26 
     27     for(i = 1; i<=n; i++){
     28         s = (ListNode *)malloc(sizeof(ListNode));
     29         s->id = i;
     30         s->next = p->next;
     31         p->next = s;
     32         p = p->next;
     33         printf("第%d个序号为:%d\n", i, p->id);
     34     }
     35 
     36     return OK;
     37 }
     38 
     39 int Josephus(LinkList Head, int m)
     40 {
     41     int iCount = 1, iOrder = 0;
     42     ListNode *pcur, *pprev, *pdel;
     43 
     44     if (!Head)
     45         return Err_InvalidParam;
     46 
     47     pprev = Head;
     48     pcur = Head->next;
     49     while(pprev != pcur->next){
     50         if (pcur != Head && iCount == m){
     51             pdel = pcur;
     52             pprev->next = pcur->next;
     53             pcur = pcur->next;
     54             iOrder++;
     55             printf("第%d个出列序号为:%d\n", iOrder, pdel->id);
     56             free(pdel);
     57             iCount = 1;
     58         } else {
     59             if (pcur != Head)
     60                 iCount ++;
     61             pprev = pcur;
     62             pcur = pcur->next;
     63         }
     64     }
     65 
     66     printf("第%d个出列序号为:%d\n", ++iOrder, pcur->id);
     67     free(pcur);
     68     free(pprev);
     69 
     70     return OK;
     71 }
     72 
     73 void main()
     74 {
     75     int n, m;
     76     LinkList Joseph;
     77     printf("请输入参与人数n:\n");
     78     scanf("%d", &n);
     79     printf("请输入报数上限m:\n");
     80     scanf("%d", &m);
     81     Joseph = (ListNode *)malloc(sizeof(ListNode));
     82     if (CreateList(Joseph, n) != OK){
     83         printf("链表创建错误\n");
     84         return;
     85     }
     86     if(Joseph->next == Joseph){
     87         printf("参与人数输入错误\n");
     88         return;
     89     }
     90     printf("\n");
     91     Josephus(Joseph, m);
     92 
     93 }

     

    展开全文
  • #include <stdio.h>#include <stdlib.h>typedef struct aa{int data;struct aa *next;}Link;int n; Link * CreateLink(Link *L){Link *p,*q;int i;printf("请输入人数:");scanf("%d",&...i...

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct aa{
     int data;
     struct aa *next;
    }Link;
    int n;
    Link * CreateLink(Link *L){
     Link *p,*q;
     int i;
     printf("请输入人数:");
     scanf("%d",&n);
    for(i=1;i<=n;i++){
        if(i==1){
         L=p=(Link *)malloc(sizeof(Link));
         L->data=i;
     }
     else
     {
      q=(Link *)malloc(sizeof(Link));
      q->data=i;
      p->next=q;
      p=q;
      }
     }
     p->next=L;
     return L;
    }
    int DeleteLink(Link *L){
     int x;
     Link *p,*q;
     int k=1,i=1;
     printf("请输入要报的数:");
     scanf("%d",&x);
     q=L;
        while(n>1){
         k++;
         p=q;
       q=q->next;
       if(k==x){
     p->next=q->next;
     printf("第%d次报数,淘汰的数:%d\n",i,q->data);
        free(q);
        k=1;
        q=p->next;
        n--;
         i++;
       }
     }
     return p->data; 
    }
    int main(){
     Link *L,*p;
     int x;
     L=CreateLink(L);
     for(p=L,x=0;p!=NULL,x<n;x++,p=p->next)
      printf("%d ",p->data);
     x=DeleteLink(L);
     printf("最后留下的数是%d",x);
    }

    转载于:https://www.cnblogs.com/ljxn/p/10732671.html

    展开全文
  • 使用循环单链表解决约瑟夫环问题

    千次阅读 2014-02-26 17:23:16
     //创建一个长度为n的循环链表    p =(LinkList)malloc(sizeof(LNode));   p- > data = 0 ;   p- > link = p ;    cur = p ;   for (int i = 1 ;i < n ;i++)   {   LinkList t =...
  • @用循环单链表解决约瑟夫(Joseph)问题 用循环单链表解决约瑟夫(Joseph)问题 问题描述 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39...
  • 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复...
  • /***************************************用循环单链表实现约瑟夫环*************************************/ #include using namespace std; class P { public:  char data;  P* next; }; ...
  • 这里用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点...
  • Description ...一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针...提示:存储结构采用不带头结点的循环单链表,...
  • 循环链表为单链表的变形,与单链表的区别在于循环链表的尾结点的指针域不是空,存放的是首结点的地址,因此判断表空的条件不是first->Link==NULL... 约瑟夫问题的求解关键为把围坐一圈的人抽象成循环单链表的数据结构。
  • 单链表实现约瑟夫环: 分析:首先我们应该了解什么事约瑟夫环约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人...
  • *约瑟夫环问题 *问题描述:N个人做成一圈,从第K个人开始报数游戏(从0开始报数), 报M的出列,最后剩下的一个人获胜 *算法: 循环单链表(无头节点) *新建单链表: 返回value最小的节点当作"head",新建过程即是...
  • 环形单向链表解决约瑟夫问题: 首先要创建一个N个小孩的环形单向链表: 1.创建一个first指针,置为空,再创建一个辅助指针curBoy 2.用for循环创建小孩节点,如果是第一个节点(first指向第一个小孩,并且第一个...
  • 链表有各种形式,除了单链表外还有双链表,循环链表等。 图示如下: 下面我们来讨论单链表单链表的存储 每个节点由两部分组成:数据元素本身和指向下一节点的指针。 struct linkNode { datatype
  • Josepfu(约瑟夫环) 问题 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌...
  • 循环单链表: /** * 单链表 * * @author liyang */ public class CircleLinkNodeList { /** * 头节点 加入的数据的第一个 */ private LinkNode first; /** * 记录链表中节点数量 */ private int ...
  • 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
  • 首先先了解一下什么是约瑟夫环问题Josephus有过的故事:39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数...
  • java之单链表解决约瑟夫问题 文章内容选自尚硅谷,jdk8,eclipse环境 所谓约瑟夫问题就是丢手绢游戏,一个带编号环形列表,从某处开始重复报数,假如报到n的人必须退出列表,求最后退出列表的人是原来环形列表的第几...
  • 约瑟夫环:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围只有一个人。 ...
  • 思路分析:用一个不带头节点的环形链表来处理,先构成一个有n个节点的环形单链表,然后由K节点开始报数,报到m时,对应节点删除,然后再从被删除的节点下一个节点开始计数,知道最后一个节点被删除算法结束。...
  • 遍历环形链表思路 先让一个辅助指针(变量)curBoy, 指向first节点 然后通过一个while循环遍历该环形链表即可 curBoy.next == first 结束 生成小孩出圈顺序的思路 根据用户的输入, 生成一个小孩出圈的顺序 n = 5, 即...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,041
精华内容 416
关键字:

循环单链表解决约瑟夫环