Алгоритм Иосифа
Я читал алгоритм для Проблема Иосифа.
Я наткнулся на следующий алгоритм:
int josephusIteration(int n,int k) {
int a=1;
for(int i=1;i<=n;i++) {
a=(a+k-1)%i+1;
}
return a;
}
Я не мог понять его логику. Предположим, что n = 5 и k = 2.
i=1, a=1
i=2, a=1
i=3, a=3
i=4, a=1
i=5, a=3
Кто-нибудь может объяснить это, приведя пример?
Решение
Если n = 5 а также k = 2тогда безопасная позиция 3, Сначала убивают человека в положении 2, затем убивают человека в положении 4, затем убивают человека в положении 1. Наконец, человек в позиции 5 убит. Таким образом, человек в положении 3 выживает.
Я прочитал ваш код, но я хотел бы предложить рекурсивное решение ниже, которое легче понять.
// this function returns the position of the person alive
int josephus(int n, int k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k) is adjusted because the
recursive call josephus(n - 1, k) considers the original position
k%n + 1 as position 1 */
return (josephus(n - 1, k) + k-1) % n + 1;
}
После того, как первый человек (kth от начала) убит, n-1 человек остаются. Итак, мы называем josephus(n – 1, k) чтобы получить должность с n-1 человек.
Но позиция вернулась josephus(n – 1, k) рассмотрим это снова с позиции 1. Итак, добавим k-1 к нему и взять его модуль с n как есть n элементы и добавить 1, чтобы сделать позицию 1-indexed скорее, чем 0-indexed,
Ссылка: http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/
Другие решения