给定一个行号n，任务是计算每行的所有元素之和，直到n th 一行 例如：
null
Input : 2Output : 7 Explanation: row 0 have element 1 row 1 have elements 1, 1 row 2 have elements 1, 2, 1 so, sum will be ((1) + (1 + 1) + (1 + 2 + 1)) = 7Input : 4Output : 31Explanation: row 0 have element 1 row 1 have elements 1, 1 row 2 have elements 1, 2, 1 row 3 have elements 1, 3, 3, 1 row 4 have elements 1, 4, 6, 4, 1 so, sum will be ((1) + (1 + 1) + (1 + 2 + 1) + (1 + 3 + 3 + 1) + (1 + 4 + 6 + 4 + 1)) = 31
下面是Pascal三角形的11行示例：
Pascal's triangle 0th row 1 1st row 1 1 2nd row 1 2 1 3rd row 1 3 3 1 4th row 1 4 6 4 1 5th row 1 5 10 10 5 1 6th row 1 6 15 20 15 6 1 7th row 1 7 21 35 35 21 7 1 8th row 1 8 28 56 70 56 28 8 1 9th row 1 9 36 84 126 126 84 36 9 1 10th row 1 10 45 120 210 256 210 120 45 10 1
天真的方法： 在帕斯卡三角形中，行的每个条目都是二项式系数的值。所以一个简单的解决方案是生成第n行的所有行元素，并将它们相加。但这种方法将产生O（n） 3. )时间复杂性。然而，它可以优化到O（n 2. )时间复杂性。请参阅以下文章以生成Pascal三角形的元素：
更好的解决方案： 让我们看看帕斯卡的三角形图案
sum of elements in ith row0th row 1 1 -> 201st row 1 1 2 -> 212nd row 1 2 1 4 -> 223rd row 1 3 3 1 8 -> 234th row 1 4 6 4 1 16 -> 245th row 1 5 10 10 5 1 32 -> 256th row 1 6 15 20 15 6 1 64 -> 267th row 1 7 21 35 35 21 7 1 128 -> 278th row 1 8 28 56 70 56 28 8 1 256 -> 289th row 1 9 36 84 126 126 84 36 9 1 512 -> 2910th row 1 10 45 120 210 256 210 120 45 10 1 1024 -> 210
如上图所示，i th 行等于2 我 现在可以很容易地计算出所有元素的和，直到n th 通过将2的幂加在一起进行排序。 以下是上述方法的实施情况：
C++
// C++ program to find sum of all elements // upto nth row in Pascal triangle. #include <bits/stdc++.h> using namespace std; // Function to find sum of all elements // upto nth row. long long int calculateSum( int n) { // Initialize sum with 0 long long int sum = 0; // Loop to calculate power of 2 // upto n and add them for ( int row = 0; row < n; row++) { sum = sum + (1 << row); } return sum; } // Driver function int main() { int n = 10; cout << " Sum of all elements:" << calculateSum(n); return 0; } |
JAVA
// Java program to find sum of all elements // upto nth row in Pascal triangle. import java.io.*; class GFG { // Function to find sum of all elements // upto nth row. static long calculateSum( int n) { // Initialize sum with 0 long sum = 0 ; // Loop to calculate power of 2 // upto n and add them for ( int row = 0 ; row < n; row++) { sum = sum + ( 1 << row); } return sum; } // Driver code public static void main(String[] args) { int n = 10 ; System.out.println( "Sum of all elements:" + calculateSum(n)); } } |
Python3
# Python program to find sum of all elements # upto nth row in Pascal triangle. # Function to find sum of all elements # upto nth row. def calculateSum(n) : # Initialize sum with 0 sum = 0 # Loop to calculate power of 2 # upto n and add them for row in range (n): sum = sum + ( 1 << row) return sum # Driver code n = 10 print ( "Sum of all elements:" , calculateSum(n)) |
C#
// C# program to find sum of all elements // upto nth row in Pascal triangle. using System; public class GFG { // Function to find sum of all elements // upto nth row. static long calculateSum( int n) { // Initialize sum with 0 long sum = 0; // Loop to calculate power of 2 // upto n and add them for ( int row = 0; row < n; row++) { sum = sum + (1 << row); } return sum; } static public void Main() { int n = 10; Console.WriteLine( "Sum of all elements:" + calculateSum(n)); } } |
PHP
<?php // PHP program to find sum of // all elements upto nth row // in Pascal triangle. // Function to find sum of // all elements upto nth row. function calculateSum( $n ) { // Initialize sum with 0 $sum = 0; // Loop to calculate power // of 2 upto n and add them for ( $row = 0; $row < $n ; $row ++) { $sum = $sum + (1 << $row ); } return $sum ; } // Driver Code $n = 10; echo " Sum of all elements : " . calculateSum( $n ); // This code is contributed by Mahadev. ?> |
Javascript
<script> // Javascript program to find sum of // all elements upto nth row // in Pascal triangle. // Function to find sum of // all elements upto nth row. function calculateSum(n) { // Initialize sum with 0 let sum = 0; // Loop to calculate power // of 2 upto n and add them for (let row = 0; row < n; row++) { sum = sum + (1 << row); } return sum; } // Driver Code let n = 10; document.write( " Sum of all elements : " + calculateSum(n)); // This code is contributed by _saurabh_jaiswal. </script> |
输出：
Sum of all elements:1023
时间复杂性： O（n） 高效的解决方案：
2. N 可以表示为 2. N = ( 2 0 + 2 1. + 2 2. + 2 3. +. . . + 2. （n-1） ) + 1 例如： 2. 6. = ( 20 + 2 1. + 2 2. + 2 3. + 2 4. + 2 5. ) + 1 64 = ( 1 + 2 + 4 + 8 +16 + 32 ) + 1 64 = 63 + 1
那么，计算2 N 而不是计算2到（n–1）的每一次幂，根据上面的例子，2到（n–1）的幂之和将是（2） N – 1).
C++
// C++ program to find sum of all elements // upto nth row in Pascal triangle. #include <bits/stdc++.h> using namespace std; // Function to find sum of all elements // upto nth row. long long int calculateSum( int n) { // Initialize sum with 0 long long int sum = 0; // Calculate 2^n sum = 1 << n; return (sum - 1); } // Driver function int main() { int n = 10; cout << " Sum of all elements:" << calculateSum(n); return 0; } |
JAVA
// Java program to find sum of all elements // upto nth row in Pascal triangle. import java.io.*; class GFG { // Function to find sum of all elements // upto nth row. static long calculateSum( int n) { // Initialize sum with 0 long sum = 0 ; // Calculate 2^n sum = 1 << n; return (sum - 1 ); } // Driver code public static void main(String[] args) { int n = 10 ; System.out.println( "Sum of all elements:" + calculateSum(n)); } } |
Python3
# Python3 program to find sum of all elements # upto nth row in Pascal triangle. # Function to find sum of all elements # upto nth row. def calculateSum(n) : # Initialize sum with 0 sum = 0 # Calculate 2 ^ n sum = 1 << n; return ( sum - 1 ) # Driver unicode n = 10 print ( "Sum of all elements:" , calculateSum(n)) |
C#
// C# program to find sum of all elements // upto nth row in Pascal triangle. using System; public class GFG { // Function to find sum of all elements // upto nth row. static long calculateSum( int n) { // Initialize sum with 0 long sum = 0; // Calculate 2^n sum = 1 << n; return (sum - 1); } // Driver code static public void Main() { int n = 10; Console.WriteLine( "Sum of all elements:" + calculateSum(n)); } } |
PHP
<?php // PHP program to find sum // of all elements upto nth // row in Pascal triangle. // Function to find // sum of all elements // upto nth row. function calculateSum( $n ) { // Initialize sum with 0 $sum = 0; // Calculate 2^n $sum = 1 << $n ; return ( $sum - 1); } // Driver Code $n = 10; echo " Sum of all elements:" , calculateSum( $n ); // This code is contributed // by akt_mit ?> |
Javascript
// Javascript program to find sum // of all elements upto nth // row in Pascal triangle. // Function to find // sum of all elements // upto nth row. function calculateSum(n) { // Initialize sum with 0 sum = 0; // Calculate 2^n sum = 1 << n; return (sum - 1); } // Driver Code let n = 10; document.write( " Sum of all elements:" + calculateSum(n)); // This code is contributed _saurabh_jaiswal |
输出：
Sum of all elements:1023
时间复杂性： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
