Блог

Дано положительное целое число N. Задача состоит в том, чтобы найти 1² + 2² + 3² + ….. + N².

Примеры:

Input : N = 4
Output : 30
12 + 22 + 32 + 42
= 1 + 4 + 9 + 16
= 30

Input : N = 5
Output : 55

Способ 1: O(N) 

Идея состоит в том, чтобы запустить цикл от 1 до n, и для каждого i, 1 <= i² суммировать.

# 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.*/

Выход:

30

Метод 2: O(1)

Доказательство:

Мы знаем,
(k + 1)3 = k3 + 3 * k2 + 3 * k + 1
Мы можем записать вышеуказанный идентификатор для k от 1 до n:
23 = 13 + 3 * 12 + 3 * 1 + 1 ......... (1)
33 = 23 + 3 * 22 + 3 * 2 + 1 ......... (2)
43 = 33 + 3 * 32 + 3 * 3 + 1 ......... (3)
53 = 43 + 3 * 42 + 3 * 4 + 1 ......... (4)
...
n3 = (n - 1)3 + 3 * (n - 1)2 + 3 * (n - 1) + 1 ......... (n - 1)
(n + 1)3 = n3 + 3 * n2 + 3 * n + 1 ......... (n)

Подставляя уравнения (N - 1) в уравнении Н
(П + 1)3 = (Н - 1)3 + 3 * (П - 1)2 + 3 * (П - 1) + 1 + 3 * н2 + 3 * П + 1
 = (Н - 1)3 + 3 * (П2 + (п - 1)2) + 3 * ( n + (n - 1) ) + 1 + 1

Поставив все уравнения, получим
(П + 1)3 = 13 + 3 * Σ к2 + 3 * Σ к + Σ 1
н3 + 3 * н2 + 3 * П + 1 = 1 + 3 * Σ к2 + 3 * (п * (п + 1))/2 + п
н3 + 3 * н2 + 3 * н = 3 * K и Σ2 + 3 * (п * (п + 1))/2 + п
н3 + 3 * н2 + 2 * п - 3 * (п * (п + 1))/2 = 3 * Σ к.2
n * (n2 + 3 * n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k2
n * (n + 1) * (n + 2) - 3 * (n * (n + 1))/2 = 3 * Σ k2
n * (n + 1) * (n + 2 - 3/2) = 3 * Σ k2
n * (n + 1) * (2 * n + 1)/2 = 3 * Σ k2
n * (n + 1) * (2 * n + 1)/6 = Σ k2

# 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.															

Выход:

30

Избегая раннего переполнения:
Для большого числа 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)>

Выход:

30