14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
1 | |
Варианты расстановок02.04.2014, 21:34. Показов 1985. Ответов 15
Метки нет (Все метки)
Всем привет
В голову пришла безумная мысль для прикола написать программу оптимизацию распила, то есть нужно все возможные варианты расстановок, а по ходу уже откидывать невозможные, и не подходящие суть, к примеру есть N групп объектов по M одинаковых элементов нужно найти все возможные варианты перестановок рассмотрим сочетания из N внутри мы получаем некое количество объектом которые нужно раставить допустим мы выбираем из 1 и 2 групп (2 из 4), получаем 2*M объектов перебираем варианты. из каждой гуппы берем по 1-M элементов, из 1ой группы взять 0 нельзя, так как такая выборка идет в варианте 1 из N получаем M^2 и... ( * ) ( * ) я хоть правильно считаю?
0
|
02.04.2014, 21:34 | |
Ответы с готовыми решениями:
15
Определить количество расстановок ладей на шахматной доске Вычислить количество расстановок фигур в шахматах Фишера Варианты расстановок Вывести все варианты расстановок |
831 / 678 / 101
Регистрация: 11.11.2012
Сообщений: 1,800
|
|
02.04.2014, 22:12 | 2 |
если б еще понимать, что))))
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
03.04.2014, 07:53 [ТС] | 3 |
не понятно написал?
или тема непонятна? а то нужно проверить ход мыслей, а то подзабыл я теор. вер.
0
|
4 / 4 / 0
Регистрация: 18.07.2013
Сообщений: 382
|
||||||
03.04.2014, 08:18 | 4 | |||||
Я над этим тоже морочился, над перебором.
Смотри: есть массивы N1 {1 2 3 4 5 6 ...} N2 {10 11 12 13 15 18...} .... Nn {21 25 19 12 14 33 ....} Складывал каждый элемент друг с другом N1[0]+N2[0]+..+Nn[0], потом N1[0]+N2[0]+..+Nn[1] и так цикл в цикле все перебираешь. вот код, если вообще правильно тебя понял.
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
03.04.2014, 08:28 [ТС] | 5 |
не совсем, я не обязан брать по 1 объекту из каждого множества
Пример 4 группы объектов в каждой группе по 4 объекта сколькими вариантами их можно скомбинировать количество в комбинации объектов любое от 1 до 16 получаем варианты только групп, без учета количество объектов в группе 1 2 3 4 12 13 14 ... 21... ... 134 ... 1234 и того 15 вариантов, но это только варианты группировок, а внутри них мы уже можем брать N-ое количество палок пример берем и 1 и 2 групп можем взять 1 из 1ой и 1 из 2, а можно 1-2,1-3....4-4 так понятнее, вот мне и нужно проверить правильно ли я посчитал количество всех вариантов ??? кто тут шарит в комбинаторики )))) а то комбинаторика у меня давно была.....
0
|
4 / 4 / 0
Регистрация: 18.07.2013
Сообщений: 382
|
|
03.04.2014, 08:45 | 6 |
Получается тебе не важно в переборе 21 или 12, 134 или 341 или 413 или 314, на каком месте стоит то или иное число?
Это вот так чтоли (к примеру) N1 {1 2 3 4}; N2 {5 6 7 8}; N3 {9 10 11 12}; N4 {13 14 15 16}. Количество не получится задать, оно у тебя в процессе будет считаться - это количество. P.S. Или ты все таки хочешь узнать количество комбинаций из m по k Добавлено через 2 минуты Покажи пример, как ты это видишь, чтоб понять хоть тебя.
0
|
831 / 678 / 101
Регистрация: 11.11.2012
Сообщений: 1,800
|
|
03.04.2014, 13:04 | 7 |
вот я тоже совершенно не понимаю, что ТС хочет.. Можете нормально сформулировать задачу?
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
03.04.2014, 19:03 [ТС] | 8 |
Пример
имеем 4 вида досок, их по 4 штуки 1, (1,2,3,4) 2, (5,6,7,8) 3, (9,10,11,12) 4, (13,14,15,16) нужно посчитать количество вариантов расстановки их для распила из длинной доски допустим посчитаем ВСЕ варианты, без учета длин (влезут не влезет) поскольку программе все равно нужно перебрать ВСЕ варианты и уже считать существует ли такая комбинация и так, считаем количество вариантов комбинирования видов, порядок не важен можем брать 1 из 4, 2,3,4 =15 вариантов для видов вот теперь нужно посчитать количество вариантов внутри каждой растановки рассмотрим вариант, что мы берем только 1ую группу (вид) мы можем взять от 1 до 4 досок = 4 варианта переставлять их нет смысла, они одинаковые вариант 2 группы к примеру 1 и 2 1, (1,2,3,4) 2, (5,6,7,8) сколько вариантов их расставить? из каждой берем любое количество >1 4^2 = 16 вариантов 4^количество видов а вот теперь как подсчитать их расстановку ? для примера мы возьмем вариант по 2 доски 1,2 и 5,6 1256 1265 это одинаковые так как 5=6 1256 5612 это разные варианты, так как порядок важен 1526 5162 1562 5126 это вроде все варианты, но только для случая когда по 2, а если 1 и 3, 1 и 4.... 4-4 теперь задача понятна ? вот как посчитать эти перестановки я что-то не понял и того получим ( * 4^k * (а вот блин фиг знает))
0
|
4 / 4 / 0
Регистрация: 18.07.2013
Сообщений: 382
|
|
04.04.2014, 07:54 | 9 |
4 Вида досок, понятно
по 4 доски в каждом виде.
Получается 1,2,3,4 - отличаются друг от друга? Какие характеристики у досок, по 2 метра в длину ) 40 мм в толщину. Или как! Я все равно не понял, прости меня. МОжно прям на пальцах. А это как понимать? pozitiv_rus, ты этим изначально занимаешься и тебе все ясно. А я не допираю.... Добавлено через 48 секунд Прости старика.
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
04.04.2014, 08:28 [ТС] | 10 |
1,2,3,4 равны, поэтому это и 1 вид досок, допустим по 40 см, но для программы на момент перебора размер неважен, нужно ВСЕ варианты перебирать
можем брать 1 из 4, 2,3,4 ну если рассуждать, то даже если мы пытаемся запихать для распила доски 1 длинны, то все равно вариантов расстановок несколько, мы может взять 1 из 4(одинаковых) , а может и 3 или все 4, и уже перебирая варианты смотрим, а существует ли такая расстановка(4 доски могут и не влесть...), а если существует устраивает ли она нас? может остается большой обрезок задача чисто теоретическая, практическая реализация данного алгоритма на мой взгляд излишня, весь перебор все равно не нужен, при небольших количествах, проще симплекс метод задача имеет больше теоретический интерес, хоть мозги размять
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
18.04.2014, 18:47 [ТС] | 11 |
что то тема так и померла, а я так и не могу понять как этот бред посчитать)
давайте всеже попробуем решить пример: есть 3 синих и 3 красных кубика сколькими способами их можно раставить если порядок идущих подряд одноцветных кубиков неважен ? ###### как не переставляй синии кубики под № 2, 3 и 5,6 это одинаковая растановка ###### тут 4! вариантов расставить синии не трогая красные, но такие расстановки равны всего 6! вариантов, а вот как посчитать ненужные
0
|
4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182
|
|
19.04.2014, 10:46 | 12 |
0
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
19.04.2014, 11:03 [ТС] | 13 |
нет 3 и 3, это просто я последние 2 дня жутко туплю...
а редактировать уже нельзя, вот зачем так сделали( ###### ###### тут как не переставляй они все одинаковые, 1 вариант к примеру 2 и 2, считаются прямо на пальцах, 3 и 3 уже можно напутать, а если 5 и 5 ) Добавлено через 11 минут пример 2 и 2 ##@@ #@@# @@## #@#@ @#@# остальные варианты это уже перестановки одинаковых идущих подряд, но они одинаковые и не считаются 3 и 3 ###@@@ @###@@ @@###@ @@@### ##@#@@ ##@@#@ ##@@@# #@##@@ #@@##@ #@@@## и т.д. все варианты
0
|
831 / 678 / 101
Регистрация: 11.11.2012
Сообщений: 1,800
|
|
20.04.2014, 02:05 | 14 |
это вроде как число перестановок с повторением:
число перестановок из n элементов, в которых первый элемент повторяется m1 раз, .... k-й - mk раз пример 2 и 2 (не хватает там @##@) Оно? Добавлено через 8 минут а еще это похоже на обычные сочетания - выбор мест для # (а @ уже заполняют оставшиеся места автоматически) т.к. я так и не въехала в Ваше начальное условие - решайте сами, что Вам подходит или ничего из этого
1
|
14 / 14 / 5
Регистрация: 13.07.2013
Сообщений: 230
|
|
20.04.2014, 11:32 [ТС] | 15 |
Вроде оно, эх подзабыл я комбинаторику
попробовал подставить для 1-1 1-2 3-3 вроде оно обе формулы дают одинаковый ответ, в принципе при таком решение даже запись одинаковая Добавлено через 59 минут хотя... если будет 3 вида, то нужна первая формула получил формулу n - видов по (m1,m2,m3...mn) штук комбинируем всеми способами вроде так
0
|
831 / 678 / 101
Регистрация: 11.11.2012
Сообщений: 1,800
|
|
20.04.2014, 15:19 | 16 |
0
|
20.04.2014, 15:19 | |
20.04.2014, 15:19 | |
Помогаю со студенческими работами здесь
16
Проверка правильности расстановок скобок Цикл для всех возможных расстановок Получить m расстановок 8 ферзей на шахматной доске Определить правильность расстановок скобок в тексте Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |