MyException - 我的异常网
当前位置:我的异常网» 综合 » 以傻子坐飞机有关问题论新手怎么解算法题

以傻子坐飞机有关问题论新手怎么解算法题

www.MyException.Cn  网友分享于:2013-10-27  浏览:2次
以傻子坐飞机问题论新手如何解算法题
概率论没学好,这题数学方法求解失败了,所以选择了用程序模拟,当是玩玩。
对模拟现实事件的代码,很多新手会觉得茫然,其实只要把大问题拆成小问题,一切就ok了。
PS:边编码,边思考,前后不超过5分钟。嘻嘻。
不废话,看题:

100个人排队乘坐有100个座位的飞机,正常情况时每个都都会对号入坐,但是,第一个上飞机的是个傻子,他随机坐了一个位子,接下来的人上飞机时,如果自己座位被人坐了就会随机找个座位坐下,否则就坐自己坐位。问题:最后一个上飞机的人坐到自己座位的概率是多少??

第一步:建一个项目,一个类,废话。
第二步:有几个东西需要表示
a, 100个位子。把他编号为0~99。常量
b, 100个人。把他们编号为0~99。常量
b, 哪个人坐哪个位子。人和位子的编号一一对应。常量
c, 位子上有没有坐人。在程序中定义一个 boolean sited[]=new boolean[100];变量

第三步:有几个动作要表示
a, 坐到某个位子上,写个方法,sit(int sitNum);
b, 随便坐个位子,写个方法,randSit(),
c, 尝试坐到某个位子上,被坐了就随便坐个位子,写个方法,trySit(int num);
PS:我是先写上方法的定义,后面才写代码的,要首先从宏观的角度思考问题,然后再深入细节。

第四步:求解
a, 模拟100个人上飞机的过程,并返回最后一个人是不是坐到他自己的位子
b,计算1000000次,计算成功次数。

把每个方法实现,代码就完成了。把大问题拆解成小问题,问题就可以迎刃而解。就象画画,新手总是直接画鼻子画眼,会画的都是,先勾勒个轮廓。看到很多新手遇到复杂问题会很茫然,希望我的话能对他们有所帮助。
代码:
import java.util.Random;

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

/**
 * @author <a href="mailto:guileen@gmail.com">桂健雄</a>
 * @since 2007-7-15
 */
public class FoolSit {
	boolean[] sited=new boolean[100];
	int emptySitCount = 100;
	
	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<100;i++){
			if(!sited[i]){
				c++;
				if(c==x){
					sit(i);
					break;
				}
			}
		}
	}
	
	/**
	 * 
	 * @return 第一百个人是否做到了自己的位子
	 */
	boolean testSit(){
		//初始化
		for(int i=0;i<100;i++){
			sited[i] = false;
		}
		emptySitCount = 100;
		
		//傻子,随便坐个位置
		ranSit();
		for(int i=1;i<99;i++){
			trySit(i);
		}
		return sited[99];
	}
	
	public static void main(String[] args) {
		FoolSit f = new FoolSit();
		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();
	
	
}
1 楼 rocks 2007-07-15  
这个问题的数学解和概率论有多大关系?我给个数学解吧。
假设从1号开始到100号依次上飞机。1号是傻子,如果1号直接做到1号位置,那么,最后一人肯定能坐自己的座位,如果1号坐在100号,那么最后一个人一定上不了自己的座位。如果1号选中m号,那么到m-1前的人都会坐在自己位置上,如果到底m个人上来的时候,他又面临一次选择。如果到他坐0到1号,ok,后面按顺序,如果他坐到100号,没戏,如果他做到m+n号,那么到m+n-1的人都按顺序的。
好,我们反过来想,最后一个坐不到自己位子的概率是多少呢?他坐不到一定是因为前面某个人坐不到自己的位子导致被人坐了他的位子。我们设fx(m)为第m个人坐不到自己的位子的概率。
从fx(2)开始考虑:fx(2)=0.01。那么fx(3)=0.01+fx(2)*1/99 //被第一人坐了自己的位子+被第二个人坐了
fx(4)=0.01+fx(2)*1/99+fx(3)*1/98;   //被第一个+第二个+第三个人坐了。
fx(5)=0.01+fx(2)*1/99+fx(3)*1/98+fx(4)*1/97;
朋友看到这里,应该看出递推关系了吧。fx(2)=0.01,fx(3)=(1+1/99)*fx(2)
也就是说fx(m)=(1+1/(102-m))*fx(m-1)//数学归纳法证明就免了吧。太无聊了。谁有空给证一下好了。
fx(4)=(1+1/98)*fx(3)=(1+1/98)(1+1/99)(1/100)

同理fx(100)=(1+1/2)(1+1/3)(1+1/4)....(1+1/99)(1/100)=3/2*4/3*5/4*....*100/99*1/100
同志们,看到这个式子,是不是很兴奋?
发现fx(100)=0.5,那么我们求什么呢?最后一个坐到自己的位子上。很简单就是1-fx(100)=0.5
2 楼 庄表伟 2007-07-15  
rocks 写道
如果1号坐在100号,那么最后一个人一定上不了飞机。


这句以后的分析,就不必再看了。
3 楼 rocks 2007-07-15  
庄表伟 写道
rocks 写道
如果1号坐在100号,那么最后一个人一定上不了飞机。


这句以后的分析,就不必再看了。

口误+笔误。。。。。
4 楼 yimlin 2007-07-15  
晕,还分析了半天,
只有一个结果,坐到自己座位和没有坐到, 几率对半开!
5 楼 抛出异常的爱 2007-07-16  
yimlin 写道
晕,还分析了半天,
只有一个结果,坐到自己座位和没有坐到, 几率对半开!
应该这么分析

1.傻子坐对了 1%
2.傻子坐错了 99%

傻子侍错了:
1.第两人坐了100号 1/99
2.第两人坐了非100号 98/99

第二个人坐了100号
1.第三个人坐了100 1/98
2.第三个人坐了傻子的位置 1/98
3.第三个人坐了其它位置 97/98

。。。。。。。。。。。。
第一百人上了飞机
只可能有两个位置
一个是傻子的位置
另一个是100号的位置
6 楼 jindw 2007-07-19  
我想应该可以这样:
var n0 = 99% * (1/100-1) //傻子直接占上自己的坐位的概率
var n1= n0 //第一个正常人坐位被占的概率
var n2= n0+n1*(1/100-2)
var n3= n0+n1*(1/100-2)+n2*(1/100-3)
...
var n99=n0+n1*(1/100-2)+n2*(1/100-3)+.....
7 楼 jindw 2007-07-19  
var MAX = 99
var rates = [(MAX/(MAX+1)) * (1/MAX)];
for(var i=1;i<=MAX;i++){
  var x = rates[0];
  for(var j = 1;j<i;j++){
    x+=rates[j]*(1/(MAX-j))
  }
  rates[i] = x;
}

document.write(rates.join('\n'))


不过,结果和jasongreen的差别太大,不知道错在那里。


.....
0.2475
0.32999999999999996
0.49499999999999994
0.9899999999999999

第99个人的概率倒是挺相近的。
晚上再查查,问题到底出在那里:)
8 楼 抛出异常的爱 2007-07-19  
99%
哪出来的?
9 楼 jindw 2007-07-19  
傻子坐到别人的坐位的概率是
(99/100)
坐上某个指定的位置是(99/100)*(1/99)『不就是1/100吗?当时怎么就每转过弯来,倒霉』
10 楼 jindw 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的程序有问题?我改错了?
11 楼 抛出异常的爱 2007-07-19  
这题 的做法
是用随机数来完成概率题的标准作法

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

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

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

再之后循环个上百万次就可以了
12 楼 gof95 2007-07-20  
不是50%吗
傻子坐的位置有3种可能:傻子自己的位置;最后一个人的位置;其他位置
若为1,则return true
若为2,则return false
若为3,则被傻子占了位子的人变成傻子,再次重复这3种可能
而出现1和2的概率是相同的
13 楼 抛出异常的爱 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());
		
	}
}

14 楼 jasongreen 2007-07-27  
jindw 写道


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

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


这个结果的确是不受座位数量影响的。
15 楼 抛出异常的爱 2007-07-28  
是的用我写的程序把常量改一下就可以了。。。
不过有谁能把我写的程序改一下
让傻子不是一号乘客?()
16 楼 jindw 2007-07-28  
jasongreen 写道
jindw 写道


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

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


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


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

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

gof95 写道
不是50%吗
傻子坐的位置有3种可能:傻子自己的位置;最后一个人的位置;其他位置
若为1,则return true
若为2,则return false
若为3,则被傻子占了位子的人变成傻子,再次重复这3种可能
而出现1和2的概率是相同的

文章评论

我是如何打败拖延症的
我是如何打败拖延症的
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
如何成为一名黑客
如何成为一名黑客
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员必看的十大电影
程序员必看的十大电影
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
10个调试和排错的小建议
10个调试和排错的小建议
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
代码女神横空出世
代码女神横空出世
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员都该阅读的书
程序员都该阅读的书
鲜为人知的编程真相
鲜为人知的编程真相
老程序员的下场
老程序员的下场
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员的鄙视链
程序员的鄙视链
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我的丈夫是个程序员
我的丈夫是个程序员
那些争议最大的编程观点
那些争议最大的编程观点
一个程序员的时间管理
一个程序员的时间管理
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员应该关注的一些事儿
程序员应该关注的一些事儿
中美印日四国程序员比较
中美印日四国程序员比较
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
编程语言是女人
编程语言是女人
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
每天工作4小时的程序员
每天工作4小时的程序员
漫画:程序员的工作
漫画:程序员的工作
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
 程序员的样子
程序员的样子
Java程序员必看电影
Java程序员必看电影
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有