遞歸遞推練習–F6

    計算組合數。C(n,m),表示從n個數中選擇m個的組合數。

計算公式如下：

若：m=0，C(n,m)=1

否則， 若 n=1，C(n,m)=1

             否則，若m=n，C(n,m)=1

                         否則 C(n,m) = C(n-1,m-1) + C(n-1,m)

此題就按題目寫個簡單的遞歸函數用個二維數組記憶化處理就好了。全局數組a中用一個負數初始化

#include<iostream>
using namespace std;
int a[21][21];
int c(int n,int m)
{
	if(a[n][m]!=-1)
	{return a[n][m];}
	if(m==0||n==1||m==n)
	{a[n][m]=1;
	  return 1;}
	else
	 {a[n][m]=c(n-1,m-1)+c(n-1,m);
	return a[n][m];}
}
int main()
{
	int b[100],s,t,p;
	for(int i=0;i<=20;i++)
	{for(int j=0;j<=20;j++)
	{a[i][j]=-1;}}//初始化
	cin>>s;
	for(int i=0;i<s;i++)
	{
		cin>>t>>p;
		b[i]=c(t,p);
	}
	for(int i=0;i<s;i++)
	{cout<<b[i]<<endl;}
}