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

Question

[gridex]

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

Comments

[BigSmoke]

Вроде как последним должен быть съеден (общее количество кустов - 1). Непонятно почему во втором примере ответ 2

[Rsa97]

BigSmoke, Потому что когда мы движемся по кругу, то не считаем уже съеденные кусты. И последний оставшийся куст съесть невозможно.

[BigSmoke]

Rsa97, что-то у меня все равно ответ 2 во втором примере не получается.

1 2 3 4 5 <- начальное состояние
2 4 <- что осталось после первого прохода
4 <- что осталось после второго прохода
ответ 4

1 2 3 4 5 6 7 <- начальное состояние
2 4 6 <- что осталось после первого прохода
4 <- что осталось после второго прохода
ответ 4

[Saboteur]

BigSmoke, да, по идее во втором случае должен быть 6

[Rsa97]

BigSmoke, Похоже, что последний оставшийся куст не съедается, поскольку к нему нельзя попасть "через одного". Тогда всё сходится.
12345 -> x2345 -> .2x45 -> .2.4x -> .2.x.
Последний 4.

1234567 -> x234567 -> .2x4567 -> .2.4x67 -> .2.4.6x -> .2.x.6. -> .x...6.

Последний 2.

[Rsa97]

Bavashi, Третий раз повторяю. Последний куст съесть невозможно, потому что к нему невозможно пройти "через один".

Answer 1

[N]

Тебе код нужен прям?

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

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

P.S.: Тут даже третий пункт не нужен, если нет задачи "сожрать" :)
Т.е. надо через один рубить кусты по кругу пока не останется один...это и будет ответ...

Comments

[gridex]

Боже, действительно, совсем другая мысль просто пришла в голову, и от нее не отходил, благодарю, что направили на нужное русло.

[N]

Bavashi, Я ниже в другом ответе написал...у меня вроде как 6 выходит...
Главное автор ход мыслей понял походу...но мне тож интересно :)

[gridex]

N, если идти по кругу, то когда существо съест все возможные кусты, то остановится на втором. Всего останется второй и шестой куст, но так как их два, существо просто остается на втором и съедает его. То есть, если даже в тетради нарисовать 7 объектов и переходить по очереди, то будет наглядно видно. сначала съест 1 куст, потом 3,5,7,4,2, ну и шестой остается, он его не съедает просто.

[N]

gridex, Теперь вроде ясно...задача не в том, что будет последним оставшимся...а в том, что будет съедено последним...

[N]

В любом случае, логика правильная)

Answer 2

[Wataru]

Это известная задача иосифа. По ссылке есть всякие решения. Вам подойдет самое тупое и медленное. У вас в задаче k прибито гвоздями к 2.

Понять те формулы можно примерно так. Съели мы первый куст, перешли ко второму. Теперь перенумеруем их, что останется? Та же самая задача, только с n-1 кустом. Только все кусты сдвинуты на k позиций и один номера у них на один уменьшены. Т.е. можно взять тот самый куст который при n-1 останется и найти, какой у него был номер до сдвига.

Answer 3

[cicatrix]

Обновил - написал вроде бы работающий код решения в комментариях (С#).

Comments

[Rsa97]

"Съеденные" кусты не должны считаться при следующем проходе по массиву. Попробуйте свой алгоритм для 7 кустов.

[BigSmoke]

По этому алгоритму с изначальным количеством кустов 7шт ответ получится 6. А автор говорит, что ответ должен быть 2

[N]

BigSmoke, Кстати...я в своём ответе только для 5 проверил...при 7 у меня тоже вроде как 6 получается...

[Rsa97]

cicatrix, Когда вы съели куст 7, куста 1 уже нету и "через один" - это пройти через куст 2 и съесть куст 4. Затем через 6 и съесть 2. Остаётся куст 6, который съесть невозможно.

[cicatrix]

Rsa97, Rsa97, N, gridex
Вот, вроде работает:

static int Solve(int bush_count)
        {
            int remaining = bush_count-1; // сколько ещё несъеденных
            int[] state = new int[bush_count]; // 1 - есть куст, 0 - нет.
            // Инициализация, первый съеден
            for (int i = 1 ; i < bush_count ; ++i)
            {
                state[i] = 1;
            }
            int lastIndex = 0; // индекс последнего съеденного куста
            while (remaining > 1)
            {
                // ищем следующий несъеденный 2 раза
                int turns = 0;
                while (turns < 2)
                {
                    do
                    {
                        lastIndex = (lastIndex + 1) % bush_count;
                    } while (state[lastIndex] == 0);
                    turns++;
                }                
                // едим
                state[lastIndex] = 0;
                remaining--;
            }
            return lastIndex + 1;
        }

[N]

cicatrix, Автору сам ход мыслей нужен был))
Мы даже не знаем на каком языке программирования он задачу решает...
Так-то красава, что замарочился))

Answer 4

[Rsa97]

Исходя из примеров получается, что когда остаётся последний куст, то его съесть невозможно.
Самый простой вариант - организовать массив и N-1 раз циклически продвигаться по нему, отмечая "съеденные" элементы.

Answer 5

[Adamos]

Очевидно, из цифр от 1 до N сразу логично выкинуть нечетные.
Следующим проходом из списка оставшихся будут выкидываться нечетные, если N четное, иначе четные.
И так каждую итерацию (вместо N будет длина предыдущего списка), пока длина списка оставшихся не будет равна 1.
Но гонять в памяти списки - это скучно, конечно. Лучше попробовать вывести формулу того, что выкидывается на каждом этапе. Глядишь, последнюю цифру удастся просто вычислить.