|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
04.04.2018, 00:52 | #1 |
Пользователь
Регистрация: 04.04.2018
Сообщений: 16
|
Сколько вариантов окраски
Имеем 126 квадратов. Их надо раскрасить в 4 цвета (красный,синий, жёлтый, зеленый) В один цвет нельзя окрашивать более 41 квадрата где бы они не стояли. Сколько вариантов окраски.
Последний раз редактировалось stanislav55; 04.04.2018 в 01:11. |
04.04.2018, 07:41 | #2 |
Участник клуба
Регистрация: 03.06.2009
Сообщений: 1,814
|
комбинаторика...эх...
Программирование - это единственный способ заставить компьютер делать то, что тебе хочется, а не то, что приходится.
|
04.04.2018, 09:12 | #3 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Там же бешенные числа )) Можно попытаться динамическим программированием (+ длинная арифметика, очень длинная).
V(n) - число вариантов для n квадратов V(1) = 4 Для n<41: V(n+1) = V(n)*4 Для 41<=n<82: V(n+1) = V(n)*4 - (C(41,n)*3^(n-41))*4 где C(41,n) = n!/41!/(n-41)! (может и ошибся, идея - вычесть те варианты где перевалило за 41 у одного из цветов) Для 82<=n<123 уже два цвета может быть по 41, для 123<=n - 3 цвета, лень формулу выводить да и смысла не вижу ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 04.04.2018 в 09:17. |
04.04.2018, 09:46 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
согласен.
в "лоб" перебором не решишь. если порядок расположения имеет значение, тогда общее число вариантов раскраски 4^126 ~ 7.8E75 (75значное число) поэтому перебирать все варианты - это не выход. нужно думать над алгоритмом/формулой. |
04.04.2018, 10:12 | #5 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
С другой стороны там всего 10660 решений целочисленного уравнения:
a+b+c+d=126 где 3<=a,b,c,d<=41 для каждого решения посчитать число вариантов, а это реально, и сложить. И та же длинная арифметика
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 04.04.2018 в 10:18. |
04.04.2018, 22:50 | #6 |
Пользователь
Регистрация: 04.04.2018
Сообщений: 16
|
Квадраты расположены на одной линии.Значит имет.
|
04.04.2018, 22:53 | #7 | |
Пользователь
Регистрация: 04.04.2018
Сообщений: 16
|
Цитата:
Что надо чтобы было не лень |
|
05.04.2018, 23:59 | #8 |
Пользователь
Регистрация: 04.04.2018
Сообщений: 16
|
свыше перечисленами условиями может быть число вариантов меньше чем 4^125
Последний раз редактировалось stanislav55; 06.04.2018 в 00:21. |
06.04.2018, 17:57 | #9 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
|
06.04.2018, 18:38 | #10 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как узнать сколько сводных таблиц и сколько срезов на рабочем листе? | RISagitov | Microsoft Office Excel | 0 | 31.10.2015 19:30 |
Маленька проблема окраски | Dimka Wumok | Microsoft Office Excel | 16 | 28.10.2012 14:10 |
Скорректировать код окраски повторяющих значений в листе.. | Slavatron1984 | Microsoft Office Excel | 2 | 19.12.2011 17:06 |
Сколько стоит такая программка? И сколько по времени её сделать? | Палыч I | Фриланс | 8 | 10.09.2010 16:23 |
Помогите оценить, сколько может стоить проект. Его покупают - сколько взять? | grenles | Свободное общение | 4 | 16.07.2008 09:38 |