Task 85. Незаконченная формула
UniLecsЗадача: дано выражение вида _ 1 _ 2 _ ... _ n = k
На месте символов нижнего подчеркивания должны стоять знаки + или -, так чтобы получилось верное равенство. Необходимо для заданного k найти минимально возможное n, для ктр существует указанная формула.
Входные данные: k - целое число.
Вывод: минимально возможное число n (n >= 1), при ктр существует формула.
Пример:
1. k = 2 -> n = 3; 1 - 2 + 3 = 2
2. k = 12 -> n = 7; -1 + 2 + 3 + 4 + 5 + 6 - 7 = 12
Идея: рассмотрим случай для k >= 0. Тогда, ищем минимальное n, для ктр 1+2+...+n >= k.
Если в сумме S = 1 + 2 + … + n перед любым из слагаемых поставить минус, четность суммы при этом не изменится. Этот вывод делается на основе свойств четности/нечетности целых чисел.
Подробнее вы можете посмотреть здесь:
Свойства четности и нечетности чисел
Сумма S - арифмитическая прогрессия, поэтому сформируем уравнение: (1+n)*n/2 = k. Приведем уравнение к квадратному: n^2 + n - 2k = 0.
Решив квадратное уравнение, получим его положительный корень, округленный вверх:
n1 = (-1 + Math.Sqrt(1 + 8k)) / 2.
Так как мы округлили значение, нам нужно определить точное решение, будем увличивать n1 на единицу, пока четность суммы 1+2+...+n и четность k не совпадут.
Реализация:
https://gist.github.com/unilecs/449334565d2fd728a0de3d92c775ae3e
Тест: