递归完美解决"傻子造成的问题" :)
昨天晚上快睡觉的时候在这里看到了这样的一个帖子,问题是:
"100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个傻子，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。问题：最后一个上飞机的人坐到自己座位的概率是多少？？ "
我对此特别感兴趣就想了一个晚上,算是找到了自己比较满意的答案0.5.虽然我看到回帖的人中有很多都说的是0.5,但是我是有我自己的解决思路,在这里拿出来和大家一起探讨一下;有什么不对的地方希望大家多指教.如果你能指出我解答之中的错误请给我指出来，送8分。
考虑一般的问题,不管一共有多少人,设为n个人,n个位置.
反面考虑,和有的人一样求最后一个人(即第n个人)不能坐到自己位置的概率为P(n);
设倒数第二个人不能坐到自己位置的概率为P(n-1),
则P(n) = P(n - 1) + (1/(n - (n - 1) + 1)) * P(n - 1);
第一个人不能坐到自己的位置的概率显然是(n-1)/n;
第二个人不能坐到自己的位置的概率是:1/n (只有傻子可能坐他的位置);
即这些人中第k个人(k <= n && k > 2)不能坐到自己的位置是;
P(k) = P(k-1)+{1/[n-(k-1)+1]}*P(k-1);
用数学规纳法证明（我其实是通过一般的情况才看出来的这个规律）：
证:
最基本的情况就是当k=3的时候;
第三个人的位置只可能被第一个人坐和被第二个人坐；
1.当被第一个人坐时，而第二个人坐自己的位置概率为(1/n)*1;
2.当被第二个人坐时，肯定第一个人把第二个人的位置坐了第二个人再把
三个人的位置坐了(第二个人坐的时候有n-1个位置他可以随便选)，
则概率为：(1/n)*[1/(n-1)] = {1/[n-(3-1)+1]}*P(2);
则第三个人不能坐到自己位置的概率为;(1/n)+{1/[n-(3-1)+1]}*(1/n);
即：P(3) = P(2)+{1/[n-(3-1)+1]}*P(2);
假设第k个人不能坐到自己的位置的概率P(k)=P(k-1)+{1/[n-(k-1)+1]}*P(k-1)成立;
则第k+1个人的位置让别人坐了的概率为P(k+1);
第k+1个人的位置只可能让他前面的k个人给坐了，有两种情况：
1.可能把第k个人的位置坐了的前k-1个人中的一个坐了他的位置，则第k个人
肯定坐自己的位置。显然这部分的概率和第k个人的位置被坐的概率一样即
为：P(k);
2.可能就是第k个人把他的位置给坐了，那肯定第k个人的位置就是让前k-1个
中的一个家伙给坐了概率为P(k),而第k个人又把第k+1个人的位置坐了概率
1/(n-k+2)(当第k个人坐的时候有n-k+1个位置随便他选).则这部分的概率
为：P(k)*[1/(n-k+1)];
则第k+1个人的位置让别人坐了的概率为：P(k)+P(k)*[1/(n-k+1)];
即：P(k+1)=P(k+1-1)+{1/[n-(k+1-1)+1]}P(k+1-1);
综上可得100个人中任意第n个人位置被坐的概率
P(n)=P(n-1)+{1/[100-(n-1)+1]}*P(n-1);
做递归计算程序如下(相信特别的简单了吧)
//自定义头文件
#ifndef CH_H
#define CH_H
double P(float);//计算在给定人数情况下最后一个人位置被坐的概率
#endif
//ch.cpp文件，定义函数double P(float)
#include "stdafx.h "
#include "ch.h "
double P(float n) //参数n为上飞机和位置的总数
{
if(n == 1)
return (n - 1) / n;
else if(n == 2)
return 1 / n; //结束条件
else
return P(n - 1) + (1/2) * P(n - 1); //递归调用
}
// fool.cpp : Defines the entry point for the console application.
//
#include "stdafx.h "
#include <iostream.h>
#include "ch.h "
int main(int argc, char* argv[])
{
float n; //第N个人的编号吧
char flag;
do
{
cout < < "请输入你要知道的总人数n: ";
cin > > n;
cout < < endl < < "则最后一个人能坐到自己位置的概率是： ";
cout < < 1 - P(n) < < endl < < endl;; //第N个人能坐到自己的位置的概率
cout < < "还要计算下一个人的概率吗？Y/N -> ";
cin > > flag;
cout < < endl;
}while(flag == 'Y ' || flag == 'y ');
return 0;
}
希望大家能和我多交流，我学得的东西很少，希望大家多多指教。小弟先谢谢了。
[解决办法]
我不管你分析得对不对,但是你这个地方错了.
double P(float n) //参数n为上飞机和位置的总数
{
if(n == 1)
return (n - 1) / n;
else if(n == 2)
return 1 / n; //结束条件
else
return P(n - 1) + (1/2) * P(n - 1); //递归调用
}
----------------------------------------------------
最后一个语句相当于 return P(n - 1); 因为(1/2) = 0;
所以你算出来的是0.5.
----------------------------------------------------
把分全给我吧.
