2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 18:47 
Заслуженный участник


12/09/10
1547
Есть известная задача: в данном множестве из $N$ элементов найти подмножество с заданной суммой элементов.
Алгоритм следующий: множество разбиваем на две примерно равные части. Например, если дано 44 числа, то на 2 множества по 22 элемента. Для каждой части формируем все подмножества и находим сумму их элементов. Итого у нас получается два массива по $2^{N/2}$ элемента. Сортируем один из массивов. Тогда, пробегая по неотсортированному массиву, мы можем для каждого его элемента найти бинарным поиском в сортированном массиве нужную "добавку", если таковая имеется.
Имея даже не сильно мощный компьютер можно за приемлемое время (несколько минут) управиться со множеством из 50 элементов. 44 элемента потребуют же всего несколько секунд.
А у Вас задача еще несколько проще. Количество элементов искомого подмножества тоже задано. Это сильно сужает перебор.

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 18:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Cash в сообщении #735984 писал(а):
А у Вас задача еще несколько проще. Количество элементов искомого подмножества тоже задано. Это сильно сужает перебор.

Да, у меня задача совсем простая :D
И я её уже почти решила, осталось всего 5 шагов. Конечно, и эти шаги можно осилить, но уже за бОльшее время. До этого программа работала от нескольких секунд вначале до нескольких минут в конце.
Если описанный вами метод даёт решение за несколько секунд, решите, пожалуйста, задачу и скажите: 11 "правильных" массивов - это окончательный результат :wink:

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

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 19:06 
Заслуженный участник


12/09/10
1547
Можете привести задачу полностью?
Во множестве из 44 первых нечетных простых чисел выделить подмножество из 36 элементов с суммой 2628? Правильно?

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 19:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Правильно.

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 19:12 
Заслуженный участник


04/05/09
4582
Nataly-Mak в сообщении #735988 писал(а):
Если описанный вами метод даёт решение за несколько секунд, решите, пожалуйста, задачу и скажите: 11 "правильных" массивов - это окончательный результат :wink:
В эти несколько секунд не входит время на написание программы. ;-)

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 19:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну да, если бы программа уже была написана, то результат был бы уже в студии :D

-- Ср июн 12, 2013 20:38:21 --

А тем временем моя программа одолела ещё один шаг:

Код:
Начало массива (вариант 5+31):

3  5  7  11  13

Сумма всех чисел в массиве равна 2628.
S1=39, S2=2628-39=2589

17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  157  197
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  163  191
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  173  181
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  151  173  179
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  157  167  179
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  163  167  173
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  151  163  179
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  157  163  173
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  139  149  151  167  173
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  157  173
17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  131  137  139  149  151  163  167

KOLICHESTVO MASSIVOV 11

Этот вариант программа обрабатывала около часа. Массивов по-прежнему найдено 11.
Осталось всего 4 шага, но самые долгоиграющие.

-- Ср июн 12, 2013 20:55:55 --

venco в сообщении #735996 писал(а):
В эти несколько секунд не входит время на написание программы. ;-)

Я свою программу написала за 5 минут:

(Оффтоп)

Код:
#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
LOCAL I,J,K,Z,W,I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,S,S1 AS LONG
LOCAL I17,I18,I19,I20,I21,I22,I23,I24,I25,I26,I27,I28,I29,I30,I31,I32,I33,I34,I35 AS LONG
                                                               
Z=39:W=31:S=2589
DIM A(W) AS LONG,P(Z) AS LONG

OPEN "A1.TXT" FOR INPUT AS #1
FOR I=1 TO Z
INPUT #1,P(I)
NEXT I
CLOSE #1

OPEN "A2.TXT" FOR OUTPUT AS #1

K=0
FOR I1=1 TO Z
PRINT "I1=";I1
A(1)=P(I1)
FOR I2=I1+1 TO Z
A(2)=P(I2)
FOR I3=I2+1 TO Z
A(3)=P(I3)
FOR I4=I3+1 TO Z
A(4)=P(I4)
FOR I5=I4+1 TO Z
A(5)=P(I5)
FOR I6=I5+1 TO Z
A(6)=P(I6)
FOR I7=I6+1 TO Z
A(7)=P(I7)
FOR I8=I7+1 TO Z
A(8)=P(I8)
FOR I9=I8+1 TO Z
A(9)=P(I9)
FOR I10=I9+1 TO Z
A(10)=P(I10)
FOR I11=I10+1 TO Z
A(11)=P(I11)
FOR I12=I11+1 TO Z
A(12)=P(I12)
FOR I13=I12+1 TO Z
A(13)=P(I13)
FOR I14=I13+1 TO Z
A(14)=P(I14)
FOR I15=I14+1 TO Z
A(15)=P(I15)
FOR I16=I15+1 TO Z
A(16)=P(I16)
FOR I17=I16+1 TO Z
A(17)=P(I17)
FOR I18=I17+1 TO Z
A(18)=P(I18)
FOR I19=I18+1 TO Z
A(19)=P(I19)
FOR I20=I19+1 TO Z
A(20)=P(I20)
FOR I21=I20+1 TO Z
A(21)=P(I21)
FOR I22=I21+1 TO Z
A(22)=P(I22)
FOR I23=I22+1 TO Z
A(23)=P(I23)
FOR I24=I23+1 TO Z
A(24)=P(I24)
FOR I25=I24+1 TO Z
A(25)=P(I25)
FOR I26=I25+1 TO Z
A(26)=P(I26)
FOR I27=I26+1 TO Z
A(27)=P(I27)
FOR I28=I27+1 TO Z
A(28)=P(I28)
FOR I29=I28+1 TO Z
A(29)=P(I29)
FOR I30=I29+1 TO Z
A(30)=P(I30)
FOR I31=I30+1 TO Z
A(31)=P(I31)

S1=0
FOR I=1 TO W:S1=S1+A(I):NEXT I
IF S1<>S THEN 940

K=K+1
FOR I=1 TO W:PRINT #1,A(I);:NEXT I
PRINT #1,

940 NEXT I31
942 NEXT I30
944 NEXT I29
946 NEXT I28
948 NEXT I27
950 NEXT I26
952 NEXT I25
954 NEXT I24
956 NEXT I23
958 NEXT I22
960 NEXT I21
962 NEXT I20
964 NEXT I19
966 NEXT I18
968 NEXT I17
970 NEXT I16
972 NEXT I15
974 NEXT I14
976 NEXT I13
978 NEXT I12
980 NEXT I11
982 NEXT I10
984 NEXT I9
986 NEXT I8
988 NEXT I7
990 NEXT I6
992 NEXT I5
994 NEXT I4
996 NEXT I3
998 NEXT I2
1000 NEXT I1

2000 PRINT #1,:PRINT #1,"KOLICHESTVO MASSIVOV";K
CLOSE #1
END

END FUNCTION

Тут писать-то нечего. Несколько вложенных циклов и проверка условия.
Дальше просто добавляю ещё один вложенный цикл или наоборот убираю.
И много памяти для моей программы не требуется.

Очень хотелось бы посмотреть на вашу программу, которая решает задачу менее чем за секунду :wink:
Какое время требуется на написание такой программы, по вашим прикидкам?

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 20:14 
Заслуженный участник


04/05/09
4582
Nataly-Mak в сообщении #736000 писал(а):
И много памяти для моей программы не требуется.
Ну да, дурное дело не хитрое. ;-)

Nataly-Mak в сообщении #736000 писал(а):
Очень хотелось бы посмотреть на вашу программу, которая решает задачу менее чем за секунду :wink:
А что мне за это будет?

Nataly-Mak в сообщении #736000 писал(а):
Какое время требуется на написание такой программы, по вашим прикидкам?
Около 10-ти минут, хотя баги можно долго ловить...

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 20:35 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
venco в сообщении #736013 писал(а):
Nataly-Mak в сообщении #736000 писал(а):
И много памяти для моей программы не требуется.
Ну да, дурное дело не хитрое. ;-)

Спасибо за комплимент :wink:

Цитата:
А что мне за это будет?

А чего бы вы хотели? :D

Цитата:
Около 10-ти минут, хотя баги можно долго ловить...

А вот в "дурных" программах багов не бывает :wink:

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 20:37 
Заслуженный участник


04/05/09
4582
Получилось 17 минут. :-(
А программа работает меньше 20 миллисекунд.

-- Ср июн 12, 2013 13:39:18 --

Ну и 11 наборов чисел, которые надо исключать:
Код:
151 163 167 173 179 181 191 193
151 157 167 173 179 181 193 197
151 157 163 167 179 191 193 197
149 157 163 167 181 191 193 197
149 151 163 173 181 191 193 197
139 157 167 173 181 191 193 197
149 151 157 179 181 191 193 197
137 157 163 179 181 191 193 197
139 151 167 179 181 191 193 197
127 163 167 179 181 191 193 197
127 157 173 179 181 191 193 197

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 20:43 
Заслуженный участник


12/09/10
1547

(Оффтоп)

Опередили... Математика на работе - пришлось сортировку самому писать :(. Итого почти час потратил...

Nataly-Mak, Вы правы - 11 наборов всего.
Код:
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+131+137+139+149+151+163+167
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+131+137+139+149+151+157+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+149+157+163+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+139+149+151+167+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+163+167+173
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+149+151+163+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+157+167+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+151+173+179
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+173+181
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+163+191
3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+101+103+107+109+113+127+131+137+139+149+157+197

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение12.06.2013, 20:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
venco
Ага, значит, всё-таки 11 массивов и есть.
Спасибо-о-о :wink:

А программу не покажете? Вдруг ещё кому пригодится решать подобные задачи.

-- Ср июн 12, 2013 21:50:24 --

Cash в сообщении #736034 писал(а):
Опередили... Математика на работе - пришлось сортировку самому писать :(. Итого почти час потратил...

Не огорчайтесь :-)
И вам огромное спасибо. Ещё раз подтвердили результат.
Теперь могу не сомневаться уже в правильности этого результата.
И свои последние долгоиграющие 4 шага делать не буду :?

-- Ср июн 12, 2013 22:21:15 --

У меня задач переборных очень много, прямо пачками лежат на столе :D
Некоторые удаётся решить сразу, другие - сильно подумав, а третьи совсем никак не поддаются.
Например, здесь
post735258.html#p735258
одна из таких задач описана.

Давно она на мне "висит"; бросила тогда, а теперь вот опять она "всплыла". Надо бы сильно подумать :?

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение03.07.2013, 17:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Уважаемые коллеги!
Ещё переборная задачка у меня возникла :-)
Пожалуйста, подскажите, с чего начать, как сделать простенькую программку.
Сама немного подумала, но мало :D Ещё жара, мозги расплавились.

Есть массив простых чисел близнецов, у меня в нём записаны только первые числа из каждой пары близнецов.
Вот начало массива:

Код:
3        5       11       17       29       41       59       71
      101      107      137      149      179      191      197      227
      239      269      281      311      347      419      431      461
      521      569      599      617      641      659      809      821
      827      857      881     1019     1031     1049     1061     1091
     1151     1229     1277     1289     1301     1319     1427     1451
     1481     1487     1607     1619     1667     1697     1721     1787
     1871     1877     1931     1949     1997     2027     2081     2087
     2111     2129     2141     2237     2267     2309     2339     2381
     2549     2591     2657     2687     2711     2729     2789     2801
     2969     2999     3119     3167     3251     3257     3299     3329
. . . . . .

Задача такая:
требуется сформировать несколько первых массивов чисел (для начала штук 10-15), состоящих из 18 пар близнецов (из 36 чисел) таких, что сумма всех чисел массива кратна 6.

Простая задача. Сейчас мозги остужу немного и буду думать.
Жду подсказок :?

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение03.07.2013, 18:37 
Заслуженный участник


11/11/07
1198
Москва
Если $p$ и $p+2$ - простые близнецы, $p > 3$, то $p + p + 2$ кратно 6. Так что берете любые 18 пар близнецов, кроме пары $(3, 5)$, и получите сумму, кратную 6.

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение03.07.2013, 18:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Действительно.
Спасибо большое!
И никакой программы воообще не надо.

 Профиль  
                  
 
 Re: Переборная задача, есть ли шанс?
Сообщение19.07.2013, 05:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Задача такая возникла... очень долго работает программа, на несколько суток растянется проверка.
Нет ли каких-то идей по оптимизации программы?

Программа проверяет построение примитивного квадрата из 32 пар комплементарных чисел.
Пары комплементарных чисел - это пары чисел с одинаковой суммой (называемой константой комплементарности).
Есть массив, состоящий из 218 пар комплементарных чисел.
Иными словами: массив состоит из двух равных частей A и B таких, что для каждого элемента m из А существует ровно один элемент n в В, что m+n=K.
Для проверки берутся все различные массивы (массивы считаются раличными, если они отличаются по крайней мере одной парой), состоящие ровно из 32 пар комплементарных чисел. Ну, или проверяется сразу весь массив полным перебором.
Понятно, что массивов из 32 чисел будет огромное количество.
И в любом случае проверка очень и очень длинная получается.

Один массив из 32 пар проверяется довольно быстро. Но если бы он был один или хотя бы штук 20-30. Но их будет... я даже не берусь сосчитать сколько.

Можно ли здесь применить многопоточное программирование?
(о котором только слышала, но применять его не умею)

Кто может помочь советом и/или делом :-)

Пример

Код:
19  83  1019  1583  3229  3793  4729  4793
103  167  1103  1667  3313  3877  4813  4877
499  563  1499  2063  3709  4273  5209  5273
523  587  1523  2087  3733  4297  5233  5297
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0
S=24024

Это единственное известное мне решение данной задачи.
Здесь массив состоит из 195 пар комплементарных чисел.
Те элементы, которые здесь нули, это как раз элементы из соответствующей пары, то есть они однозначно определяются 32 найденными элементами квадрата.
Константа комплементарности здесь равна 6006.
S=24024 это индекс примитивного квадрата (S=4K).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 64 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

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



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

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


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

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