От ProjectEuler.net:
Prob 76: Сколько разных способов можно записать в виде суммы как минимум двух положительных целых чисел?
Я не знаю, как начать это... любые точки в правильном направлении или помочь? Я не ищу, как это сделать, но некоторые подсказки о том, как это сделать.
Например, 5 можно записать так:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
Итак, 6 возможностей.
Номера разделов (или функции раздела) являются ключом к этому.
Проблемы, подобные этим, обычно проще, если вы начинаете снизу и прокладываете себе путь, чтобы узнать, можете ли вы обнаружить любые шаблоны.
Совет. Посмотрите, можете ли вы построить P (N) из некоторой комбинации результатов до P (N).
Решение может быть найдено с использованием алгоритма измельчения.
Используйте, например, 6. Затем мы имеем:
6
5+1
4+2
3+3
но мы еще не закончили.
Если мы возьмем 5 + 1 и рассмотрим часть +1 как законченную, потому что все остальные конечные комбинации обрабатываются 4 + 2 и 3 + 3. Поэтому нам нужно применить тот же трюк к 5.
4+1+1
3+2+1
И мы можем продолжить. Но не бездумно. Поскольку, например, 4 + 2 производит 3 + 1 + 2 и 2 + 2 + 2. Но мы не хотим 3 + 1 + 2, потому что у нас будет 3 + 2 + 1. Таким образом, мы используем только все производные 4, где самое низкое число больше или равно 2.
6
5+1
4+1+1
3+1+1+1
2+1+1+1+1
1+1+1+1+1+1
2+2+1+1
3+2+1
4+2
2+2+2
3+3
Следующий шаг - поместить это в алгоритм.
Хорошо, нам нужна рекурсивная функция, которая принимает два параметра. Число, которое нужно нарезать, и минимальное значение:
func CountCombinations(Number, Minimal)
temp = 1
if Number<=1 then return 1
for i = 1 to Floor(Number/2)
if i>=Minimal then
temp := temp + CountCombinations(Number-i, i)
end for
return temp
end func
Чтобы проверить алгоритм:
C(6,1) = 1 + C(5,1) + C(4,2) + C(3,3) = 11, which is correct.
C(5,1) = 1 + C(4,1) + C(3,2) = 7
C(4,1) = 1 + C(3,1) + C(2,2) = 5
C(3,1) = 1 + C(2,1) = 3
C(2,1) = 1 + C(1,1) = 2
C(1,1) = 1
C(2,2) = 1
C(3,2) = 1
C(4,2) = 1 + C(2,2) = 2
C(3,3) = 1
Кстати, количество комбинаций 100:
CC(100) = 190569292
CC(100) = 190569291 (if we don't take into account 100 + 0)
Хороший способ приблизиться к ним не зацикливается на "100", но попытайтесь рассмотреть, какая разница между суммированием для суммы n и n + 1 будет, если искать шаблоны при увеличении n 1,2,3....
Я бы поехал сейчас, но у меня есть работа:)
Как и большинство проблем в Project Euler с большими номерами, лучший способ подумать о них - это не быть в тупике с этой огромной верхней границей и думать о проблеме в меньших терминах, и постепенно прокладывать себе путь. Возможно, по дороге вы узнаете шаблон или узнаете достаточно, чтобы легко получить ответ.
Единственный другой намек, который, я думаю, могу дать вам, не испортив ваше прозрение, - это слово "раздел".
Как только вы это поняли, вы получите его в кратчайшие сроки:)
один подход состоит в том, чтобы думать о рекурсивной функции: найти перестановки числовой серии, взятой из положительных целых чисел (допускаемых дубликатов), которые составляют до 100
другой подход состоит в том, чтобы думать о генеративной функции: начинать с нуля и находить последовательности перестановок до цели, сохраняя отображение/хэш или промежуточные значения и числа
вы можете перебирать значение с 1 или пересчитывать с 100; вы получите тот же ответ в любом случае. В каждой точке вы можете (для наивного решения) сгенерировать все перестановки ряда положительных чисел, считанных до целевого числа минус 1, и подсчитать только те, которые прибавляют к целевому номеру
Удачи!
Примечание. Моя математика немного ржавая, но, надеюсь, это поможет...
Вы хорошо справляетесь со своей проблемой.
Подумайте:
Итак, идея состоит в том, чтобы найти первый набор (скажем, 5 = (5-1) +1), а затем рассматривать (5-1) как новый n... 5 = 4 +1... 5 = ((4-1) + 1) +1. Однажды, которая исчерпана, снова начинается на 5 = 3 + 2.... которая становится 5 = ((3-1) +1) +2.... = 2 + 1 + 2.... разрушая каждый как вы идете.
Многие математические проблемы могут быть решены с помощью induction.
Вы знаете ответ для определенного значения, и вы можете найти ответ для каждого значения, если найдете что-то, что связывает n с n+1.
Например, в вашем случае вы знаете, что ответ для Сколько разных способов можно записать в виде суммы по крайней мере двух положительных целых чисел? - всего 1.
Что я имею в виду со ссылкой между n и n+1? Ну, я имею в виду, что вы должны найти формулу, которая сообщит вам ответ на n, вы найдете ответ для n+1. Затем, вызывая рекурсивно эту формулу, вы узнаете ответ, и вы сделали (обратите внимание: это только математическая часть этого, в реальной жизни вы можете обнаружить, что такой подход дал бы вам что-то слишком медленное, чтобы быть практичным, поэтому вы еще не сделали - в этом случае я подумаю, что вы сделаете).
Теперь предположим, что вы знаете, что n может быть записано как сумма как минимум двух положительных целых чисел? в k разными способами, одним из которых будет:
n = a1 + a2 + a3 +... am (эта сумма имеет m слагаемых)
Что вы можете сказать о n+1? Поскольку вы хотели бы просто намеки, я не пишу здесь решение, а только то, что следует. Конечно, у вас есть те же самые k разные способы, но в каждом из них будет член +1, один из которых будет:
n + 1 = a1 + a2 + a3 +... am + 1 (эта сумма имеет m + 1 членов)
Тогда, конечно, у вас будут другие возможности k, такие как те, в которых последний член каждой суммы не один и тот же, но он будет увеличен на единицу, например:
n + 1 = a1 + a2 + a3 +... (am + 1) (эта сумма имеет m слагаемых)
Таким образом, существует как минимум 2k способов записи n+1 в виде суммы по крайней мере двух положительных целых чисел. Ну, есть и другие. Найдите это, если вы можете:-)
И наслаждайтесь: -))