***組合數***（C語言）
題目：求組合數C(N,M)，以及C(N,M)因子個數，
要求：
輸入格式
N和M，其中0<=M<=N<=50,以EOF結束，
輸出格式
該組合數結果
怎么說，這個題目看起來不難，可是我卻交了無數次，一直時間超限
哎 ，嘆口老氣，
看看我的代碼，能過能過
#include<stdio.h>
int a[60]={0};//全域變數，放質因子
//定義函式求質因子和因子
long long int fun(int x,int y)
{
memset(a,0,sizeof(a));
//printf("%d %d\n",a[2],a[7]);
for(int i=x;i>=x-y+1;i–)
{
int t=i;
for(int j=2;j<=t;j++)
{
while(t%j0)
{
a[j]++;
t=t/j;
}
}
}//求出分母的質因子
//printf("%d %d\n",a[2],a[7]);
for(int i=y;i>=2;i–)
{
int t=i;
for(int j=2;j<=t;j++)
{
while(t%j0)
{
a[j]–;
t=t/j;
}
}
}//減去分子的質因子
//printf("%d %d\n",a[2],a[7]);
//2 7 是組合數的質因子
long long int ans=1;
for(int i=2;i<60;i++)//求組合數
{
if(a[i]!=0)
{
for(int j=1;j<=a[i];j++)
{
ans=ans*i;
}
}
}
return ans;//回傳其組合數
}
int main()
{
int x,y;
while(~scanf("%d%d",&x,&y))
{
long long int f=fun(x,y),ans1=1;
for(int i=1;i<60;i++)
{
if(a[i]!=0)
{
ans1=ans1*(a[i]+1);
}
}//計算其因子數
printf("%d %d\n",f,ans1);
}
}
快快，我來解釋一下
我是在自定義函式中求得組合數
組合數在求解程序中由兩部分組成：分母和分子
如C（8，3）
分子是876
8的質因子有三個2，7的質因子為一個7，6的質因子為一個2一個3，
所以統計分母為四個2，一個3，一個7；
再統計分母123，最后個數相減為一個7，三個2；
就可以求組合數了，2227；
因子個數 （1+1）（3+1）；
還有一些看起來很厲害的方法，可是不能過
如下：
C（a,b)=C(a-1,b-1)+C(a-1,b);這個可以用遞回實作，如果那個題目要使用遞回的話，
下面這個是求因子的另一種方法的代碼，不是上面的
for(i=1;i*i<=h;i++)
{
if(h%i==0)
{
b[now++]=i;
if(i!=h/i)
b[now++]=h/i;
}
這個now就是因子個數，還是有點六；（我覺得）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241937.html
標籤：其他
上一篇：DevExpress Winform ProgressBarControl 修改進度條顏色
下一篇：3D數學中，關于矩陣變換意義