Количество отдельных простых разделов
Возможный дубликат:
Число как простое число
У меня есть мое домашнее задание, чертовски трудное, где я должен получить все четкие простые разбиения данного числа. Например, число 7 имеет пять различных простых разделов (или пять различных способов представления двух основных разделов):
- 5 + 2
- 2 + 5
- 3 + 2 + 2
- 2 + 3 + 2
- 2 + 2 + 3
Как видите, само число исключается, если оно простое. Мне не нужно печатать все отдельные разделы, только их количество.
Так что я немного растерялся с этим. Мне совершенно не удалось создать какой-либо код, но я думаю, что должен подходить к этому с точки зрения динамического программирования. Я только прошу несколько подсказок. У кого-нибудь есть идея? Заранее спасибо.
Самое высокое введенное число — 100.
Также время работы программы не может превышать 1 секунду, а ограничение памяти составляет 128 МБ.
Решение
Чтобы решить эту проблему, вам нужно объединить три идеи:
Скажем, данное число равно n:
-
найти все простые числа меньше n, как показано Вот.
-
динамически вычислять сумму подмножества из вашего простого массива и n. Несколько подсказок Вот а также Вот
-
затем вычислите количество различных перестановок каждого ответа, полученного на втором шаге, как Вот.
Теперь, конечно, это всего лишь подсказка. Но это должно очень помочь вам подготовить ваш окончательный код.
Другие решения
Итак, в виде подсказок в отличие от ответа:
- Как уже было сказано, вы можете заранее вычислить простые числа.
- Можете ли вы использовать результаты с меньшего числа? Итак, предполагая, что вы знаете фактические перестановки для 5, это поможет вам найти какие-либо фактические перестановки для 7?
- Есть ли какая-либо структура результатов, и если да, можете ли вы использовать эту структуру, чтобы избежать повторения расчетов? Например, вы перечислили 5 перестановок для числа 7, но они демонстрируют некоторое сходство друг с другом — это общая тенденция и что это?
- Предполагая, что вы найдете внутреннюю структуру а также можете использовать меньшие результаты, чтобы помочь найти более крупные, можете ли вы сделать и то и другое — можете ли вы полностью избежать сохранения полных промежуточных результатов?
- Наконец, вам нужно перечислить каждую заказанную комбинацию или просто вернуть число упорядоченных комбинаций? Вы можете сохранить вычисления здесь.
Вы не можете улучшить грубую силу здесь слишком много, к сожалению. Одна вещь, которую вы обязательно должны сделать, это использовать сито из Эратосфена рассчитать все простые числа до заданного числа. После этого с заданным числом N рекурсивно выведите все его разделы, где наименьшее простое число — это каждое простое число из списка простых чисел последовательно (не забудьте, чтобы оно было наименьшим, чтобы не повторять разделы).
РЕДАКТИРОВАТЬ: после знания вам нужно знать только количество разделов:
Лучшее решение будет использовать динамическое программирование. Опять же вам нужно будет запомнить в массиве с двумя измерениями mem[MAX_SIZE][MAX_SIZE] первый индекс — это число, для которого вы вычисляете решение, а второй — индекс минимального простого числа, которое вы должны использовать для раздела.
Вы можете посмотреть на математику разделов в Википедия в частности, разделы, посвященные функции создания и функциям создания ограниченных разделов, примерно на полпути вниз по странице. В нем упоминается производящая функция для разбиений, состоящих из конкретных слагаемых (заданных набором T натуральных чисел).
Пусть число не зависящих от порядка простых разбиений числа n равно R (n). Вы можете получить R (n) из производящей функции, взяв n-ю частную производную w.r.t x и установив тогда x = 0. Это может быть непросто.
Одно предостережение: эти разделы не зависят от порядка (то есть 1 + 2 и 2 + 1 считаются только как один раздел).