回复概率问题

iwantnon 2009-05-24 03:23:55

原帖：http://topic.csdn.net/u/20090518/21/8b96f19a-af92-4eb8-8021-2977c29f27d2.html#replyachor
本来想暑假回来再回帖，没想到帖子现在就结了。
大概看了一下，感觉其中tian428的回复较有意义：
[Quote=引用 37 楼 tian428 的回复:]
C/C++ codedouble f(int r, int b)
{
if(r>b)
return 0;
if(r==0)
return 1;
return (f(r-1, b-1)*r+f(r, b-2)*b)/(r+b);
}

写成递归代码貌似就几行...
测试
[tian@localhost ctest]$ ./a.out 3 10
0.207792
[tian@localhost ctest]$ ./a.out 2 3
0.133333
[tian@localhost ctest]$ ./a.out 3 4
0.057143
[/Quote]
之所以说有意义，是因为给出了得数，而有了得数，就能够很轻易地驳倒那些一直在试图给出数学表达式的朋友了。
[Quote=引用 56 楼 tian428 的回复:]
引用 43 楼 morilasi 的回复:
测个1000以上的数据试试？
不加备忘录是不行滴

别说1000了,上几十我那个递归就不行了;只这是个求值的题,怎么递归都是很慢很大的,最快的计算方法就是推出通项公式直接套公式
[/Quote]
恩，动态规划问题肯定能用递归解，只不过效率就低了。
这道题说来说去终归是一个马尔可夫链（或者说动态规划）问题，所以正规的解决法当就是用动态规划了。

...全文

112 6 打赏收藏转发到动态举报

写回复

用AI写文章

6 条回复

切换为时间正序

请发表友善的回复…

发表回复

iwantnon 2009-05-28

打赏
举报

宿舍网到期了，快一个星期了还没有续上。
各位先研究吧，我失陪几天。

iwantnon 2009-05-28

打赏
举报

[Quote=引用 3 楼 litaoye 的回复:]
不知道数再大点会怎么样,200毕竟太小了,试试10^6以上吧!

用dp感觉应当是个O(n)的算法,如果可以转化为通过某个关于(m,n)的公式求解的话,是有可能log(n)的!
[/Quote]
线性复杂度不是已经很好了吗？已经可以满足应用。
200*200时可以瞬间得出结果，如果要弄更大的数，等待一下就行了。
理论上马尔可夫链都可以求出数学解（写出转移矩阵，然后求矩阵的幂的通式），但是实际上好像没有多少这样做的，都是用数值算，我想原因还是因为算法本身复杂度不很高，所以没必要求符号解吧。
也许我一楼的算法还不够好，大家可以继续研究，不过我认为推数学公式的路子是不可取的，因为方法缺乏一般性，应用面太窄，也与论坛主题不符。

捧剑者 2009-05-25

打赏
举报

绿色夹克衫 2009-05-24

打赏
举报

不知道数再大点会怎么样,200毕竟太小了,试试10^6以上吧!

用dp感觉应当是个O(n)的算法,如果可以转化为通过某个关于(m,n)的公式求解的话,是有可能log(n)的!

acdbxzyw 2009-05-24

打赏
举报

顶，楼主好样的。

iwantnon 2009-05-24

打赏
举报

#include <iostream.h>

template <typename T>

T** new2(int m,int n,const T&valu)//动态创建二维数组

{

	int i,j;

	T **p;

	p=new T*[m];

	for(i=0;i<=m-1;i++)

	{

		p[i]=new T[n];

	}

	for(i=0;i<=m-1;i++)

	{

		for(j=0;j<=n-1;j++)

		{

			p[i][j]=valu;

		}

	}

	return p;

}

template <typename T>

delete2(T**p,int m,int n)//销毁由new2创建的二维数组

{

	for(int i=0;i<=m-1;i++)

	{

		delete []p[i];

	}

	delete []p;

}

template <typename T>

init2(T**p,int m,int n,const T&valu)//二维数组初始化

{	

	int i,j;

	for(i=0;i<=m-1;i++)

	{

		for(j=0;j<=n-1;j++)

		{

			p[i][j]=valu;

		}

	}

}

template <typename T>

copy(T**p,T**tp,int m,int n)//拷贝二维数组

{

	int i,j;

	for(i=0;i<=m-1;i++)

	{

		for(j=0;j<=n-1;j++)

		{

			p[i][j]=tp[i][j];

		}

	}

}

double dp(int m,int n)//计算概率

{

	int i,j;

	double**p=new2(m+1,n+1,(double)0);

	double**tp=new2(m+1,n+1,(double)0);

	p[m][n]=1;

	bool Aturn=true;

	double rsp=0;

	while(1)

	{

		if(Aturn)

		{

			init2(tp,m+1,n+1,(double)0);

			bool finish=true;

			rsp+=p[0][1];

			p[0][1]=0;

			for(i=0;i<=m;i++)

			{

				for(j=0;j<=n;j++)

				{

				

					if(p[i][j]!=0)

					{

						if(i-1>=0)tp[i-1][j]+=i*1.0/(i+j)*p[i][j];

						if(j-1>=0)tp[i][j-1]+=j*1.0/(i+j)*p[i][j];

						finish=false;

					}

				}

			}

			if(finish)

			{

				break;

			}

			copy(p,tp,m+1,n+1);

			Aturn=false;

		}else

		{

			init2(tp,m+1,n+1,(double)0);

			bool finish=true;

			rsp+=p[0][1];

			p[0][1]=0;

			for(i=0;i<=m;i++)

			{

				for(j=0;j<=n;j++)

				{

				

					if(p[i][j]!=0)

					{

						if(j-1>=0)tp[i][j-1]+=p[i][j];

						finish=false;

					}

				}

			}

			if(finish)

			{

				break;

			}

			copy(p,tp,m+1,n+1);

			Aturn=true;

		}

	}

	delete2(p,m+1,n+1);

	delete2(tp,m+1,n+1);

	return rsp;

}

main()

{

	int m,n;

	cout<<"m:";

	cin>>m;

	cout<<"n:";

	cin>>n;

	cout<<dp(m,n)<<endl;

}

测试：
m:3
n:10
0.207792
Press any key to continue
m:2
n:3
0.133333
Press any key to continue
m:3
n:4
0.0571429
Press any key to continue
可见，与37楼n428的结果相同。下面是几个较大的数：
m:38
n:59
5.04079e-008
Press any key to continue
m:200
n:200
6.22302e-061
Press any key to continue
m:200
n:201
3.8924e-062
Press any key to continue
都能瞬间得出，所以用动态规划效率还是很高的。