Java简单实现约瑟夫环算法示例

本文实例讲述了Java简单实现约瑟夫环算法。分享给大家供大家参考，具体如下：

1.算法背景:

罗马人攻占了乔塔帕特，41人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家josephus和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家决定了一个自杀方案，所有这41人围城一个圆圈，由第一个人开始顺时针报数，没报数为3的人就立刻自杀，然后由下一个人重新开始报数

仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止.

约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参数到自杀方案中，但是最后却躲过了自杀。请问是怎么做到的

2.下面直接代码进行实现：

public class YueSeFuHuan {
  static final int nums = 41;// 总共多少人
  static final int killMan = 3;// 数到3则被杀
  public static void main(String[] args) {
    jufehus(2);
  }
  public static void jufehus(int alive) {
    int[] man = new int[nums];// 未被杀的都被标记为0
    int pos = -1;// 数组角标
    int i = 0;
    int count = 1;// 杀到第几个记录值
    while (count <= nums) {
      do {
        pos = (pos + 1) % nums;// 循环标记
        if (man[pos] == 0)
          i++;
        if (i == killMan) {
          i = 0; // 重置
          break;// 找到了被杀的位置，跳出循环，进行标记
        }
      } while (true);
      man[pos] = count;
      count++;
    }
    System.out.println("我们测试结果：");
    // 显示不被杀的位置
    alive = count - alive;
    for (int j = 0; j < man.length; j++) {
      if (man[j] >= alive)
        System.out.println("不被杀的位置是->" + (j + 1));
    }
  }
}

打印出结果是:

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

赞 (0)

相关推荐

  • 图解程序员必须掌握的Java常用8大排序算法

    图解程序员必须掌握的Java常用8大排序算法

    这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序,分享给大家一起学习. 分类 1)插入排序(直接插入排序.希尔排序) 2)交换排序(冒泡排序.快速排序) 3)选择排序(直接选择排序.堆排序) 4)归并排序 5)分配排序(基数排序) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 不稳定:快速排序,希尔排序,堆排序. 先来看看8种排序之间的关系: 1.直接插入排序 (1)基本思想

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • Java遗传算法之冲出迷宫

    遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法.它能解决很多问题,比如数学方程的最大最小值,背包问题,装箱问题等.在游戏开发中遗传算法的应用也十分频繁,不少的游戏 AI 都利用遗传算法进行编码. 就个人理解,遗传算法是模拟神奇的大自然中生物"优胜劣汰"原则指导下的进化过程,好的基因有更多的机会得到繁衍,这样一来,随着繁衍的进行,生物种群会朝着一个趋势收敛.而生物繁衍过程中的基因杂交和变异会给种群提供更好的基因序列

  • java LRU算法介绍与用法示例

    java LRU算法介绍与用法示例

    本文实例讲述了java LRU算法介绍与用法.分享给大家供大家参考,具体如下: 1.前言 在用户使用联网的软件的时候,总会从网络上获取数据,当在一段时间内要多次使用同一个数据的时候,用户不可能每次用的时候都去联网进行请求,既浪费时间又浪费网络 这时就可以将用户请求过的数据进行保存,但不是任意数据都进行保存,这样会造成内存浪费的.LRU算法的思想就可以运用了. 2.LRU简介 LRU是Least Recently Used 近期最少使用算法,它就可以将长时间没有被利用的数据进行删除. LRU在人们

  • 使用java自带des加密算法实现文件加密和字符串加密

    复制代码 代码如下: import java.io.ByteArrayInputStream;import java.io.ByteArrayOutputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.InputStream;import java.io.OutputStream;import java.security.SecureR

  • java字符串相似度算法

    本文实例讲述了java字符串相似度算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class Levenshtein {     private int compare(String str, String target) {         int d[][]; // 矩阵         int n = str.length();         int m = target.length();         int i; // 遍历str的      

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • 十种JAVA排序算法实例

    排序算法有很多,所以在特定情景中使用哪一种算法很重要.为了选择合适的算法,可以按照建议的顺序考虑以下标准: (1)执行时间 (2)存储空间 (3)编程工作  对于数据量较小的情形,(1)(2)差别不大,主要考虑(3):而对于数据量大的,(1)为首要. 一.冒泡(Bubble)排序 复制代码 代码如下: void BubbleSortArray() {       for(int i=1;i<n;i++)       {         for(int j=0;i<n-i;j++)       

  • Java使用DFA算法实现过滤多家公司自定义敏感字功能详解

    Java使用DFA算法实现过滤多家公司自定义敏感字功能详解

    本文实例讲述了Java使用DFA算法实现过滤多家公司自定义敏感字功能.分享给大家供大家参考,具体如下: 背景 因为最近有通讯有个需求,说需要让多家客户公司可以自定义敏感词过滤掉他们自定义的规则,选择了DFA算法来做,不过和以前传统了DFA写法不太一样了 模式图 直接上代码 public class KeywordFilter { // private static ReentrantReadWriteLock lock = new ReentrantReadWriteLock(); public

  • 浅谈java实现背包算法(0-1背包问题)

    0-1背包的问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题.问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高.问题的名称来源于如何选择最合适的物品放置于给定背包中. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放. 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是: f[i][v]=max{ f[i-1][v], f

随机推荐