расположить последовательность чисел так, чтобы сумма соседних чисел была простым числом

Как лучше всего расположить последовательность чисел так, чтобы сумма любых двух соседних чисел была простым числом. Например: 7,6,5,2,1,4,3 — одна такая последовательность чисел от 1 до 7. .


algorithm evolutionary-algorithm stl-algorithm
person Hemal    schedule 25.12.2013    source источник
comment
Вы пробовали это сами? Кроме того, всегда ли числа находятся в диапазоне [1..n]?   -  person Abhishek Bansal    schedule 25.12.2013
comment
Первое, на что следует обратить внимание: чтобы это было возможно, всегда должны быть нечетно-четно-нечетные числа. Если у вас больше нечетных, чем четных чисел, вы должны начать с четных; и т.п.   -  person Floris    schedule 25.12.2013
comment
Да, пожалуйста, уточните. Я не уверен, что это верно для произвольных последовательностей [1..n], поэтому я не совсем уверен, что вам нужно...   -  person J Trana    schedule 25.12.2013
comment
Эволюционный алгоритм не кажется мне лучшим. Кроме того, требуется определение «лучший». Это разовая задача или нужно делать много прогонов для разных n? Насколько большим может быть n? Один из возможных приемов — найти циклические последовательности диапазона [N..M], чтобы (первый+последний) также был простым.   -  person Abstraction    schedule 25.12.2013
comment
Я считаю, что вы можете решить эту проблему с помощью алгоритма поиска. Все ли числа положительные? Мы можем добавить некоторую обрезку.   -  person Tao HE    schedule 25.12.2013
comment
Перейдите по этой ссылке получить комплексное решение.   -  person Narendra Verma    schedule 11.01.2014

Ответы (1)


arrow_upward
3
arrow_downward

Насколько я понимаю, самый простой способ решить эту проблему — разбить ее на две более четко определенные части:

  1. Сгенерируйте неориентированный граф так, чтобы каждая вершина была числом в этом списке чисел, а каждое ребро связывало пару чисел, которые могут быть соседними. Или, другими словами, генерирует граф, который соединяет любые два числа, у которых есть сумма простых чисел. Это можно сделать довольно просто, перебирая 2 индекса.

  2. Найдите гамильтоновский путь для вышеупомянутого графа. Это та последовательность, которую вы хотите. Это довольно хорошо изученная проблема, и существует ряд алгоритмов. Вам просто нужно выбрать один, и он может быть реализован в программном обеспечении, таком как Mathematica. Это будет даже быстрее, чем O(n^2).

Конечно, вы можете найти несколько способов ускорить первый шаг, если вы знаете немного больше о том, с каким списком чисел вы имеете дело.

person Xiaolei Zhu    schedule 25.12.2013