|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
30.04.2015, 15:49 | #1 | |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
Простая (или не очень) задача про окраску канареек
Доброе время суток, уважаемые форумчане! Хотелось бы прочитать ваши соображения по поводу следующей задачки:
Цитата:
Последний раз редактировалось Demius; 30.04.2015 в 16:53. Причина: Уточнение формулировки |
|
30.04.2015, 16:43 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
А на мой взгляд, совсем не простая задача!
тут же надо анализировать исходную окраску элементов и, исходя из неё, строить оптимальную стратегию по закраске в нужный (единый цвет). |
30.04.2015, 16:50 | #3 |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
Мы же можем при чтении цвета канареек выбрать тот цвет, который встречается чаще всего и в него всех остальных перекрашивать, или я не прав?
|
30.04.2015, 17:09 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
нет, это неверный алгоритм.
допустим, 1,3,5 и 7-я канарейки окрашены в зелёный цвет, 2-я в красный, а 4-я и 6-я - в фиолетовый. Тогда ОДНОЙ командой "Красить" A=1 B=фиолетовый мы всех окрасим в фиолетовый цвет. хотя преобладающий цвет явно зелёный... |
30.04.2015, 17:14 | #5 | |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
Цитата:
командой "Красить" A=1 B=фиолетовый мы всех окрасим в фиолетовый цвет за пять перекрашиваний (1,2,3,5,7), в то время как команда A=2 B=зелёный даст нам всего 3 перекрашивания (2,4,6). |
|
30.04.2015, 17:31 | #6 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
в данном случае согласен с Вами.
но я хотел проиллюстрировать другое. ладно Пусть 1-я, 2 и 3-я выкрашены в красный цвет 4-я - в фиолетовый 5-я - в зелёный 6-я - в фиолетовый в какой цвет и как будем красить? кстати, Цитата:
Нвапример, что будет иметь "наименьшее число": покрасить за 1 запрос 4 канарейки, или покрасить за 3 запроса 3 канарейки? |
|
30.04.2015, 17:40 | #7 | |
Пользователь
Регистрация: 03.12.2012
Сообщений: 24
|
Цитата:
2) Рассмотрим два случая:
Согласен, брать макс цвет не всегда выгодно. |
|
30.04.2015, 20:39 | #8 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Внимание! Написано в больном бреде. Кто поверит, тот сам виноват
Теперь по делу : Рассмотрим работу алгоритма на неком k-ом шаге : Всего у нас было k-1 канареек и p - кол-во различных цветов, в которых изначального были выкрашены первые k-1 канареек Теперь мы бахаем перебор : мы можем выкрасить оставшуюся канарейку в цвета 1..p. Как это делать : у нас будет матрица (k-1)*p. На пересечении i-ой строки и j-ого столбца будет находиться массив изменений, которыми мы производили для этих параметров. Тогда нам остается перебрать все решения для k-1 и clr = 1..p. И смотреть в массив, который находится в в матрице[k-1][clr]. Вот из него мы берем все ходы и смотрим кратно ли k ходу (ну или есть 1 - является ли k простым) Если нашли такой - матрица[k][clr] = матрица[k-1][clr], если нет - матрица[k][clr] = матрица[k-1][clr]+1 (потом напишу какой элемент добавить) Ответом же будет являться минимум из последней строки Но тут такой еще момент : когда на k-Ом шаге получается p+1. Тогда нужно решать туже проблему, но для одного цвета(эт несильно мудрено) Теперь про то, какой элемент добавить : я бы делал так : если красим все элементы кратные m, то ничего хорошего в голову не лезет, кроме как смотреть по всем делителям и определять сколько элементов перекрасим. Другой вариант - просто добавлять токующий элемент, но потом при добавлении следующего смотреть, можно ли объединить некий элемент предыдущего решения и нынешней позиции Вот. За сим откланиваюсь |
01.05.2015, 00:29 | #9 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Просто отвлечённые рассуждения.
1. Есть массив (канареек), заполненный числами (окрашенных цветами). 2. Пока предположим, что цвета абсолютно все разные. 3. Чтобы покрасить все в один цвет х (нам на данном этапе пояснений безразличен цвет) нужно дать серию команд Код:
На словах, какие команды подаются: покрасить простые, кратные простым (в том числе чётные). Последние, чтобы учесть случаи, когда индекс элемента (номер канарейки) - степень простого числа (например, 7*7*7*7). Теперь нужно решать задачу о минимальном покрытии. Для минимизации нужно учесть, что какие-то группы могут быть полностью одного цвета, а также наличие "особых" индексов (равных степеням одного простого числа), гарантированно добавляющих группу (тут можно минимизировать количество покрасок разложением степени на множетели). В общем, что-то напоминающее импликанты из Квайна-МакКласки. |
02.05.2015, 17:58 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Попробовал свой вариант (только решил отказаться от матрицы и считать по строкам)
Код:
Последний раз редактировалось Poma][a; 02.05.2015 в 21:14. |
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Очень сложная задача про векторы | logikal | Помощь студентам | 4 | 29.04.2014 22:29 |
Delphi - Очень простая задача! | honest | Помощь студентам | 1 | 11.06.2009 14:10 |
Не простая, но очень интересная задача (Pascal)! | Juliya_U | Паскаль, Turbo Pascal, PascalABC.NET | 29 | 17.04.2009 19:33 |