UVA10375 Choose and divide 組合數

編輯：關於Android編程

題意很簡單，求兩個組合數相除，數字有點大，想要直接求是不可能的，只能想辦法化簡或者其它辦法，基礎可能打的不是很結實，一開始想不出，有點想要把除法變成乘法，然後約分，這樣不太現實，萬一p,q很大，r,s很小還是有可能超的，感覺這道題目比較好的，思路有點活，最後想出來還是覺得題目比較奇妙的，題目給的

m!
C(m,n) = -------------
n!(m-n)!

事實上在看白書的時候裡面數學基礎知識那裡有個介紹的，還可以寫成

m*(m-1)*(m-2)...(m-n+1)
C(m,n) = ------------------------------------

然後進一步我們可以發現，觀察一下，分母階乘化簡開來，項數為n項，分子我們仔細看看，從m乘到(m-n+1)，實際上項數（m-(m-n)）也就是n項，意思是這個分式的分子項數和分母項數是一樣的，那麼就可以利用一乘一除的方法來進行求解了，

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;
//

int main()
{
	int p,q,r,s;
	while(scanf("%d %d %d %d",&p,&q,&r,&s)==4)
	{
		int max1=max(p-q,q);
		int max2=max(r-s,s);
		int maxn=max(max1,max2);
		double ans=1.00000;
		for(int i=1;i<=maxn;i++)
		{
			if(i<=max1)
				ans=ans/i*(p-max1+i);
			if(i<=max2)
				ans=ans/(r-max2+i)*i;
		}
		printf("%.5lf\n",ans);
	}

	return EXIT_SUCCESS;
}

上一頁:說說android端實現Airplay多屏互動（一）
下一頁:android 窗口小部件（例子）

關於Android編程