前n个自然数平方和的Python程序-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. 总而言之。

                     # Python3 Program to                   
                     # find sum of square                   
                     # of first n natural                   
                     # numbers                   
                             
                             
                     # Return the sum of                   
                     # square of first n                   
                     # natural numbers                   
                     def                               squaresum(n) :                   
                             
                                         # Iterate i from 1                   
                                         # and n finding                   
                                         # square of i and                   
                                         # add to sum.                   
                                         sm                               =                               0                   
                                         for                               i                               in                               range                               (                               1                               , n                               +                               1                               ) :                   
                                         sm                               =                               sm                               +                               (i                               *                               i)                   
                             
                                         return                               sm                   
                             
                     # Driven Program                   
                     n                               =                               4                   
                     print                               (squaresum(n))                   
                             
                     # This code is contributed by Nikita Tiwari.*/                   

输出：

方法2:O（1）

图片[1]-前n个自然数平方和的Python程序-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²

                     # Python3 Program to                   
                     # find sum of square                   
                     # of first n natural                   
                     # numbers                   
                             
                     # Return the sum of                   
                     # square of first n                   
                     # natural numbers                   
                     def                               squaresum(n) :                   
                                         return                               (n                               *                               (n                               +                               1                               )                               *                               (                               2                               *                               n                               +                               1                               ))                               /                               /                               6                   
                             
                     # Driven Program                   
                     n                               =                               4                   
                     print                               (squaresum(n))                   
                             
                     #This code is contributed by Nikita Tiwari.                   

输出：

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

                     # Python Program to find sum of square of first                   
                     # n natural numbers. This program avoids                   
                     # overflow upto some extent for large value                   
                     # of n.y                   
                             
                     def                               squaresum(n):                   
                                         return                               (n                               *                               (n                               +                               1                               )                               /                               2                               )                               *                               (                               2                               *                               n                               +                               1                               )                               /                               3                   
                             
                     # main()                   
                     n                               =                               4                   
                     print                               (squaresum(n));                   
                             
                     # Code Contributed by Mohit Gupta_OMG <(0_o)>                   

输出：

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

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

THE END

技术文章