Задача java за сегодня

Подзадача 2: сумма простых чисел (10 баллов)

Все натуральные числа N> = 4 можно представить в виде суммы простых чисел. Чем больше N, тем больше

Существуют различные возможности сумм простых чисел:

N S (N)

4 = 2 + 2 1 5 = 2 + 3 1 6 = 2 + 2 + 2 = 3 + 3 2 7 = 2 + 2 + 3 = 2 + 5 2 8 = 2 + 2 + 2 + 2 = 2 + 3 + 3 = 3 + 5 3 9 = 2 + 2 + 2 + 3 = 2 + 2 + 5 = 2 + 7 = 3 + 3 + 3 4

10 = 2 + 2 + 2 + 2 + 2 = 2 + 2 + 3 + 3 = 2 + 3 + 5 = 3 + 7 = 5 + 5 5 ...

Напишите Java-программу PrimeSums.java, которая вычисляет статическое длинное числоOfSums (int N) // в функции S (N).

рассчитывается количество различных сумм простых сумм. Реализовать алгоритм рекурсивно. Основная функция класса PrimeSums должна выводить все значения S (N) в одну строку, каждое до 4 <= N <= 200, передаваемых в качестве параметра программы:

gruenau6 Ahrens 25 (~)> Java PrimeSums 10 4: 1

5: 1

6: 2

7: 2

8: 3

9: 4

10: 5

gruenau6 Ahrens 25 (~)>

Реализовать основной тест в отдельной функции

статическое логическое простое число (int n) // является простым числом? который решает для всех натуральных чисел n> 0, существует ли простое число.

намек

Вы не можете просто сложить результаты всех S (N-p) для всех простых чисел p <N / 2 (при необходимости +1, если N-p простое число, и еще +1, если N / 2 простое число), потому что тогда могут быть одинаковые суммы быть посчитано несколько раз:

Пример: N = 9

2 <9/2: S (9-2) = 2 3 <9/2: S (9-3) = 2

2+ 2 + 2 + 5 3+ 3 + 3 + 3

будет засчитан дважды!

+1 2 + 7

2 + 2 + 3 2 + 2 + 2

Поэтому может быть полезно использовать рекурсию в расширенной (и перегруженной) функции

static long numberOfSums (int N, int min) // определить количество

// сумма простых чисел n без слагаемых меньше min

вмещать. Какова связь между двумя функциями?

Даже если ваша программа определит (и выведет) правильные значения для S (N) в конце, вы обнаружите, что вычисление становится очень медленным, самое позднее, при N = 200. Это цена за то, что одни и те же вызовы часто выполняются в рекурсивной реализации. Тем не менее, ваша программа на gruenau6 с N = 200 должна занять максимум полминуты. Измерьте время выполнения с помощью утилиты Unix - она выполняет указанную команду и измеряет ее время:

gruenau6 Ahrens 25 (~)> время Java PrimeSums 200 ...

198: 8969035

199: 9397473

200: 9845164

18.490u 0.068s 0: 18.42 100.7% 0 + 0k 0 + 64io 0pf + 0w gruenau6 Ahrens 25 (~)>

~ 19 секунд

ДОПОЛНИТЕЛЬНАЯ ЗАДАЧА как текст:

Дополнительное задание: (10 дополнительных баллов)

Расширьте свое решение PrimeSums.java (сохраняя вышеуказанную функциональность), чтобы оно

также может быть вызван как параметр с опцией -sums и последующим числом N, а затем выводит все разные итоги (исключительно) из N:

gruenau6 ahrens 34 (~)> java PrimeSums -sums 11 2 + 2 + 7

2 + 2 + 2 + 5

2 + 2 + 2 + 2 + 3

2 + 3 + 3 + 3,

3 + 3 + 5

gruenau6 ahrens 35 (~)>

Конечно, вы можете (и должны) сделать это рекурсивно. Мы рекомендуем вам добавить новую функцию

статическая строка allSums (int N) // вычисляет все возможные суммы в виде строки //, которая генерирует все различные суммы «одним куском» (включая концы строк) // при выводе, например, через System.out.print (allSums (11)) ;

реализовать и реализовать это (на основе принципа, описанного выше) с помощью соответствующей расширенной и перегруженной рекурсивной функции, которая переносит уже найденные частичные строки общего решения и, возможно, частичные суммы в параметрах. Больше не должно быть обнаружено.