第一n自然数平方和的C++程序-yiteyi-C++库

给定一个正整数 N .任务是找到1 ^2. + 2 ^2. + 3 ^2. + ….. + N ^2. .

null

例如：

Input : N = 4
Output : 30
1² + 2² + 3² + 4²
= 1 + 4 + 9 + 16
= 30

Input : N = 5
Output : 55

方法1:O（N） 这个想法是从1到n运行一个循环，对于每个i，1<=i<=n，找到i ^2. 总而言之。

CPP

                         // CPP Program to find sum of square of first n natural numbers                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Return the sum of the square                       
                         // of first n natural numbers                       
                         int                                     squaresum(                                     int                                     n)                       
                         {                       
                                                 // Iterate i from 1 and n                       
                                                 // finding square of i and add to sum.                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 sum += (i * i);                       
                                                 return                                     sum;                       
                         }                       
                                   
                         // Driven Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 4;                       
                                                 cout << squaresum(n) << endl;                       
                                                 return                                     0;                       
                         }                       

输出：

方法2:O（1） 图片[1]-第一n自然数平方和的C++程序-yiteyi-C++库证据：

We know,
(k + 1)³ = k³ + 3 * k² + 3 * k + 1
We can write the above identity for k from 1 to n:
2³ = 1³ + 3 * 1² + 3 * 1 + 1 ......... (1)
3³ = 2³ + 3 * 2² + 3 * 2 + 1 ......... (2)
4³ = 3³ + 3 * 3² + 3 * 3 + 1 ......... (3)
5³ = 4³ + 3 * 4² + 3 * 4 + 1 ......... (4)
...
n³ = (n - 1)³ + 3 * (n - 1)² + 3 * (n - 1) + 1 ......... (n - 1)
(n + 1)³ = n³ + 3 * n² + 3 * n + 1 ......... (n)

Putting equation (n - 1) in equation n,
(n + 1)³ = (n - 1)³ + 3 * (n - 1)² + 3 * (n - 1) + 1 + 3 * n² + 3 * n + 1
         = (n - 1)³ + 3 * (n² + (n - 1)²) + 3 * ( n + (n - 1) ) + 1 + 1

By putting all equation, we get
(n + 1)³ = 1³ + 3 * Σ k² + 3 * Σ k + Σ 1
n³ + 3 * n² + 3 * n + 1 = 1 + 3 * Σ k² + 3 * (n * (n + 1))/2 + n
n³ + 3 * n² + 3 * n = 3 * Σ k² + 3 * (n * (n + 1))/2 + n
n³ + 3 * n² + 2 * n - 3 * (n * (n + 1))/2 = 3 * Σ k²
n * (n² + 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k²
n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k²
n * (n + 1) * (n + 2 - 3/2) = 3 * Σ k²
n * (n + 1) * (2 * n + 1)/2  = 3 * Σ k²
n * (n + 1) * (2 * n + 1)/6  = Σ k²

CPP

                         // CPP Program to find sum                       
                         // of square of first n                       
                         // natural numbers                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Return the sum of square of                       
                         // first n natural numbers                       
                         int                                     squaresum(                                     int                                     n)                       
                         {                       
                                                 return                                     (n * (n + 1) * (2 * n + 1)) / 6;                       
                         }                       
                                   
                         // Driven Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 4;                       
                                                 cout << squaresum(n) << endl;                       
                                                 return                                     0;                       
                         }                       

输出：

避免提前溢出： 对于较大的n，（n*（n+1）*（2*n+1））的值将溢出。利用n*（n+1）必须能被2整除的事实，我们可以在一定程度上避免溢出。

CPP

                         // CPP Program to find sum of square of first                       
                         // n natural numbers. This program avoids                       
                         // overflow upto some extent for large value                       
                         // of n.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Return the sum of square of first n natural                       
                         // numbers                       
                         int                                     squaresum(                                     int                                     n)                       
                         {                       
                                                 return                                     (n * (n + 1) / 2) * (2 * n + 1) / 3;                       
                         }                       
                                   
                         // Driven Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 4;                       
                                                 cout << squaresum(n) << endl;                       
                                                 return                                     0;                       
                         }                       

输出：

请参阅完整的文章前n个自然数的平方和更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章