Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.03.2017, 18:06   #1
WonderDog
 
Регистрация: 20.10.2016
Сообщений: 3
По умолчанию Алгоритм, который определяет в каком порядке сидели мыши

Доброго времени суток. Такая вот задачка: N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.
Даже не знаю есть ли смысл скидывать то, что у меня есть ибо там можно сказать что ничего и нет, вообще не могу понять как ее сделать. Находил, так сказать, словесные решения, но что-то их реализовать у меня не получилось. Может у кого-нибудь есть идеи? Заранее благодарен.
WonderDog вне форума Ответить с цитированием
Старый 24.03.2017, 14:11   #2
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Так а разве это возможно?? тут же вариантов рассадки мышей может быть очень много. Они ведь сидят не чередующемся порядке Б С Б С Б С ...
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 24.03.2017, 15:15   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
Так а разве это возможно??
а почему нет?


Цитата:
Сообщение от WorldMaster Посмотреть сообщение
тут же вариантов рассадки мышей может быть очень много.
если это действительно так, то нужно найти один любой, который удовлетворяет условиям задачи.

p.s. впрочем, согласен, в условии должно быть отмечено, что "если таких вариантов несколько - выведите любой подходящий".


а вообще это модификация известной классической задачи:
Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом
ещё ТЫЦ

Последний раз редактировалось Serge_Bliznykov; 24.03.2017 в 15:19.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.03.2017, 20:43   #4
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

В прямом решении может и возможно .. но вот восстановить исходный порядок. Это же бесконечное количество решений.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 25.03.2017, 18:42   #5
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Как вариант (решение с хвоста).
Выбираем конечное состояние: оставшиеся мышки сидят подряд - все серые а затем все белые (можем рассадить и рандомно).
Выбираем первую любую мышку и при движении против часовой стрелки начинаем вставлять:
всех белых мышек (M-L), а затем - всех серых (N-K).
Последняя вставленная мышка будет серой. С нее и был начат поход кошки.
В результате получим один из вариантов решения.
Другая версия - вставлять мышек по очереди (белая, серая). Тут важно выяснить, каких мышек было съедено больше, с тем, что бы последней была вставлена серая.
Реализовать можно с помощью кольцевого списка.
PS:
Надо представить алгоритм поиска решения - представлен.
В условии задачи нет ограничений на число мышей и число циклов кошки.
При некоторых разумных предположениях о прожорливости кошки задача может быть решена (как мне кажется).

Как-то так, ...
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 27.03.2017, 17:56   #6
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Как вариант (решение с хвоста).
Выбираем первую любую мышку и при движении против часовой стрелки начинаем вставлять:
всех белых мышек (M-L), а затем - всех серых (N-K).
Последняя вставленная мышка будет серой. С нее и был начат поход кошки.
В результате получим один из вариантов решения.
В том то и проблема, что мне не нужно заранее задавать "массив мышей", а сделать непосредственно алгоритм, который и выведет мне их изначальное расположение в зависимости от введенного количества оставшихся мышей. Собственно в этом то и проблема, если бы со старта можно было, то я бы примерно что-то да сделал может быть, а с этим вообще не догоняю.
WonderDoggy вне форума Ответить с цитированием
Старый 27.03.2017, 19:02   #7
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Цитата:
Сообщение от WonderDoggy Посмотреть сообщение
В том то и проблема, что мне не нужно заранее задавать "массив мышей", а сделать непосредственно алгоритм, который и выведет мне их изначальное расположение в зависимости от введенного количества оставшихся мышей.
Этих решений будет достаточно много. Это учебная задача или как??
Может есть какое то дополнительное условие?
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 28.03.2017, 22:41   #8
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Цитата:
В том то и проблема, что мне не нужно заранее задавать "массив мышей", ...
Про "массив мышей" я не писал. Список - это не массив.
Поскольку никаких дополнительных данных нет, то можно строить только предположения. Например:
- M и N так велики, что кошка съедает всех мышек не завершив круг. Просто объелась. Можно предположить, что мышки сидели так, что L -серых и K -белых кошка съела за L+K шагов: (L+K)*S <=N+M
- Кошка ела по кругу до тех пор, пока не попала на пустое место (мышка была съедена ранее).
- После съедания мышки оставшиеся сдвигаются так, что образуется новый, полностью заполненный круг.
- ... тут предлагается и самому придумать очередной вариант.

Вам нужен алгоритм, который восстановит размещение мышек в полностью неопределенной ситуации.
В таком случае может быть огромное множество решений.
Вам предложен один из вариантов.
PS: Вы ведь не станете отрицать, что, например, кошка могла вначале съесть K-1 серую мышку (последняя оставлена на десерт ), а затем всех L- белых мышек, закончив обед десертом.
Так о чем мы тут рассуждаем ...


Как-то так, ...
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 30.03.2017, 16:50   #9
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
Это учебная задача или как??
Да, учебная, ну если я правильно понял что вы имеете в виду.
Цитата:
Сообщение от WorldMaster Посмотреть сообщение
Может есть какое то дополнительное условие?
Это все условие, дополнительного нет.
WonderDoggy вне форума Ответить с цитированием
Старый 30.03.2017, 16:53   #10
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Список - это не массив
Списки то мне сказали и не использовать...

Цитата:
Сообщение от ViktorR Посмотреть сообщение
Вам предложен один из вариантов
За что я и благодарю, вы хоть отозвались и предложили
WonderDoggy вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как правильно занулить бит,который определяет знак, в типе 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