Блог

Выведите сумму рядов 1³ + 2³ + 3³ + 4³ + ……^{.+ n 3} до n-го срока.

Примеры:

Input : n = 5
Output : 225
13 + 23 + 33 + 43 + 53 = 225

Input : n = 7
Output : 784
13 + 23 + 33 + 43 + 53 + 
63 + 73 = 784

# Simple Python program to find sum of series
# with cubes of first n natural numbers

# Returns the sum of series
def sumOfSeries(n):
	sum = 0
	for i in range(1, n+1):
		sum +=i*i*i
		
	return sum


# Driver Function
n = 5
print(sumOfSeries(n))

# Code Contributed by Mohit Gupta_OMG <(0_o)>

Выход:

225

Временная сложность : O(n)

Эффективное решение заключается в использовании прямой математической формулы, которая является (n ( n + 1 ) / 2) ^ 2

For n = 5 sum by formula is  (5*(5 + 1 ) / 2)) ^ 2  = (5*6/2) ^ 2  = (15) ^ 2  = 225

For n = 7, sum by formula is  (7*(7 + 1 ) / 2)) ^ 2  = (7*8/2) ^ 2  = (28) ^ 2  = 784

# A formula based Python program to find sum
# of series with cubes of first n natural
# numbers

# Returns the sum of series
def sumOfSeries(n):
	x = (n * (n + 1) / 2)
	return (int)(x * x)



# Driver Function
n = 5
print(sumOfSeries(n))

# Code Contributed by Mohit Gupta_OMG <(0_o)>

Выход:

225

Временная сложность : O(1)

Как работает эта формула?

Мы можем доказать формулу, используя математическую индукцию. Мы легко можем видеть, что формула справедлива для n = 1 и n = 2. Пусть это верно для n = k-1.

Let the formula be true for n = k-1.
Sum of first (k-1) natural numbers = 
 [((k - 1) * k)/2]2

Sum of first k natural numbers = 
 = Sum of (k-1) numbers + k3
 = [((k - 1) * k)/2]2 + k3
 = [k2(k2 - 2k + 1) + 4k3]/4
 = [k4 + 2k3 + k2]/4
 = k2(k2 + 2k + 1)/4
 = [k*(k+1)/2]2

Вышеприведенная программа вызывает переполнение, даже если результат не выходит за пределы целого числа.

# Efficient Python program to find sum of cubes
# of first n natural numbers that avoids
# overflow if result is going to be withing
# limits.

# Returns the sum of series
def sumOfSeries(n):
	x = 0
	if n % 2 == 0 :
		x = (n/2) * (n+1)
	else:
		x = ((n + 1) / 2) * n
		
	return (int)(x * x)


# Driver Function
n = 5
print(sumOfSeries(n))

# Code Contributed by Mohit Gupta_OMG <(0_o)>

Выход:

225