数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学莱布尼茨调和三角形
莱布尼茨调和三角形，也称为莱布尼茨级数或莱布尼茨公式，是由德国数学家和哲学家戈特弗里德·威廉·莱布尼茨在17世纪后期发现的一种三角形排列的数字。
莱布尼茨调和三角形是由分数组成的三角形排列。我们从顶部开始，数字为1，最外层的项是表示该特定行号的自然数的倒数。一般来说，莱布尼茨调和三角形中的一个项可以通过以下等式确定，其中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，莱布尼茨调和三角形有三行。每行的最外层项 = 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。
声明一个二维向量L，具有n+1行和n+1列，并将所有元素初始化为0。
调用函数LHT，参数为n和L。
在函数LHT中，迭代从i=0到i<=n。
在上述循环中，迭代从j=0到j<=min(i,n)。
在上述循环中，如果j==0或j==i，则将L[i][j]的值设置为1。
否则，将L[i][j]的值设置为L[i-1][j-1]+L[i-1][j]。
调用函数printLHT，参数为n和L。
在函数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是莱布尼茨调和三角形中的行数。这是因为该程序通过计算每个条目作为两个先前条目的和来生成三角形，并且三角形中有n2个条目。
空间复杂度：O(n2)
此程序的空间复杂度也为O(n2)，因为它将整个三角形存储在一个大小为(n + 1) * (n + 1)的二维向量中。
结论
在本文中，我们讨论了一种生成直到给定行数的莱布尼茨调和三角形的方法。莱布尼茨调和三角形是一个有趣的数学概念，类似于帕斯卡三角形。讨论了概念、实现、解决方案方法以及伪代码、使用的算法和C++程序。我们还分析了我们解决方案的时间和空间复杂度。
149 次查看
