@gridex

Как решить задачу?

Задача может быть решена на любом языке программирования, мне вообще нужно понять логику, ибо никак не могу догадаться.
Существует некое поле, на котором растут кусты, кол-во кустов необходимо вводить вручную в промежутке от 2 до 100 . Эти кусты расположены по кругу. Некое существо "съедает" первый куст и переходит через один к следующему. Какой по счету P куст будет съеден последним?
В целом кажется легко, но не понятно становится после анализа входных/выходных данных. Они таковые:
Ввод число 5 --> ответ 4
Ввод число 7 --> ответ 2.
У кого какие идеи?
  • Вопрос задан
  • 410 просмотров
Решения вопроса 1
Fernus
@Fernus
Техник - Механик :)
Тебе код нужен прям?

Смотри...есть 5 кустов:

1. "Съедаем" всё через один, получается:
2,4
2. Если кусты остались, жрём дальше...получается:
4
3. Остаётся последний куст...жрём и смотрим, что сожрали последним:
4

P.S.: Тут даже третий пункт не нужен, если нет задачи "сожрать" :)
Т.е. надо через один рубить кусты по кругу пока не останется один...это и будет ответ...
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
wataru
@wataru
Это известная задача иосифа. По ссылке есть всякие решения. Вам подойдет самое тупое и медленное. У вас в задаче k прибито гвоздями к 2.

Понять те формулы можно примерно так. Съели мы первый куст, перешли ко второму. Теперь перенумеруем их, что останется? Та же самая задача, только с n-1 кустом. Только все кусты сдвинуты на k позиций и один номера у них на один уменьшены. Т.е. можно взять тот самый куст который при n-1 останется и найти, какой у него был номер до сдвига.
Ответ написан
@cicatrix
было бы большой ошибкой думать
Обновил - написал вроде бы работающий код решения в комментариях (С#).
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Исходя из примеров получается, что когда остаётся последний куст, то его съесть невозможно.
Самый простой вариант - организовать массив и N-1 раз циклически продвигаться по нему, отмечая "съеденные" элементы.
Ответ написан
Adamos
@Adamos
Очевидно, из цифр от 1 до N сразу логично выкинуть нечетные.
Следующим проходом из списка оставшихся будут выкидываться нечетные, если N четное, иначе четные.
И так каждую итерацию (вместо N будет длина предыдущего списка), пока длина списка оставшихся не будет равна 1.
Но гонять в памяти списки - это скучно, конечно. Лучше попробовать вывести формулу того, что выкидывается на каждом этапе. Глядишь, последнюю цифру удастся просто вычислить.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы