Задано четыре числа. Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальной. Например, для чисел 2,3,4,5 надо вывести 26 (2*3+4*5).
А бывают архисложные, требующие подключения серьёзного математического аппарата:
Для целого положительного числа от 1 до 1000 требуется найти число способов представить его в виде суммы нечётных слагаемых. Порядок слагаемых неважен. Например, для числа 6 надо вывести 4. Сами разбиения выводить не надо:
[1+1+1+1+1+1], [3+1+1+1], [3+3], [5+1]
Я сначала решил "в лоб" - прямым перебором, используя
Set для фильтрации. Потом ускорил в несколько сотен раз, отказавшись от Set. Это позволило мне обнаружить, что происходит переполнение для больших чисел. Посему мне пришлось заменить long на BigInteger, замедлив программу раза в два.fun count(array: IntArray, size: Int): BigInteger {
var count = BigInteger.ONE
val size2 = size - 2
if (size > 2 && array[size - 1] == 1 && array[size2] == 1) {
array[0] += 2
count = count.plus(count(list, array, size2))
array[0] -= 2
var index = 0
while (++index < size2) {
if (array[0] == array[index]) continue
if (array[0] == array[index] + 2) {
array[index] += 2
count = count.plus(count(list, array, size2))
array[index] -= 2
}
break
}
}
return count
}Тут стало очевидно, что после 170 мы перестаём укладываться в две секунды и подсчёт ответа для 400 занял более двух дней:in: 100; out: 444793; time: 21 ms in: 200; out: 487067746; time: 7958 ms in: 300; out: 114872472064; time: 1873429 ms in: 400; out: 11962163400706; time: 196301147 ms
Написал код для вывода комбинаций и пытаемся анализировать, чтобы для получившейся выше рекурсивной функции вывести формулу, ибо полный перебор - это уже перебор. 8)
