Prime Sums

[Nataly-Mak]

mertz
1.Предлагаю сделать раскраску в соответствии с весами элементов квадрата.
Например, так:



0 = {1,2,3,4,5,6}
1 = {7,8,9,10,11,12}
и т.д.

2. Я вижу кнопки Run Min, Run Max, Stop.
Это не работает?
Например, делать поиск решения 1760 (по конфигурации 896/1768) в автоматическом режиме? Возможно ли это?

[mertz]

1). I will try to add the weight to the display.
2). I had many versions of my algorithm. One did odd and even N>7 minus N=4k+2. The 4k+2 did one swap between the highest number in group 0 with the lowest in group 1 or group 3 and group 4 depending on if looking for minimum or maximum. N=5 was just random, no scheme. For N=6 and N=7, I randomly swapped a number in one set for a number in the set next to it. I picked the best one, and started again. I was close on N=6, 892 and 1756. N=7 not as good, 1812 and 3084. I can set it up so the Run command will run YOUR external program. Here is how that would work. When you press Run, the application would write the grid to a file call input.grid. Your program would be executed using input.grid as the starting grid. At the end of your program you would write a file called output.grid. The application would then load your output grid and display it. Your program could be written in any programming language.

[Nataly-Mak]

mertz
1. Я получила программу с дисплеем весов, спасибо. Это очень хорошо!



2. К сожалению, это я не поняла - проблемы перевода.

-- Пт янв 11, 2013 19:23:14 --

Продолжаю эксперимент.
Попробовала искать решения 1762 и 1764 с той же схемой, но варьируя разбиения.
Увы, выставляются 11 зачётных линий, но с неправильной 12-ой линией, значение этой линии не простое число.
Вот, например, решения 1762 и 1764 с неправильной 12-ой зачётной линией:

S=1762
33,19,36,10,25,14,
15,35,5,26,8,24,
34,20,27,9,29,12,
16,30,11,32,13,31,
23,7,17,2,22,3,
6,28,4,21,1,18

S=1764
33,19,27,11,25,12,
15,35,5,29,6,23,
32,20,34,8,28,9,
16,36,14,26,13,30,
31,7,17,4,21,2,
10,22,3,18,1,24

-- Пт янв 11, 2013 19:27:20 --

svb
вы ушли в подполье?
Где ваша программа для "шестёрки", которая для конкретной схемы-разбиения работает минуты-секунды?
У меня, к сожалению, программа для конкретной схемы-разбиения работает часы и ничего не находит

[whitefox]

(svb)

svb в сообщении #670175 писал(а):

Интересный квадрат

Вы занялись распространением "писем счастья"

Ответ: $10a+b-(a+b)=9a$

[svb]

Nataly-Mak

Цитата:

svb
вы ушли в подполье?
Где ваша программа для "шестёрки", которая для конкретной схемы-разбиения работает минуты-секунды?

И это я такое брякнул? Что-то смутно вспоминаю - помню для очистки совести запустил программу и для страховки к секундам добавил минуты.

Сейчас я в этом не уверен, привожу в порядок свои программы, стараюсь проверять. Я бы уже давно выложил и программу, и тексты, но ...
1. Вы меня побьете за интерфейс - я сам сейчас не очень помню, какие числа нужно вводить при некоторых вопросах программы.
2. Программ несколько, некоторые расчеты не включены в основную программу. Описать, как нужно это использовать - только запутывать.
3. После опубликования алгоритмов Pavlovsky и Vovka17 возникли задачи, которые хотелось бы проанализировать.
4. Чудес перебора в моей программе нет, нужна ли она сейчас?
5. Естественно, что имеется потребность в небольшом отдыхе.

Постараюсь, все же, побыстрее закончить работу по приведению программы в порядок, чтобы было не очень стыдно ее выкладывать

-- Сб янв 12, 2013 10:30:02 --

whitefox
Это было выложено в клубе выпускников на facebook

[Nataly-Mak]

svb
Вот здесь вы сказали:

svb в сообщении #668288 писал(а):

Предварительно я собирался сей простой алгоритм использовать только для знакомства с ситуацией, но так и "застрял". При фиксированной схеме и заданном распределении $M_i$ уже при $N=6$ идет полный перебор за несколько секунд-минут. При $N>7$ любая случайная схема сразу дает решение, только при $N=8$ иногда можно наблюдать небольшое замедление процесса. При этом я еще не дошел до чисто технической оптимизации алгоритма.

Ещё и опртимизации не было а уже минуты-секунды.

Я тоже очень устала (параллельно ещё квадратами Стенли занимаюсь).
Но вот непрестанно думаю: почему у svb программа выполняется секунды-минуты, а у меня часы?
Может быть, это ещё от схемы зависит?
Или у вас действительно есть "чудеса перебора"
Кстати, для предыдущей схемы (с оценкой 1760) у меня программа работала намного быстрее в случае, когда задавался конкретный набор из 12 простых (действительно это были минуты). А со схемой с оценкой 1768 ни черта не хочет работать!

Но вы, как я поняла, не задаёте конкретный набор из 12 простых. И даже в этом случае у вас программа работает быстро.

Кроме того, я для каждой схемы пишу новую программу. Не представляю, как можно проверять разные схемы по одной программе Тупею!

-- Сб янв 12, 2013 12:15:11 --

mertz
я получила новую версию программы. Спасибо!
Это очень интересная программа.
Пока попробовала Import:

1,15,2,30,3,36,23,8,22,13,25,18,11,29,10,34,12,35,27,7,28,14,21,16,5,20,4,31,6,33,24,9,26,17,32,19

Программа ищет решения. Правда, максимум пока найден только 1738.

[Nataly-Mak]

Восторг!
Опробовала программу Эда для N=8. Минут 6-7 и максимум найден. Красиво! Класс!



Кстати, об интерфейсе.
Вот в программе Эда классный интерфейс. Никаких вопросов! Только кнопки.

Очень похоже на интерфейс в программах alexBlack. Мне всегда очень нравились все его программы. Это "искусство программирования" Его программа построения маршрутов коня вообще чудо, я могла часами любоваться, как программа рисует маршруты. Это шедевр!

-- Сб янв 12, 2013 13:38:02 --

А это 8max, найденный по программе whitefox. Тоже очень красивое решение. Веса как симметрично распределены. Просто загляденье



-- Сб янв 12, 2013 13:52:04 --

Ну, и ещё одна картинка
Просто очень нравится работа программы. Высший пилотаж!
От введённого 8max (Import) ищу минимум для N=8. Чуть больше минуты потребовалось программе Эда на этот поиск. И в найденном решении тоже идеальный шахматный порядок в распределении весов. Дьявольски красиво!

[Nataly-Mak]

mertz
я выложила вашу последнюю версию программы на файлообменник:
http://narod.ru/disk/65392625001.a425a4 ... 4.zip.html

Всем, всем, всем!
Посмотрите эту программу. Есть чему поучиться. Отличная работа!

Да, забыла. Коротенькие инструкции, Эд написал мне их в письме.

Режим 1. Поиск по введённому решению

a) Import
b) Hill Climb
c) Run Max (или Run Min)

Режим 2. Поиск по генерируемой программой конфигурации.

а) Select N
b) Configurations
с) Fill Max (или Fill Min)
d) Hill Climb
e) Run Max (или Run Min)

Надеюсь, не напутала
Если что, Эд поправит. В письме инструкции ещё короче
Я действовала методом тыка (самый верный метод, когда ни фига не понимаешь ).

[svb]

Nataly-Mak

Цитата:

Кстати, для предыдущей схемы (с оценкой 1760) у меня программа работала намного быстрее в случае, когда задавался конкретный набор из 12 простых (действительно это были минуты).

С самого начала я решил, что часто придется проверять числа на простоту. Для этого разумно создать массив простых чисел pr[] и написать функцию $prime(x)$, которая для любого числа $x$ выдает номер простого числа в массиве при простом $x$, либо 0, если $x$ - составное. Сейчас используется метод двоичного поиска:

function prime(x:longint):integer;
var i,j,k:integer;
begin
  prime:=0;
  if (x<pr[begpr])or(x>pr[numpr]) then exit;
  i:=begpr-1;j:=numpr+1;
  repeat
    k:=(i+j)div 2;
    if x=pr[k] then begin prime:=k;exit end;
    if x>pr[k] then i:=k else j:=k
  until i>=j-1;
end;

$begpr$ и $numpr$ - индексы крайних простых чисел, между которыми может находиться искомое простое число. Можно использовать линейный поиск, но в этом случае время работы резко возрастает.

[dimkadimon]

Цитата:

С самого начала я решил, что часто придется проверять числа на простоту. Для этого разумно создать массив простых чисел pr[] и написать функцию $prime(x)$, которая для любого числа $x$ выдает номер простого числа в массиве при простом $x$, либо 0, если $x$ - составное.

Можно создать boolean[] P, где P[i]=true если i простое иначе P[i]=false. A еще можно создать int[] Ind. Ind[i]=k если i простое с индексом k.

[mertz]

I see an error in your output. It is swapping numbers in groups. I was testing and did not take out. I will send you a new program when I fix.

Configurations
Select a configuration if there is more than one.
Run Min or Run Max

Run does Fill and Hill Climb.

[svb]

dimkadimon
Это так, но я до сих пор не могу в себе переломить стремление к экономии памяти, со времен машин на 80286 , хотя для $N<8$, когда диапазон очень узкий, такое оправдание уже не проходит.

Но, в целом, вот из подобных "мелочей" и зависит скорость работы. Вопрос состоит в том, с чего начинать? Рисовать всю картину в целом и только потом прорисовывать детали, либо аккуратно заполнять пустой холст хорошо прорисованными деталями и в конце получить картину для мусорной корзины?

[Nataly-Mak]

svb в сообщении #670717 писал(а):

Можно использовать линейный поиск, но в этом случае время работы резко возрастает.

Да, то же самое мне говорил whitefox. Он смотрел одну из моих программ.
Кажется, у меня как раз линейная проверка. То есть массив простых в программу введён, например P(12). Как только я получаю значение зачётной линии, то сразу проверяю его на принадлежность этому массиву (если принадлежит, иду дальше, если не принадлежит - возврат). Это просто и тривиально. Других методов проверки я не знаю.

[svb]

Nataly-Mak
Воспользуйтесь советом dimkadimon - ускорение будет заметным. Тем же способом разумно исключать уже задействованные простые числа.

[dimkadimon]

svb в сообщении #670751 писал(а):

dimkadimon
Но, в целом, вот из подобных "мелочей" и зависит скорость работы. Вопрос состоит в том, с чего начинать? Рисовать всю картину в целом и только потом прорисовывать детали, либо аккуратно заполнять пустой холст хорошо прорисованными деталями и в конце получить картину для мусорной корзины?

Незнаю как другие, но я сначала пишу минимальную программу которая работает. Пусть она будет самая тупая и медленная, но главное чтобы работала верно без ошибок. А вот потом уже добавляю всякие улучшения скорости и памяти. Иногда начинаю полностью заново, при этом убирая ненужные части старой программы.