c++编写下列项目:任意给定一个小于20的整数n,任意打印出n行杨辉三角。 杨辉三角的形式为: 1 1_1 1_2_1 1_3_3_1 1_4_6_4_1 …… (以上实例中,“_”代表空格,仅用来间隔两个数字,在输出时不要 打印出来。请自行学习杨辉三角的特点)
时间: 2024-02-06 18:09:50 浏览: 19
以下是用 C++ 编写的杨辉三角程序:
```cpp
#include <iostream>
using namespace std;
int main() {
int n;
cout << "请输入小于20的整数n:";
cin >> n;
int a[20][20] = {0}; // 初始化二维数组为0
for (int i = 0; i < n; i++) {
a[i][0] = 1; // 每行第一个数为1
for (int j = 1; j <= i; j++) {
a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; // 计算当前数字
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cout << a[i][j] << " "; // 输出数字
}
cout << endl; // 换行
}
return 0;
}
```
运行程序后,输入一个小于20的整数n,程序会输出n行杨辉三角。例如,当输入n=5时,输出结果如下:
```
请输入小于20的整数n:5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
```
相关问题
设计一个C++代码任意给定一个小于 20 的整数 n,任意打印出 n 行杨辉三角
以下是一个简单的C++代码实现:
```cpp
#include <iostream>
using namespace std;
int main()
{
int n;
cout << "请输入一个小于20的整数n:" << endl;
cin >> n;
int triangle[n][n];
// 初始化杨辉三角
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
triangle[i][j] = 1;
} else {
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
}
}
}
// 打印杨辉三角
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cout << triangle[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
运行结果如下(以输入 n=6 为例):
```
请输入一个小于20的整数n:
6
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
```
题目描述 从杨辉三角中按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列: 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,... 给定一个正整数N,求数列中第一次出现N是第几个数。 输入格式 输入一个整数N。 输出格式 输出一个整数代表答案。 数据范围 1≤N≤10^10 样例 输入样例: 6 输出样例: 13给出C++优化代码和详细注释
解题思路:
我们发现其实我们无法计算整个数列,因为其规模太大,所以需要寻找特殊的规律进行计算
我们尝试将杨辉三角转化成如下的形式:
1
1,1
1,2,1
1,3,3,1
1,4,6,4,1
可以发现一个规律,即每一行前后均为1,并且每一行的元素可以由上一行相邻的两个元素和组成。如果我们将每个数都减去其前面的元素,我们能够得到如下形式的数列:
1,0,1,0,2,0,1,0,3,0,3,0,1,0,4,...
可以发现,每当出现一个新的数n时,一定伴随着一个0的出现。
现在对于每个数列的位置pos,我们都能够通过pos / (pos的行数)得到其所在行的位置k,然后我们再通过pos % (pos的行数)得到其在该行中的位置j。这样就可以使用组合数快速计算出其对应的数值了。
具体地,对于pos所在的行,我们使用二项式系数计算其对应的系数,即C(k, j)。由于杨辉三角、下三角和正方形三个部分组成的三角形是关于竖直中线和左下到右上的中线对称的,所以当k > j时,我们可以将其替换为C(k, k - j)。
而对于每次出现新的数n,我们都能够找到其对应的位置pos,根据已知规律计算出其值即可。
注意,由于N可能很大,我们需要使用long long存储计算结果。
时间复杂度 分别为:计算0~pos范围内的所有数字时间复杂度为O(pos * log(pos)),pos的计算时间复杂度为O(log(N)),因此总的时间复杂度为O(pos * log(pos) + log(N))。
C++ 代码