`
shaomeng95
  • 浏览: 221890 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

约瑟夫环问题

阅读更多

约瑟夫环是一个数学的应用问题:

写道
  已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

 如同杀人游戏啊,哈哈,假如有6个人,要杀掉5个人,从1开始报数,叫到2的杀掉,用程序怎么写呢,作为程序员的我,开始吭哧吭哧的写了,不会数学算法啊,只能用程序员的方式解决。

package com.ssm.common;

import java.util.ArrayList;
import java.util.List;

public class Josephus {

	List<Peple> pepleList = new ArrayList<Peple>();

	class Peple {
		int next;//下一个人
		int index;// 本人序号
		boolean flag = true;//是否活着
	}

	/**
	 * 杀人
	 * @param total 总人数
	 * @param killNum 需要杀死的人数
	 * @param m 报到此数将被杀死
	 */
	public void jsph(int total,int killNum,int m) {
		int startIndex = 0;//开始序号
		int count = 1;//报数开始
		int killedCount=0;//被杀的人总数

		while (killedCount<killNum) {//被杀的人数等于设定的杀人数量 则结束
			//1、判断当前这个人是否可以杀
			if (count == m)
			{
				pepleList.get(startIndex).flag = false;//杀死
				++killedCount;
				count=0;    
				System.out.println(pepleList.get(startIndex).index+" is killed");
			}
			
	        //2、找到下一个人,进行报数
			do
			{
				startIndex=pepleList.get(startIndex).next;//被杀的下一个人	
			}
			while(!pepleList.get(startIndex).flag);//循环直到找到活人
			
			//2、向下报数
			++count;

		}
		
		showResult();//显示结果
	}
	
	private void showResult()
	{
		System.out.print("\n\nresult:");
		for (int i = 0; i < pepleList.size(); i++) {
			
			if(pepleList.get(i).flag)
				System.out.print(pepleList.get(i).index+"[live] ");
			else
				System.out.print(pepleList.get(i).index+"[dead] ");
			
		}
	}
	
	/**
	 * 启动游戏
	 * @param total 总人数
	 * @param killNum 需要杀死的人数
	 * @param m 报到次数将被杀死
	 */
	public void startGame(int total,int killNum,int m) {
		System.out.println("Rule:total is "+total+",killNum is "+killNum+",callNum is "+m);
		System.out.println("\n\nInit peples...");
		for (int i = 0; i < total; i++) {
			Peple p = new Peple();
			p.index = i;// 序号
			p.next = (i == total-1) ? 0 : i+1;
			pepleList.add(p);
			System.out.print("["+p.index+"]");
		}
		
		System.out.println("\n\nGame is starting...");
		this.jsph(total,killNum,m);//杀人
	}


	public static void main(String[] args) {
		new Josephus().startGame(6, 5, 2);
	}

}

 

运行结果:
Rule:total is 6,killNum is 5,callNum is 2


Init peples...
[0][1][2][3][4][5]

Game is starting...
1 is killed
3 is killed
5 is killed
2 is killed
0 is killed


result:0[dead] 1[dead] 2[dead] 3[dead] 4[live] 5[dead]

 没学过算法设计啊,只能这么写,最后发现这个问题有个公式啊,请看http://baike.baidu.com/view/717633.htm#sub717633,最后想说的是,学好数学还是蛮有用的啊,后悔ing.

分享到:
评论
2 楼 shaomeng95 2011-04-25  
sakajiaofu 写道
这个好像就是难再了怎么去找下一个没有被杀的问题上面
下面是一个我改进的你的代码
  class Person {
    Person(int id) {
        this.id = id;
    }
    int id;
    boolean killed;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public boolean isKilled() {
        return killed;
    }

    public void setKilled(boolean killed) {
        this.killed = killed;
    }
}


    /**
     * @param total 总的人数
     * @param killNum 需要被杀掉的编号
     */
    static void killGame(int total, int killNum) {
        // 初始化所有的人数
        List<Person> list = new ArrayList<Person>();
        for (int i = 0; i < total; i++) {
            // 给每一个人一个Id
            list.add(new Person(i + 1));
        }

        int length = list.size();
        // 剩下多少人没有被杀
        int remainCount = length;
        // 下一个人在list中的索引
        int nextIndex = 0;
        // 每一次报数时候每一个人的报的号码
        int num = 1;

        Person temp;

        while (remainCount >= killNum) {
            temp = list.get(nextIndex);
            if (nextIndex == length - 1) {
                nextIndex = 0;
            }
            else {
                nextIndex++;
            }

            if (!temp.isKilled()) {
                if (num == killNum) {
                    temp.setKilled(true);
                    remainCount--;
                    num = 1;
                }
                else {
                    num++;
                }
            }
        }

        for (Person p : list) {
            if (p.isKilled()) {
                System.out.println("被杀的人的ID 是:" + p.getId());
            }
            else {
                System.out.println("活的人的ID 是:" + p.getId());
            }
        }
    }

    public static void main(String[] args) {
        killGame(7, 3);
    }



兄弟,你这代码有问题吧,你检查检查。
1 楼 sakajiaofu 2011-04-25  
这个好像就是难再了怎么去找下一个没有被杀的问题上面
下面是一个我改进的你的代码
  class Person {
    Person(int id) {
        this.id = id;
    }
    int id;
    boolean killed;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public boolean isKilled() {
        return killed;
    }

    public void setKilled(boolean killed) {
        this.killed = killed;
    }
}


    /**
     * @param total 总的人数
     * @param killNum 需要被杀掉的编号
     */
    static void killGame(int total, int killNum) {
        // 初始化所有的人数
        List<Person> list = new ArrayList<Person>();
        for (int i = 0; i < total; i++) {
            // 给每一个人一个Id
            list.add(new Person(i + 1));
        }

        int length = list.size();
        // 剩下多少人没有被杀
        int remainCount = length;
        // 下一个人在list中的索引
        int nextIndex = 0;
        // 每一次报数时候每一个人的报的号码
        int num = 1;

        Person temp;

        while (remainCount >= killNum) {
            temp = list.get(nextIndex);
            if (nextIndex == length - 1) {
                nextIndex = 0;
            }
            else {
                nextIndex++;
            }

            if (!temp.isKilled()) {
                if (num == killNum) {
                    temp.setKilled(true);
                    remainCount--;
                    num = 1;
                }
                else {
                    num++;
                }
            }
        }

        for (Person p : list) {
            if (p.isKilled()) {
                System.out.println("被杀的人的ID 是:" + p.getId());
            }
            else {
                System.out.println("活的人的ID 是:" + p.getId());
            }
        }
    }

    public static void main(String[] args) {
        killGame(7, 3);
    }


相关推荐

    循环队列和约瑟夫环问题

    循环队列和约瑟夫环问题 循环队列是一种特殊的队列结构,它的特点是队列的末尾元素连接着队列的开头元素,形成一个环形结构。这种数据结构可以用来解决约瑟夫环问题。 约瑟夫环问题是一个经典的问题,它是由古罗马...

    敢死队问题课程设计(约瑟夫环问题的应用)

    【敢死队问题(约瑟夫环问题的应用)】是一个经典的计算机科学问题,它涉及到数据结构和算法的设计。在这个问题中,M个敢死队员通过循环计数的方式决定执行任务的顺序,每数到5的人将执行任务并退出,直至只剩下一个...

    用循环链表实现约瑟夫环问题

    使用c语言中的循环链表及结构体实现约瑟夫环问题

    数据结构约瑟夫环问题

    数据结构中的约瑟夫环问题是一种经典的编程问题,它涉及到链表这一数据结构的应用。在本文中,我们将深入探讨约瑟夫环问题的背景、原理以及如何使用链表来求解这一问题,同时分析给定代码的具体实现细节。 ### ...

    约瑟夫环问题算法描述和程序实现(C#)

    约瑟夫环问题,也称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史上的一个故事。在这个问题中,人们围成一个圈,并按照一定的规则依次淘汰,最后留下来的人被称为“幸存者”。具体规则是:从...

    约瑟夫环问题用C++代码实现

    约瑟夫环问题,也称为约瑟夫问题,是一个经典的理论问题,源于古罗马时期的传说。问题描述了一群人围坐成一个圆圈,按照一定的规则进行报数,每数到特定数字的人会被排除,直到所有人都被排除。在这个场景中,我们...

    c++多种方法解决约瑟夫环问题

    多种方法解决约瑟夫环问题,1.顺序表2.循环链表3.循环队列4.普通一位数组

    约瑟夫环问题(C++)

    约瑟夫环问题,也被称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史上的一个故事。在这个问题中,人们站成一个圈,并按顺时针方向编号。从某个人开始,每隔特定的人数,这个人就会被排除出圈,...

    详细介绍约瑟夫环问题解析.docx

    约瑟夫环问题解析 约瑟夫环问题是计算机科学和数学中一个著名的问题,它是指在一个圆圈中的人按照一定的规则依次出列的问题。该问题的解析报告将从以下几个方面进行讲解: 一、问题描述 约瑟夫环问题可以用以下...

    约瑟夫环问题的编程实现

    约瑟夫环问题,也称为约瑟夫环序列或约瑟夫问题,是一个著名的理论问题,源自古罗马历史的一个故事。在数学和计算机科学中,它通常被用来演示各种算法,特别是循环移位和递归算法。这个问题描述如下:假设有一群人围...

    用C语言实现约瑟夫环问题

    《C语言实现约瑟夫环问题详解》 约瑟夫环问题,又称约瑟夫环序列,是一个著名的理论问题,源自古罗马的一个传说。在这个问题中,人们围成一个圈,按照一定的规则逐个淘汰,直到剩下最后一个人为止。这个问题在...

    约瑟夫环问题用循环队列解决

    用循环队列解决约瑟夫环问题减少用顺序表在出对是循环移动带来的空间复杂度

    1模拟轮盘抽奖游戏2模拟报数游戏(约瑟夫环问题)_抽奖轮盘_模拟报数游戏_模拟轮盘抽奖游戏_游戏_用python实现_

    在本项目中,我们将探讨如何使用Python编程语言来实现两种有趣的数学和计算机科学相关的游戏:模拟轮盘抽奖游戏和模拟报数游戏,也称为约瑟夫环问题。这两个游戏不仅有趣,而且能帮助我们理解循环、列表操作以及算法...

    约瑟夫环问题,C语言编写

    数据结构中的约瑟夫环问题 C语言编写,已经测试通过

    约瑟夫环问题的源代码(c++)

    约瑟夫环问题的源代码分析 约瑟夫环问题是计算机科学中的一种经典问题,描述的是10个小孩围坐在一圈,并给他们依次编号,指定从第s个小孩开始报数(从1~n报数),报到n的小孩出列,然后依次重复下去,直到所有的...

    C语言编写的关于约瑟夫环问题的程序

    标题中的“C语言编写的关于约瑟夫环问题的程序”指的是使用C编程语言实现的一个经典算法问题——约瑟夫环(Josephus Problem)。约瑟夫环问题是一个理论上的问题,通常在计算机科学和数学中被用作示例,以讨论和解决...

    数据结构实验报告--约瑟夫环问题

    实验报告的主题是“约瑟夫环问题”,这是一个经典的数据结构问题,源于数学家约瑟夫·弗朗西斯·里斯提出的假设情景。该问题描述了一群人围成一个圈,从某个人开始按顺时针方向依次报数,每当数到特定数值的人会被...

Global site tag (gtag.js) - Google Analytics