龙空技术网

【约瑟夫环】C语言数组法+java循环链表法

快乐的小log 83

前言:

今天大家对“循环链表的基本操作方法”大体比较看重,兄弟们都需要分析一些“循环链表的基本操作方法”的相关内容。那么小编在网络上网罗了一些关于“循环链表的基本操作方法””的相关资讯,希望同学们能喜欢,各位老铁们快快来学习一下吧!

1、什么是约瑟夫环问题

约瑟夫环(Josephus problem)是一个数学问题,传说在公元1世纪由犹太历史学家弗拉维奥·约瑟夫斯(Flavius Josephus)提出。

问题的描述如下:有n个人围坐一圈,从某个人开始顺时针报数,报到m的人出列,然后从下一个人重新开始报数,直到所有人都出列为止。

例如,如果n=7,m=3,那么报数的顺序为3、6、2、7、5、1、4,出列的顺序为3、6、2、7、5、1、4。问题的目标是找出最后一个出列的人。

约瑟夫环举例

2、问题起源

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式:41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。

问题是一开始要站在什么地方才能避免自杀?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。

3、约瑟夫环解法

约瑟夫环问题有多种解法,可以使用递归、数学公式等方法来解决。其中最常用的解法是使用循环链表来模拟整个过程。

具体的解法步骤如下:

1. 创建一个循环链表,包含n个节点,每个节点表示一个人。2. 从链表的第一个节点开始,通过循环遍历链表,每次遍历m-1个节点,找到第m个节点。3. 找到第m个节点后,将该节点从链表中移除。4. 重复步骤2和3,直到链表中只剩一个节点,即最后一个出列的人。

约瑟夫环问题可以用于模拟一些实际情况,例如报数游戏、密码学等领域问题。

小时候玩的丢手绢游戏 嘻嘻

4、代码实现 (C语言 & Java)

循环链表 解法动图01

循环链表 解法动图02

java 版本 约瑟夫 solution

C语言 约瑟夫 solution

/**    约瑟夫环:借助数组    len:     表示人数    target:  表示喊到该口号的出局。    flag:    表示当前哥们喊的口号 范围【1,2,3】    default: 从1开始数**/int YSF(int len,int target,int start){    int end = len+1;    int *a = (int*)malloc(sizeof(int)*end);    int i = 0,flag = 1,count = 0;    //初始化数组元素 都为0    for(;i<=len;i++) a[i] = 0;    //i作为游标    i = start;    while(count != len-1){        //当i游到最后一个元素的时候,应该继续从第一个元素开始        if(i == end) i = 1;        if(a[i]!=1) {            if(flag > target) flag = 1;            if(flag == target) { printf("%d ",i); a[i] = 1;count++; }            flag++;        }        i++;    }    putchar(10);    //遍历数组元素  找到那个值为0的元素,就是剩下的那个人    for(i = 1;i<=len;i++){        if(a[i]==0) a[0] = i;        printf("%-2d",a[i]);    }    putchar(10);    return a[0];}
//约瑟夫环public class Main {    //定义链表节点类型    public static class Node{        int data;        Node next;    }    //初始化循环链表数据    static Node initData(Node head){        int[] arr = {1,2,3,4,5,6,7,8,9,10};        Node tail = null;        for(int i:arr){            Node node = new Node();            node.data = i;            if(i==1) {                head = node;                tail = head;            } else {                tail.next = node;                tail = node;            }        }        tail.next = head;        return head;    }    //打印循环链表    static void printLK(Node head){        Node p = head;        while(p.next!=head){            System.out.print(p.data+" ");            p = p.next;            if(p.next==head) System.out.print(p.data+" ");        }        System.out.println();    }    //模拟约瑟夫环过程    // p   当前节点    // pre 当前节点的前一个节点    // t   当前节点的后一个节点    static void YSF(Node head){        Node pre=null,p,t=null;        p = head;        int flag = 1;        while(p.next!=p){            if(flag==3){                t = p.next;                pre.next = t;                p = t;                flag = 1;            } else {                pre = p;                p = p.next;                flag++;            }        }        System.out.println(p.data);    }    //主函数    public static void main(String[] args) {        Node head = null;        head = initData(head);        printLK(head);        YSF(head);    }}
4、运行结果截图

C语言 结果

Java 结果

标签: #循环链表的基本操作方法 #java链表怎么遍历 #c语言密码锁程序循环代码 #loopc语言 #循环java链表