Версия для печати темы

Автор: sadek 16.4.2007, 5:01

Руководитель проекта
Прошу прощения за прошлую тему. C правилами ознакомился.

Подскажите как решить задачу?
Есть 3 красных шара 3 синих и 3 черных.
Сколькими способами можно расставить в ряд шары, так что бы ни какие 2 шара одного цвета не стояли рядом?

Автор: sadek 17.4.2007, 4:44

Подскажите хоть в каком направлении "рыть"

Автор: venja 17.4.2007, 9:44

Дык непросто. Видимо. Сходу мысли не приходят.

Автор: sadek 18.4.2007, 4:52

to venja

Я сам голову ломал неделю так чего-то и не получается. Вот решил спросить. Видимо точно не просто.

Автор: Lion 18.4.2007, 5:29

А нельзя так:6*4*4?

Автор: sadek 18.4.2007, 5:44

6*4*4
Это как понимать? В смысле пояснить

Автор: A_nn 18.4.2007, 5:51

Можно, конечно, дерево построить... Но это уж конечно крайний случай. Пока ничего лучше в голову не пришло.

Автор: sadek 18.4.2007, 5:54

to A_nn
Это уж действительно крайний вариант

Автор: Lion 18.4.2007, 9:28

"6*4*4"
Да, это не правильно.

Автор: Ботаник 18.4.2007, 10:10

А можно мне сказать? Я вот забил на мудрые формулы и по-простому построил дерево. Привожу текст программы для Excel:
[attachmentid=104]
Программа нашла 174 варианта размещения. В отсутствии "двойников" я убедился кондово - затянул найденные расстановки в Access и построил по этому полю индекс без повторений. Проблема в другом: как доказать, что я ни чего не пропустил? Программа не может являться доказательством. Может быть кто-нибудь предложит вариант, отсутствующий среди найденных?

Автор: sadek 18.4.2007, 13:07

to Ботаник

я тоже на delphi прогу написал, просто перебрал все варианты получилось 174 как и у тебя. А вот как быть с мудрыми формулами???

Автор: Ботаник 18.4.2007, 14:40

Программа, которую ты накарябал, и есть твоё

решение этой задачи.

Вот если преподаватель не примет его, тогда и будем думать

Автор: Black Ghost 18.4.2007, 18:38

Если эта комбинаторная задача задана математиком, а не преподавателем информатики, то скорее всего он будет требовать аналитическое решение, а не программу.

Рассуждения Liona подтолкнули меня довести это направление до конца, т.е. сделать в лоб
Разбиваем ряд из 9 шаров на последовательные тройки.
Занумеруем шары разными цифрами для удобства

Дальше рассматриваем случаи
1.случай, когда в каждой тройке все шары разного цвета
123 123 123
321 213 213
и т.д.
3!*4*4=96 способов

2. случай, когда во всех тройках есть 2 шара одинакового цвета
121 313 232
212 323 131
и т.д.
3!=6 способов

3. случай, когда на первом месте стоит тройка шаров с разными цветами,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
идентичен случаю 4

4. случай, когда на последнем месте стоит тройка, в которой все шары разного цвета,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
121 323 123
212 313 123
313 212 123
131 232 123
4*3!=24 способов

5. случай, когда тройка шаров с разными цветами стоит посередине,
при этом в двух оставшихся тройках будет по 2 шара одинакового цвета
232 123 131
313 123 212
323 123 121
232 123 131

4*3!=24 способов, когда тройка, в которой все шары разного цвета, посредине

Считаем: 96+6+24+24+24=174, что собственно и нужно
Если у нас ответы совпали, то, скорее всего, я ничего не упустил (хотя всё может быть)
И не придется рисовать никаких деревьев

Еще бы нужно написать, что не получится случая, когда только в одной тройке будут 2 шара одинакового цвета, а в каждой из оставшихся троек будут шары разного цвета, но что-то неохота

Автор: Lion 19.4.2007, 1:37

Да, я потом поняла, что ограничилась только 1-ым случаем...

Автор: sadek 19.4.2007, 7:20

to Black Ghost

Задача комбинаторная не информатика.

Спасибо за предоставленный способ.

И Lion спасибо за мысль

Наверно другого решения нет.

Автор: Ботаник 19.4.2007, 10:33

Снова очень извиняюсь...

2 sadek:
Вы, уважаемый, чему так радуетесь? Советую сличить решение, данное Black Ghost, с тем, что выдала ваша программа на delphi. Вас ждёт сюрприз. Наверное другое решение всё-таки существует

2 Black Ghost:
Во втором случае у вас шесть вариантов расклада. Могу предложить больше. Например так:
1) КЧК СКС ЧСЧ
2) КЧК ЧСЧ СКС
3) СКС КЧК ЧСЧ
4) СКС ЧСЧ КЧК
5) СЧС КСК ЧКЧ
6) СЧС ЧКЧ КСК
7) КСК ЧКЧ СЧС
и это, увы, не всё…

Автор: Black Ghost 19.4.2007, 11:09

Да... надо подумать еще
К-1 Ч-2 С-3
121 232 313 меняем всевозможными способами 1, 2, 3 местами 3! -способами
121 313 232 - здесь всё - то же самое 3! способами
я об этом что-то не подумал
2*3!=12
Надо выписать их все... и убедиться, так ли это...

Автор: sadek 19.4.2007, 11:39

Опытным путем, следуя совету "Ботаник", выяснено
1 способ - 96 вариантов
2 способ - 12 вариантов !!!
3 способ - 24 варианта
4 способ - 18 вариантов !!!
5 способ - 24 варианта
способы согласно предложенных Black Ghost

Автор: Ботаник 19.4.2007, 11:40

1) чем этот способ будет отличаться от простроения дерева? Точно такое же нестрогое решение "на пальцах".
2) если во втором варианте раскладов стало больше, то из каких вариантов отнимать, чтобы сумма не изменилась? Или не отнимать? Ведь не факт, что 174 - верное число.

Процесс решения мы заменили подгонкой под готовый (возможно неверный) ответ, найденный экспериментальным путём.

Автор: sadek 19.4.2007, 11:42

вот и получается во втором способе прибавили 6, а в четветром отняли 6

Автор: A_nn 19.4.2007, 11:48

Да, что-то не получается нормального метода... Единственное, что облегчает задачу, так это фиксирование первых двух шаров (что приводит к уменьшению в 6 раз). Но не избавляет от примитивного перебора...
Надо думать...

Автор: Black Ghost 19.4.2007, 11:51

Вот это точно