|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
23.03.2017, 18:06 | #1 |
Регистрация: 20.10.2016
Сообщений: 3
|
Алгоритм, который определяет в каком порядке сидели мыши
Доброго времени суток. Такая вот задачка: N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.
Даже не знаю есть ли смысл скидывать то, что у меня есть ибо там можно сказать что ничего и нет, вообще не могу понять как ее сделать. Находил, так сказать, словесные решения, но что-то их реализовать у меня не получилось. Может у кого-нибудь есть идеи? Заранее благодарен. |
24.03.2017, 14:11 | #2 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Так а разве это возможно?? тут же вариантов рассадки мышей может быть очень много. Они ведь сидят не чередующемся порядке Б С Б С Б С ...
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
24.03.2017, 15:15 | #3 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
а почему нет?
если это действительно так, то нужно найти один любой, который удовлетворяет условиям задачи. p.s. впрочем, согласен, в условии должно быть отмечено, что "если таких вариантов несколько - выведите любой подходящий". а вообще это модификация известной классической задачи: Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом ещё ТЫЦ Последний раз редактировалось Serge_Bliznykov; 24.03.2017 в 15:19. |
24.03.2017, 20:43 | #4 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
В прямом решении может и возможно .. но вот восстановить исходный порядок. Это же бесконечное количество решений.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
25.03.2017, 18:42 | #5 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Как вариант (решение с хвоста).
Выбираем конечное состояние: оставшиеся мышки сидят подряд - все серые а затем все белые (можем рассадить и рандомно). Выбираем первую любую мышку и при движении против часовой стрелки начинаем вставлять: всех белых мышек (M-L), а затем - всех серых (N-K). Последняя вставленная мышка будет серой. С нее и был начат поход кошки. В результате получим один из вариантов решения. Другая версия - вставлять мышек по очереди (белая, серая). Тут важно выяснить, каких мышек было съедено больше, с тем, что бы последней была вставлена серая. Реализовать можно с помощью кольцевого списка. PS: Надо представить алгоритм поиска решения - представлен. В условии задачи нет ограничений на число мышей и число циклов кошки. При некоторых разумных предположениях о прожорливости кошки задача может быть решена (как мне кажется). Как-то так, ...
Как-то так, ...
|
27.03.2017, 17:56 | #6 | |
Пользователь
Регистрация: 12.01.2017
Сообщений: 18
|
Цитата:
|
|
27.03.2017, 19:02 | #7 | |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Цитата:
Может есть какое то дополнительное условие?
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
|
28.03.2017, 22:41 | #8 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Цитата:
Поскольку никаких дополнительных данных нет, то можно строить только предположения. Например: - M и N так велики, что кошка съедает всех мышек не завершив круг. Просто объелась. Можно предположить, что мышки сидели так, что L -серых и K -белых кошка съела за L+K шагов: (L+K)*S <=N+M - Кошка ела по кругу до тех пор, пока не попала на пустое место (мышка была съедена ранее). - После съедания мышки оставшиеся сдвигаются так, что образуется новый, полностью заполненный круг. - ... тут предлагается и самому придумать очередной вариант. Вам нужен алгоритм, который восстановит размещение мышек в полностью неопределенной ситуации. В таком случае может быть огромное множество решений. Вам предложен один из вариантов. PS: Вы ведь не станете отрицать, что, например, кошка могла вначале съесть K-1 серую мышку (последняя оставлена на десерт ), а затем всех L- белых мышек, закончив обед десертом. Так о чем мы тут рассуждаем ... Как-то так, ...
Как-то так, ...
|
|
30.03.2017, 16:50 | #9 |
Пользователь
Регистрация: 12.01.2017
Сообщений: 18
|
|
30.03.2017, 16:53 | #10 |
Пользователь
Регистрация: 12.01.2017
Сообщений: 18
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
как правильно занулить бит,который определяет знак, в типе double | КРИЖ | Общие вопросы C/C++ | 7 | 25.11.2013 07:04 |
В каком порядке учить языки? | guest0147 | Свободное общение | 6 | 27.03.2013 10:51 |
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательност | FIREMAX | Помощь студентам | 1 | 02.02.2013 12:50 |
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательност | FIREMAX | Помощь студентам | 3 | 28.11.2012 22:52 |
Составить алгоритм, который по введённому N, (0<=N<=3 000 000 000) определяет, какое число стоит на N-ом месте в последовательност | FIREMAX | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 28.11.2012 20:54 |