Текст Задачи
«Сумма квадратов первых десяти натуральных чисел равна 1^2 + 2^2 + … + 10^2 = 385. Квадрат суммы первых десяти натуральных чисел равен (1 + 2 + … + 10)^2 = 55^2 = 3025. Разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640. Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел.»
Решение и Обсуждение
1. Прямой Подход
Простое решение заключается в прямом вычислении суммы квадратов и квадрата суммы, а затем нахождении их разности.
def sum_of_squares(n):
return sum(i**2 for i in range(1, n+1))
def square_of_sum(n):
return sum(range(1, n+1)) ** 2
def difference(n):
return square_of_sum(n) - sum_of_squares(n)
result = difference(100)
Анализ скорости выполнения: Этот метод требует линейного времени (O(n)) для обоих вычислений, что эффективно для малых и средних значений n.
2. Использование Формул
Можно использовать математические формулы для суммы квадратов и суммы первых n натуральных чисел, чтобы ускорить вычисления.
Сумма первых n натуральных чисел: n(n+1) / 2
Сумма квадратов первых n натуральных чисел: n(n+1)(2n+1) / 6
def difference_formula(n):
square_of_sums = (n * (n + 1) // 2) ** 2
sum_of_squares = n * (n + 1) * (2 * n + 1) // 6
return square_of_sums - sum_of_squares
result_formula = difference_formula(100)
Анализ скорости выполнения: Этот метод требует постоянного времени (O(1)), так как использует прямые арифметические операции, не зависящие от размера n.
Вывод
Оба метода эффективно решают задачу, но использование формул значительно ускоряет вычисления, особенно для больших значений n. Выбор метода зависит от размера задачи и требований к производительности.
