xtu oj 1090 组合数

本文主要是介绍xtu oj 1090 组合数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

2^n=C(n,0)+C(n,1)+…+C(n,n)。其中^表示幂，C(n,x)表示组合数，即C(n,x)=n!/（(n-x)!x!）。现在给你n（0<=n<=33），要你输出2^n的组合数之和的表达式 输入 每行一个整数n，如果n为负数则输入结束。 输出 每行输出一个表达式，表达式格式形似为2^n=C(n,0)+C(n,1)+…+C(n,n)。 Sample Input 2 3 -1 Sample Output 2^2=1+2+1 2^3=1+3+3+1

AC代码

#include<stdio.h>
#define ll long long
ll dp[35][35]={};
void init(){int i,j;for(i=0;i<35;i++){dp[i][0]=1;dp[i][i]=1;}for(i=1;i<35;i++){for(j=1;j<i;j++){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}}
}
int main(){int n,i;init();while(scanf("%d",&n)&&n>=0){printf("2^%d=",n);for(i=0;i<=n;i++){if(i==n)printf("%I64d\n",dp[n][i]);else printf("%I64d+",dp[n][i]);}	}
} 

解题分析：2的33次方要用long long 类型，因为int 的范围是，可以用杨辉三角表示组合数，参考组合数的递推公式。

杨辉三角

dp[i][0]=dp[i][i]=1

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

这篇关于xtu oj 1090 组合数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---