Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
maytonТы уже опубликовал это где-то в гитхабе? Я хотел сделать несколько changes. Залил. Экспериментируй ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 18:15 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovА если совсем углубиться (ударение на втором у), то можно ещё ввести соотношения между объектами (окружность, диагональ). А если и ...., то можно вообще рисовать произвольные картинки, только успевай выстраивать новые схемы, которые будут похожи на 21794700 Так что, вариантов обобщения и углубления много. Я именно про это и говорю. Есть граф. У него есть подграфы. Есть вершины с весами. Часть вершин - предопределены. Часть - неизвестны. Подграфы связаны констрейнтами. Например - где-то масса подграфа должна быть константой. (К началу задачи еще и эта константа - неизвестна). Имеется также порождающий генератор (или набор генераторов) которые выдают на выходе поток чисел которыми надо заполнять вершины. Имеется цель - заполнить все вершины значениями из генератора при условии выполнения всех кострейнтов. И я имел в виду именно такую постановку. Дано: G - множество графов. V - множество вершин. E - множество ребер. Vс - подмножество вершин с весами. A - порождающий алгоритм(ы) заполнения вершин. С - множество констрейнтов (ограничений) на множество графов. И на меньшее я в топике не соглашусь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 18:45 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Можно ещё один цикл убирать. Получаем: Шаг 1. цикл по х15 - определяем а1 Шаг 2. циклs по х12 и х16 Здесь определяем в следующей последовательности: х14 (х14 + х16 = 20 или 19)( 21793947 ), х13, а2, а3, х8, х9, х10, х11. Далее - есть две внутренние окружности, где можно проверить соотношение: х12, х13, а2, а3, х8, х9, х10, х11. - есть средняя окружность, где можно проверить соотношение х8, х9, х10, х11 Шаг 3. Цикл по х2 в а1 - определяем х5 Шаг 4. Цикл по х3 в а2 – определяем х6 Шаг 5. Цикл по х4 в а3 – определяем х7 Всего 6 циклов. 3 основных и 3 вспомогательных (попарные перестановки 6 чисел) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:07 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
maytonGennadiy UsovА если совсем углубиться (ударение на втором у), то можно ещё ввести соотношения между объектами (окружность, диагональ). А если и ...., то можно вообще рисовать произвольные картинки, только успевай выстраивать новые схемы, которые будут похожи на 21794700 Так что, вариантов обобщения и углубления много. Я именно про это и говорю. Есть граф. У него есть подграфы. Есть вершины с весами. Часть вершин - предопределены. Часть - неизвестны. Подграфы связаны констрейнтами. Например - где-то масса подграфа должна быть константой. (К началу задачи еще и эта константа - неизвестна). Имеется также порождающий генератор (или набор генераторов) которые выдают на выходе поток чисел которыми надо заполнять вершины. Имеется цель - заполнить все вершины значениями из генератора при условии выполнения всех кострейнтов. И я имел в виду именно такую постановку. Дано: G - множество графов. V - множество вершин. E - множество ребер. Vс - подмножество вершин с весами. A - порождающий алгоритм(ы) заполнения вершин. С - множество констрейнтов (ограничений) на множество графов. И на меньшее я в топике не соглашусь.И что этому мешает? Надо с чего-то начать... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:11 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
С языка описания. Описать граф. Потом по этому описанию сгенерировать алгоритм. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:17 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
alex55555maytonДоказательством корректнсти программы является ее работа и ее результат. Но программисты же получают не просто результат, а оптимальный результат. Так вот по оптимальности решения полным перебором возможны большие вопросы. А где вы увидели полный перебор? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:18 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
maytonС языка описания. Описать граф. Потом по этому описанию сгенерировать алгоритм.Для этого нужен новый топик или достаточно существующего? Будем использовать опыт этого топика? Жду начала описания. Далее - развитие этого описания. Или сначала для тренировки обобщим имеющуюся задачку? 21794705 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:23 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Вам очень надо новый топик? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:24 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
maytonВам очень надо новый топик?Можно и в существующем. Я имею в виду название топика, если оно соответствует новой проблеме. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:26 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Да нет никакой проблемы. Есть "игры разума". И мы в них играем. Просто я говорю что в этих играх я бы не стал кодить конкретно данную задачу. Она мне неинтересна. Но мне интересны различные обобщения. Кроме того в каждом топике у меня есть скрытый интерес. Например здесь скрытый интерес - графы и Resouce Definition Language. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 19:33 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Сообщение 21794898 можно немножко поправить: Шаг 1. цикл по х15 - определяем а1 Шаг 2. цикл по х16 - определяем х14 (х14 + х16 = 20 или 19)( 21793947), Шаг 3. цикл по х12 Здесь определяем в следующей последовательности: х13, а2, а3, х8, х9, х10, х11. Далее - есть две внутренние окружности (которые ранее не "использовались"), где можно проверить соотношение: х12, х13, а2, а3, х8, х9, х10, х11. - есть средняя окружность (ранее не "использовалась"), где можно проверить соотношение х8, х9, х10, х11 Шаг 4. Цикл по х2 - определяем х5 из а1 Шаг 5. Цикл по х3 – определяем х6 из а2 Шаг 6. Цикл по х4 – определяем х7 из а3 Всего 6 циклов. 3 основных и 3 вспомогательных (попарные перестановки 6 чисел) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 21:23 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Теперь попробуем разобраться с а1, а2, и а3, для которых имеем 6 "свободных" чисел (если есть такое решение). Допустим, для каждого а1,а2,а3 получаем только одну пару чисел - один вариант разбивки чисел для а1, а2, а3. Тогда для а1 имеем 2 варианта решения, для а1 и а2 имеем 4 варианта решения, для а1, а2 и а3 имеем 8 вариантов решений. Если взглянуть на решения 21794557 , то получается, что - имеется одно решение для х1, х8, х9, ...., х17, - имеется два варианта разбивки 6 чисел для а1, а2, а3. То есть, всего 16 решений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 21:45 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonТы уже опубликовал это где-то в гитхабе? Я хотел сделать несколько changes. Залил. Экспериментируй Я пока в коде ничего не менял. Просто посмотрел под Valgrind/Callgrind. Из за того что основное тело алгоритма представляет собой колбасу без вызвов подпрограмм то callgrind не разбивает репорт в разрезе каждой функции. Грубо говоря в отчоте callgrind видно 85 вызовов буст-овского nextpermutation. А это неинтересно с точки зрения анализа реализации Если ее зарефакторить так чтобы каждый цикл был функцией тогда калгринд дал-бы более материальный отчот. Конечно это можно все эмулировать счетчиками и логгированием но как-то хотелось доверять технологии. Trust to technology bro... :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 22:06 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
85 миллионов вызовов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 22:07 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Картинка с профилированием. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 22:13 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Глупый codeblocks. Где в нём рефакторинг? Где extract procedure... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 22:18 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovЕсли взглянуть на решения 21794557 , то получается, что - имеется одно решение для х1, х8, х9, ...., х17, - имеется два варианта разбивки 6 чисел для а1, а2, а3. То есть, всего 16 решений.Только сейчас до меня дошло, что только одно основное решение! Раньше у нас было 12 уравнений и 15 неизвестных. Если вводятся а1, а2 и а3 вместо х2, х3, х4, х5, х6, х7, то имеем: 12 уравнений и 12 неизвестных 1 решение!!! Завтра попробую расписать формулы. А кто-то поторопился написать программу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 22:27 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
В таком случае отчот Димы содержит некорректные расстановки. Можете их указать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 23:03 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Зарефакторил один внутренний цикл. Пока не сильно помогает понять картину вызвов. К компилляции добавил опцию -pg. Теперь можно смотреть gprof. Пока такая картинка. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2019, 23:45 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovРаньше у нас было 12 уравнений и 15 неизвестных. Если вводятся а1, а2 и а3 вместо х2, х3, х4, х5, х6, х7, то имеем: 12 уравнений и 12 неизвестных 1 решение!!! Завтра попробую расписать формулы. А кто-то поторопился написать программу. Не получилось! Уравнения превращаются в тождества Остаётся только все переменные выразить через х12,х15,х16 х1= К / 3 х14 = 20 – х16 Из большой окружности х13 = К – 32 – х15 – х12 Из диагоналей: а1 = К – х15 – 12 – х1 а2 = 32 + х15 + х12 – х16 – х1 а3 = К – х1 – 20 + х16 – х12 Далее проверка – малая окружность. Аналогично находим х8,х9,х19,х11 из внутренних окружностей, где они встречаются по одному. далее проверка, где они по два, далее проверка на средней окружности.maytonВ таком случае отчот Димы содержит некорректные расстановки. Можете их указать?Указать не могу. Остаётся перебор. Просто приведенные расчеты позволяют несколько сократить количество циклов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 06:47 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
В предыдущем сообщении получено уравнение из суммы все диагоналей:Gennadiy Usovх1= К / 3Получается, что из двух вариантов для х1 и х17 Gennadiy UsovА именно: 1)выкидываем 10, в центре 20, сумма круга (диаметра) 60 2)выкидываем 20, в центре 19, сумма круга (диаметра) 57.остаётся первый: 20 и 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 07:37 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
maytonDima Tпропущено... Залил. Экспериментируй Я пока в коде ничего не менял. Просто посмотрел под Valgrind/Callgrind. Из за того что основное тело алгоритма представляет собой колбасу без вызвов подпрограмм то callgrind не разбивает репорт в разрезе каждой функции. Грубо говоря в отчоте callgrind видно 85 вызовов буст-овского nextpermutation. А это неинтересно с точки зрения анализа реализации Если ее зарефакторить так чтобы каждый цикл был функцией тогда калгринд дал-бы более материальный отчот. Конечно это можно все эмулировать счетчиками и логгированием но как-то хотелось доверять технологии. Trust to technology bro... :) next_combination() это сочетания, по-другому это Код: plaintext 1. 2. 3. 4. можно написать так Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. std::next_permutation() это размещения. Можно так через циклы написать Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. Если в код заглянешь - все циклы вложенные, заменив next_combination() получим 9 циклов вместо 2, заменив std::next_permutation() - 11 циклов вместо двух. Итого +16 вложенных циклов. ИМХО это будет не код, а фарш какой-то. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 08:10 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Что тебя смущает? Следуй советам Фаулера. Делай функции как можно меньшего размера. Его рекомендации относились ко всем языкам включая C++. О преждевременной оптимизации не парься. О ней надо думать тогда, когда точно известен bottleneck. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 09:28 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Gennadiy UsovОстаётся только все переменные выразить через х12,х15,х16 Из большой окружности х13 = К – 32 – х15 – х12 Здесь можно организовать выборку сочетаний по 3 из 15 для определения х12,х15,х16. При этом будут отсеиваться те сочетания, для которых не подходит х13. Получаем 245 вариантов без учета отсеянных. Если сочетания для варианта найдены, то имеем перестановки из 3-х элементов - всего 6 подвариантов для варианта. И для каждого подварианта определяются формулы из 21795083 с проверками. Всего 6 подвариантов для одного варианта. И не нужны циклы по каждому неизвестному. Есть один цикл для варианта и один цикл для подварианта. Для определения составляющих х2,х3,х4.х5,х6,х7 из оставшихся 6 чисел: Имеем сочетания 3 из 6 для каждой пары. Всего 20 сочетаний. И перестановки для этих пар из оставшихся 3-х чисел. Всего 6 перестановок. Итого 120 вариантов. Всё перемножать не следует, так как при работе с подвариантами будет очень большой отсев. В частности, в нашей задачке останется только один вариант, один подвариант, 2 сочетания и 8 перестановок для каждого сочетания. maytonВ таком случае отчот Димы содержит некорректные расстановки. Можете их указать?Продолжаются упрощения процесса вычислений: 1) Остаётся только 4 цикла: для варианта, для подварианта, для сочетания, для расстановки. 2) Идет работа не с объектами графа (окружности, диагонали), а с конкретными формулами вычисления неизвестных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 09:30 |
|
||
|
Как решить задачу по комбинаторике?
|
|||
|---|---|---|---|
|
#18+
Кстати, все формулы по определению неизвестных можно будет "загнать" в одну процедуру, из которой может быть несколько "аварийных выходов" в случае нарушения правила "свободного" числа или в случае выхода за границу массива чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2019, 09:37 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39765372&tid=1339994]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
176ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
50ms |
get tp. blocked users: |
1ms |
| others: | 14ms |
| total: | 278ms |

| 0 / 0 |
