`

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

算法junitCC++C# 
阅读更多
概率论没学好，这题数学方法求解失败了，所以选择了用程序模拟，当是玩玩。
对模拟现实事件的代码，很多新手会觉得茫然，其实只要把大问题拆成小问题，一切就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();
	
	
}
分享到：
| 恋爱秘笈
评论
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的概率是相同的
15 楼 抛出异常的爱 2007-07-28  
是的用我写的程序把常量改一下就可以了。。。
不过有谁能把我写的程序改一下
让傻子不是一号乘客？（）
14 楼 jasongreen 2007-07-27  
jindw 写道


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

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


这个结果的确是不受座位数量影响的。
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());
		
	}
}
12 楼 gof95 2007-07-20  
不是50%吗
傻子坐的位置有3种可能：傻子自己的位置；最后一个人的位置；其他位置
若为1，则return true
若为2，则return false
若为3，则被傻子占了位子的人变成傻子，再次重复这3种可能
而出现1和2的概率是相同的
11 楼 抛出异常的爱 2007-07-19  
这题 的做法
是用随机数来完成概率题的标准作法

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的程序有问题？我改错了？
9 楼 jindw 2007-07-19  
傻子坐到别人的坐位的概率是
(99/100)
坐上某个指定的位置是（99/100）*(1/99)『不就是1/100吗？当时怎么就每转过弯来，倒霉』
8 楼 抛出异常的爱 2007-07-19  
99%
哪出来的？
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个人的概率倒是挺相近的。
晚上再查查，问题到底出在那里：）
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)+.....
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号的位置
4 楼 yimlin 2007-07-15  
晕,还分析了半天,
只有一个结果,坐到自己座位和没有坐到, 几率对半开!
3 楼 rocks 2007-07-15  
庄表伟 写道
rocks 写道
如果1号坐在100号，那么最后一个人一定上不了飞机。


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

口误+笔误。。。。。
2 楼 庄表伟 2007-07-15  
rocks 写道
如果1号坐在100号，那么最后一个人一定上不了飞机。


这句以后的分析，就不必再看了。
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
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    Java算法集题大全.zip

    Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...

    java常见算法题解析大全。

    在这个“java常见算法题解析大全”中，你将找到一系列涵盖不同难度级别的算法问题，旨在帮助Java开发者提升技能，增强解决问题的能力。 首先，让我们了解一下折半查找（Binary Search）算法。这是一种在有序数组中...

    LetCode简单算法题 入门算法题

    算法 ,简单 入门 LeetCode网站开放的简单算法题,用于平时检验自己的算法能力,程序设计.

    C语言算法题合集.zip

    C语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法题合集.zipC语言算法...

    java笔试常见的算法题

    全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法，本人在准备笔试的时候找的，算法尽量采用最优的。 所有的代码均经过测试，个人觉得没有问题，如果哪位大牛找到错误，欢迎批评指正

    程序员的算法趣题.pdf.zip

    通过阅读《程序员的算法趣题》，读者不仅可以系统地学习和练习这些算法，还能了解到如何将理论知识应用于实际问题，从而提升自己的编程思维和问题解决能力。这本书的实践性强，适合在准备面试或日常工作中自我提升时...

    算法分析试题答案

    这意味着，二分搜索算法将问题分解成小的子问题，然后逐步解决这些子问题，以找到最优解。 第二个问题是关于动态规划算法的基本步骤，其中找出最优解的性质是动态规划算法的重要步骤之一。动态规划算法通常用于解决...

    中山大学遗传算法基本习题

    中山大学遗传算法基本习题

    软件工程师经典笔试算法题

    软件工程师经典笔试算法题 软件工程师经典笔试算法题是软件工程师面试中经常出现的算法笔试题，这篇文章将从六个方面对软件工程师经典笔试算法题进行详细的讲解。 一、将一整数逆序后放入一数组中 这个算法题考察...

    6D机器人正逆解算法（可运行）

    6D机器人正逆解算法是机器人学中的核心概念，它涉及到机器人的运动学建模和控制。6D代表六个自由度，即机器人的位置（3个笛卡尔坐标：x、y、z）和姿态（3个欧拉角或旋转矩阵表示的方位）。在这个项目中，我们看到一...

    算法设计与分析-期末考核论文.docx

    算法设计与分析是计算机科学中的一门重要课程，这门课程的主要内容是学习如何设计和分析算法，以解决计算机科学中的问题。在这篇论文中，我们将对算法设计与分析的基本概念和策略进行总结，并对贪心法进行实例研究。...

    C++面试题笔试题C++ 数据结构算法笔试题资料合集.zip

    C++面试题笔试题C++ 数据结构算法笔试题资料合集： 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....

    541127 算法新解.pdf

    本文将深入探讨算法的多个重要方面，包括初等算法、数据结构、搜索算法、树结构等，并着重介绍541127算法新解中所包含的丰富内容和创新思路。 首先，我们要明确算法的核心地位。计算机科学的基石之一便是算法，它...

    计算机算法设计与分析课后习题算法实现题1-3最多约数问题

    计算机算法设计与分析课后习题算法实现题1-3最多约数问题，标准代码

    六轴机械臂正解（FK）和逆解（IK）算法

    整理出了如下几个计算六轴机械臂正解和逆解的关键点： 01_机器人坐标系和关节的说明 02_算法坐标系的建立 03_D-H参数表的建立 04_FK（正解）算法 05_Matlab辅助计算FK（正解） 06_IK（逆解）算法 07_Matlab辅助计算...

    C++的算法题合集代码.zip

    C++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集代码.zipC++的算法题合集...

    计算机算法设计与分析试题.doc

    2. 动态规划法：这种方法用于找到最优解，通过解决子问题并存储结果以避免重复计算。动态规划通常自底向上构建最优解，例如0/1背包问题和最长公共子序列问题。动态规划的基本步骤包括定义最优解、构造最优解、算出最...

Magicbox
Global site tag (gtag.js) - Google Analytics