算法0基础刷题——组合数
2023-02-18 16:26:27 时间
前言
最近由于备战蓝桥杯,码神开了个新的专题——英雄老师算法之0基础刷题记,主要作用就是写一下自己的题解报告,用来帮助自己提高一下写作能力,也是复盘的一个好方法,话不多说,发车了!
杨辉三角
介绍
性质:
- 每个数等于它上方两数之和。
- 每行数字左右对称,由1开始逐渐变大。
- 第n行的数字有n项。
- 前n行共[(1+n)n]/2 个数。
- 第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。
对于解题有用的性质就这几个,如果想要深入了解杨辉三角,请各位彦祖百度一下。
解题报告
由于题目是让我们输出前n行的数,所以最直接的想法就是按照题的意思来说,直接进行遍历输出,暴力解法 1.暴力
for (int i = 0; i < numRows; ++i)
{
ret[i].resize(i + 1);
ret[i][0] = ret[i][i] = 1;
for (int j = 1; j < i; ++j)
{
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}
}
上面提到了杨辉三角的那么多的性质总不能不用吧,所以下面也是我自己用数学写的题解 2.组合数 在这里我们暂定为n=1,m=1,第n行的第m个数就为C(n-1,m-1),这个请出pow函数,pow函数要用头文件
计算x的y次幂 例:z=pow(x,y); x=9,y=8 z就是9的8次方。
我尝试的实现了一下,发现在这个题中它比模拟,暴力还要复杂,所以说还是用第一个吧
最后
我以后可能会长期更新这个系列,已经半夜了,睡了,下一次就只有干货,没有闲聊了,拜拜,各位彦祖!