论坛首页 海阔天空论坛

以傻子坐飞机问题论新手如何解算法题

浏览 10737 次
精华帖 (0) :: 良好帖 (0) :: 灌水帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2007-07-19  
package test;

import java.util.Random;

public class Test {

	private static final int MAX = 99;

	/**
	 * 2007-7-15 下午05:36:02
	 */

	/**
	 * @author <a href="mailto:guileen@gmail.com">桂健雄</a>
	 * @since 2007-7-15
	 */
	boolean[] sited = new boolean[MAX+1];

	int emptySitCount = MAX+1;

	void trySit(int sitNum) {
		if (sited[sitNum]) {
			ranSit();
		} else {
			sit(sitNum);
		}
	}

	/**
	 * 
	 * @param sitNum
	 */
	void sit(int sitNum) {
		sited[sitNum] = true;// 坐下来
		emptySitCount--;
	}

	/**
	 * 随便坐个位子
	 * 
	 */
	void ranSit() {
		int x = rand.nextInt(emptySitCount);
		int c = -1;
		for (int i = 0; i < MAX+1; i++) {
			if (!sited[i]) {
				c++;
				if (c == x) {
					sit(i);
					break;
				}
			}
		}
	}

	/**
	 * 
	 * @return 第一百个人是否做到了自己的位子
	 */
	boolean testSit() {
		// 初始化
		for (int i = 0; i < MAX+1; i++) {
			sited[i] = false;
		}
		emptySitCount = MAX+1;
		// 傻子,随便坐个位置
		ranSit();
		for (int i = 1; i < MAX; i++) {
			trySit(i);
		}
		return sited[MAX];
	}

	public static void main(String[] args) {
		Test f = new Test();
		int success = 0;
		for (int i = 0; i < 1000000; i++) {
			if (f.testSit())
				success++;
		}
		double rate = (double) success / 1000000;
		System.out.println("run:10000 times,success:" + success + " rate:"
				+ rate);
	}

	Random rand = new Random();

}


吧jasongreen的例子改了一下,抽出了常量99(100)
结果发现,输出结果,不受这个坐位数量影响。
这个明显是不对的。

jasongreen的程序有问题?我改错了?
0 请登录后投票
   发表时间:2007-07-19  
这题 的做法
是用随机数来完成概率题的标准作法

1:写出一个旅客座飞机的过程
之后把随机数带入就可以了

作出一个旅客的类
有一个动作就是找坐;
当座上有客人时
就用随机数,
还有就再用,

每次得到第100人上飞机的第一次选择是否有人
就可以了。

再之后循环个上百万次就可以了
0 请登录后投票
   发表时间:2007-07-20  
不是50%吗
傻子坐的位置有3种可能:傻子自己的位置;最后一个人的位置;其他位置
若为1,则return true
若为2,则return false
若为3,则被傻子占了位子的人变成傻子,再次重复这3种可能
而出现1和2的概率是相同的
0 请登录后投票
   发表时间:2007-07-20  
package com.maodajun.javaeye2;

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

public class FoolByPlan {
	static final int PLANSIZE =100;
	static Random random= new Random();  
	 List plan  = null;
	 List passenger =null;
	public FoolByPlan(){
		plan = new ArrayList();
		passenger = new ArrayList();
		for(int i = 0 ; i < PLANSIZE ; i++){
			plan.add("-1"); 
			passenger.add(i+"");
		}
		
	}
	/**
	 * 看看本座位是否被占,
	 * 如果没被占则旅客坐在坐位上
	 * @param block     座位号
	 * @param passenger 乘客号
	 * @return 
	 * @throws Exception 
	 */
	public boolean findBlock(int block,String passengerz) {
		if(plan.get(block).equals("-1")){
			sitBlock(block,passengerz);
			return true;
		}if(plan.indexOf("-1")<0){
			throw new RuntimeException("Out of List");
		}
		
		return false;

	}
	public void sitBlock(int block,String passengerz){
		plan.set(block,passengerz);
	}
	/**
	 * 找到空座位
	 * @param passengerz
	 */
	public void radomBlock(String passengerz){
		int block = Integer.parseInt(passengerz);
		
		while(!findBlock(block ,passengerz)){
			block = random.nextInt(PLANSIZE);			
		}
	}
	/**
	 * 重构到内部的
	 * 傻子找座
	 *
	 */
	public void foolBlock() {
		findBlock(random.nextInt(PLANSIZE),"fool");		
	}
	/**
	 * 最后一人是否有座
	 *
	 */
	public boolean lastBlock(){
		for(int i = 1 ; i < PLANSIZE -1; i++){
			radomBlock(""+i);
		}
		return findBlock(PLANSIZE-1,""+(PLANSIZE-1));
	}
	public static void main(String[] arg){
		int findit =0;
		int notfindit = 0;
		
		for(int i = 0 ; i <100000 ; i ++){
			FoolByPlan fool = new FoolByPlan();
			fool.foolBlock();
			if(fool.lastBlock()){
				findit ++;				
			}else{
				notfindit++;
			}
			System.out.println(fool.plan);

		}
		System.out.println(findit+"/"+notfindit);
	}
}


测试:
package com.maodajun.javaeye2;



import java.util.Iterator;

import junit.framework.TestCase;

public class FoolByPlanTest extends TestCase {
	private FoolByPlan foolbyplan ;
	public static void main(String[] args) {
		junit.textui.TestRunner.run(FoolByPlanTest.class);
	}

	protected void setUp() throws Exception {
		super.setUp();
		foolbyplan =  new FoolByPlan();
		
	}

	protected void tearDown() throws Exception {

		System.out.println( foolbyplan.passenger);
	
		System.out.println(foolbyplan.plan);
		super.tearDown();
	}

	/*
	 * Test method for 'com.maodajun.javaeye2.FoolByPlan.findBlock(int, int)'
	 */
	public void testFindBlock() {
		
		assertTrue(foolbyplan.findBlock(0,"11"));
		assertFalse(foolbyplan.findBlock(0,"12"));
		

	}
	public void testRadomBlock() {
		
		foolbyplan.radomBlock("5");
		foolbyplan.radomBlock("5");
		foolbyplan.radomBlock("5");
		
		Iterator it = foolbyplan.plan.iterator();
		String str ;
		int count = 0 ;
		while(it.hasNext()){
			str = it.next().toString();
			if(str.equals("5")){
				count++;
			}
		}
		assertEquals(3, count);

	}
	public void testRadomBlockTooLarge() {
		try{
			for(int i  = 0 ; i< FoolByPlan.PLANSIZE+1 ; i ++){
				foolbyplan.radomBlock("5");
			}
			fail();
		}catch(RuntimeException e){
			assertEquals("Out of List",e.getMessage());
		}
	}
	public void testFoolBlock(){
//		foolbyplan.foolBlock();//怎么测试呢?
	}
	public void testLastBlockRight(){
		foolbyplan.findBlock(0,"0");
		assertTrue(foolbyplan.lastBlock());
		
	}
	public void testLastBlockWrong(){
		foolbyplan.findBlock(foolbyplan.PLANSIZE-1,"0");
		assertFalse(foolbyplan.lastBlock());
		
	}
}

0 请登录后投票
   发表时间:2007-07-27  
jindw 写道


吧jasongreen的例子改了一下,抽出了常量99(100)
结果发现,输出结果,不受这个坐位数量影响。
这个明显是不对的。

jasongreen的程序有问题?我改错了?


这个结果的确是不受座位数量影响的。
0 请登录后投票
   发表时间:2007-07-28  
是的用我写的程序把常量改一下就可以了。。。
不过有谁能把我写的程序改一下
让傻子不是一号乘客?()
0 请登录后投票
   发表时间:2007-07-28  
jasongreen 写道
jindw 写道


吧jasongreen的例子改了一下,抽出了常量99(100)
结果发现,输出结果,不受这个坐位数量影响。
这个明显是不对的。

jasongreen的程序有问题?我改错了?


这个结果的确是不受座位数量影响的。


是我想错了,而且我原来那个程序也是错的。

看到gof95的分析,令我豁然开朗,^_^

gof95 写道
不是50%吗
傻子坐的位置有3种可能:傻子自己的位置;最后一个人的位置;其他位置
若为1,则return true
若为2,则return false
若为3,则被傻子占了位子的人变成傻子,再次重复这3种可能
而出现1和2的概率是相同的
0 请登录后投票
论坛首页 海阔天空版

跳转论坛:
Global site tag (gtag.js) - Google Analytics