极客笔记C++ 莱布尼茨和谐三角形
莱布尼茨和谐三角形，也称为莱布尼茨级数或莱布尼茨公式，是17世纪末由德国数学家和哲学家哥特弗里德·威廉·莱布尼茨发现的一种数列排列形式。
莱布尼茨和谐三角形是一种分数的三角形排列。我们从顶部开始，最外层的项是自然数的倒数，表示特定的行号。一般情况下，莱布尼茨和谐三角形中的一项可以由下列公式确定，其中r是行号，c是列号，并且满足条件c ≤ r：
L(r,c) = L(r-1,c-1) – L(r,c-1)，其中 L(r,1) = 1/r
下图描述了莱布尼茨和谐三角形的前3行。
题目描述
给定一个数字n，生成n行的莱布尼茨和谐三角形。
示例
输入
n = 3
输出
1/1
1/2 1/2
1/3 1/6 1/3
解释
对于n = 3，Leibniz的调和三角形有三行。每一行的最外层项=1/(行号)。
为了生成这个三角形，我们从第一行开始，也就是1/1。然后，对于第二行，我们计算每个单元格的值为左上角的单元格减去左边的单元格：
L(2, 1) = 1/2
L(2, 2) = 1/2
所以第二行是1/2 1/2。
最后，对于第三行，我们再次计算每个单元格的值为左上角的单元格减去左边的单元格
L(3,1) = L(3,3) = 1/3
L(3,2) = L(2,1) – L(3,1) = 1/6
输入
n = 4
输出
1/1
1/2 1/2
1/3 1/6 1/3
1/4 1/12 1/12 1/4
解释
直到n = 3时的方法与上面的例子相同。
对于第四行
L(4,1) = L(4,4) = 1/4
L(4,2) = L(3,1) – L(4,1) = 1/3 – 1/4 = 1/12
L(4,3) = L(3,2) – L(4,2) = 1/6 – 1/12 = 1/12
解决方法
伪代码
- 开始
-
将n的值初始化为4。
-
声明一个n+1行n+1列的2D向量L，并将所有元素初始化为0。
-
使用参数n和L调用函数LHT。
-
在函数LHT中，从i=0迭代到i<=n。
-
在上述循环内，从j=0迭代到j<=min(i,n)。
-
在上述循环内，如果j0或ji，则将
L[i][j]的值设为1。 -
否则，将L[i][j]的值设为
L[i-1][j-1]+L[i-1][j]。 -
使用参数n和L调用函数printLHT。
-
在函数printLHT中，从i=1迭代到i<=n。
-
在上述循环内，从j=1迭代到j<=i。
-
在上述循环内，打印”1/”，后跟
i*L[i-1][j-1]。 -
在每个内部循环完成后打印一个新行。
-
结束。
算法
function LHT()
for i = 0 to n do
for j = 0 to min(i, n) do
if j == 0 or j == i then
L[i][j] = 1
else
L[i][j] = L[i-1][j-1] + L[i-1][j]
end if
end for
end for
printLHT(n, L)
end function
function printLHT()
for i = 1 to n do
for j = 1 to i do
print "1/" + i*L[i-1][j-1] + " "
end for
print new line
end for
end function
function main
Initialize n = 4
L = 2D vector of size n + 1 x n + 1, with all elements initialized to 0
LHT(n, L)
return 0
示例：C++程序
下面的C++程序使用函数LHT()和printLHT()生成并打印给定行数的莱布尼兹谐波三角形。main()函数初始化行数，并创建一个大小为n + 1 * n + 1的二维向量’L’来存储项。
// CPP Program to print Leibniz Harmonic Triangle
#include <bits/stdc++.h>
using namespace std;
// Function to print Leibniz Harmonic Triangle
void printLHT(int n, vector<vector<int>> L){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++)
cout << "1/" << i * L[i - 1][j - 1] << " ";
cout << endl;
}
}
// Function to generate Leibniz Harmonic Triangle
void LHT(int n, vector<vector<int>> &L){
for (int i = 0; i <= n; i++){
for (int j = 0; j <= min(i, n); j++){
if (j == 0 || j == i)
L[i][j] = 1;
// Generate the value using previously stored values
else
L[i][j] = L[i - 1][j - 1] + L[i - 1][j];
}
}
// print Leibniz Harmonic Triangle
printLHT(n,L);
}
// Main function
int main(){
int n = 5;
// 2D vector to store the Leibniz Harmonic Triangle
vector<vector<int>> L(n + 1, vector<int>(n + 1, 0));
LHT(n, L);
return 0;
}
输出
1/1
1/2 1/2
1/3 1/6 1/3
1/4 1/12 1/12 1/4
1/5 1/20 1/30 1/20 1/5
时间和空间复杂度分析
时间复杂度：O(n2)
该程序的时间复杂度是O(n2)，其中n是Leibniz Harmonic Triangle的行数。这是因为程序通过计算每个条目作为前两个条目之和来生成三角形，而三角形中有n2个条目。
空间复杂度：O(n2)
该程序的空间复杂度也是O(n2)，因为它将整个三角形存储在大小为(n + 1) * (n + 1)的二维向量中。
结论
在上文中，我们讨论了一种生成Leibniz调和三角形的方法，直到给定行数为止。Leibniz调和三角形是一个有趣的数学概念，类似于帕斯卡三角形。我们讨论了概念、实现、解决方案以及伪代码、算法和C++程序。我们还分析了解决方案的时间和空间复杂度。