利用排列组合公式Cnm输出杨辉三角(C语言实现)-创新互联

二项式定理与杨辉三角联系十分紧密。杨辉三角的第 n 行的第 m(设m从0开始数) 个数即 n 次二项式展开的第 m 个系数,因此杨辉三角某行某列上的数都可以通过二项式定理的系数来得知,计算n次二项式展开的系数又可以通过排列组合的公式来求。

利川网站建设公司成都创新互联,利川网站设计制作,有大型网站制作公司丰富经验。已为利川成百上千家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的利川做网站的公司定做!

杨辉三角的第 n 行 第  m 列可以使用该公式求得,这里的 n 行、m 列对应着上方公式中的 n 和  m 。等式最右边的分子为 n 的阶乘,一定包含分母中的 (n - m)! ,两者相消,得到的结果分子为 n * (n - 1) * (n - 2) * (n - 3) * ...... * (n - m + 1),分母为 m!。

同时还有,0!= 0,所以杨辉三角的第零行,就是什么都没有。。。

#include// 计算分母 返回一个数的阶乘
double findFactorial(double num){
	double result = 1;
	for( ; num >1 ; num--){
		result *= num;
	}
	return result;
}

// 计算分子 start * ( start - 1 ) * ( start - 2 )~~~~(start - end + 1)
double calculate(double start, double num){
	double result = 1;					// 保存结果
	double tempstart = start;
	for(; start >tempstart - num ; start--){
		result *= start;
	}
	return result;
}

// 打印出杨辉三角		默认从第一层开始 ‘1’、‘1 1’、‘1 2 1’....
void printYangHui(double n){
	if(n == 0){					// 如果要第零层则打印空
		return;
	}
	for(double i = 0 ; i< n ; i++){
		for(double j = 0 ; j<= i ; j++){
			printf("%0.lf  ",calculate(i, j) / findFactorial(j));
		}
		printf("\n");
	}
}

int main(){
	printf("请输入杨辉三角的层数:");
	int n = 0;
	scanf("%d",&n);
	printf("result:\n\n");
	printYangHui(n);
	
}

对比利用数组来输出杨辉三角,这种方法不需要开辟数组,节省了一定的空间,但是计算较多,也存在重复计算的问题:杨辉三角是两侧对称的,即两侧的数据有重复的,这里的计算重复了。

利用递归改进一下,对称输出,就不用重复计算之前已经计算过的值了:

// 利用递归进行对称打印  新增的
void printSymmetry(int i, int j){
	double temp = calculate(i, j) / findFactorial(j);
	printf("%0.lf  ", temp);                // 三角的左边输出
	if(j< i / 2){
		printSymmetry(i, j + 1);
	}
	if(2 * j != i){                        // 判断情况,三角的右边输出
		printf("%0.lf  ",temp);		
	}
}

// 打印出杨辉三角		默认从第一层开始 ‘1’、‘1 1’、‘1 2 1’....
void printYangHui(double n){
	if(n == 0){					// 如果要第零层则打印空
		return;
	}
	for(double i = 0 ; i< n ; i++){		// C00 = 1 即第一行为1
		printSymmetry(i, 0);                // 在这里调用上面的递归函数
		printf("\n");
	}
}

不过这里面,还是有很多重复的计算,比如阶乘的计算就重复计算了很多次。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站栏目:利用排列组合公式Cnm输出杨辉三角(C语言实现)-创新互联
文章URL:http://pwwzsj.com/article/dssigi.html