2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 60, 61, 62, 63, 64, 65, 66, 67  След.
 
 Re: Prime Sums
Сообщение11.01.2013, 11:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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) в автоматическом режиме? Возможно ли это?

 Профиль  
                  
 
 Re: Prime Sums
Сообщение11.01.2013, 16:16 


02/11/12
141
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.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение11.01.2013, 17:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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
вы ушли в подполье? :D
Где ваша программа для "шестёрки", которая для конкретной схемы-разбиения работает минуты-секунды?
У меня, к сожалению, программа для конкретной схемы-разбиения работает часы и ничего не находит :-(

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 09:03 
Заслуженный участник
Аватара пользователя


19/12/10
1546

(svb)

svb в сообщении #670175 писал(а):
Интересный квадрат :D

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 10:27 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak
Цитата:
svb
вы ушли в подполье? :D
Где ваша программа для "шестёрки", которая для конкретной схемы-разбиения работает минуты-секунды?
И это я такое брякнул? :D Что-то смутно вспоминаю - помню для очистки совести запустил программу и для страховки к секундам добавил минуты.

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

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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 11:03 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

Я тоже очень устала (параллельно ещё квадратами Стенли занимаюсь).
Но вот непрестанно думаю: почему у svb программа выполняется секунды-минуты, а у меня часы?
Может быть, это ещё от схемы зависит?
Или у вас действительно есть "чудеса перебора" :wink:
Кстати, для предыдущей схемы (с оценкой 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.

Изображение

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 12:20 
Заблокирован
Аватара пользователя


22/03/08

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

Изображение

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

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

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

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

Изображение

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

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

Изображение

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 13:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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)

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 15:09 
Аватара пользователя


20/01/10
766
Нижний Новгород
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$ - индексы крайних простых чисел, между которыми может находиться искомое простое число. Можно использовать линейный поиск, но в этом случае время работы резко возрастает.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 15:35 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 15:53 


02/11/12
141
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.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 16:06 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 16:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #670717 писал(а):
Можно использовать линейный поиск, но в этом случае время работы резко возрастает.

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 16:22 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение12.01.2013, 16:48 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
svb в сообщении #670751 писал(а):
dimkadimon
Но, в целом, вот из подобных "мелочей" и зависит скорость работы. Вопрос состоит в том, с чего начинать? Рисовать всю картину в целом и только потом прорисовывать детали, либо аккуратно заполнять пустой холст хорошо прорисованными деталями и в конце получить картину для мусорной корзины?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 60, 61, 62, 63, 64, 65, 66, 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group