удаление каждого К-того элемента из arraylist по кругу

#java #алгоритм

наша задача - для заданного числа человек N и заданного шага K - определить номер
счастливчика который останется последним в этой жеребьёвке. Например если всего 10
человек и выбывает каждый 3-й:

N = 10, K = 3
последовательность "вылета" будет такой (в скобках указаны выбывающие номера):


  1-й круг: 1 2 (3) 4 5 (6) 7 8 (9) 10
  
  2-й круг:                            1 (2) 4 5 (7) 8 10
  
  3-й круг:                                                (1) 4 5 (8) 10
  
  4-й круг:                                                               4 (5) 10
  
  5-й круг:                                                                        4 (10)


итак победителем оказался тот кто стоял четвертым в начальной позиции.

Входные данные содержат количество человек N и размер шага K.
Ответ должен содержать "выигрышный номер" (считая с 1).

Имеется вопрос насчёт того, как после окончания первого круга во втором круге начать
удаление не со второго элемента, а с первого уже

package com.company;

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList  list1 = new ArrayList();
        int n = 88;
        int sh = 6;
        for (int i = 0; i

Ответы
Ответ 1

Это двухтысячелетняя задача Иосифа Флавия в современной формулировке: идём ко кругу,
убиваем каждого K-ого, последний выживает. Вопрос на какую позицию в круге от начала
отсчёта встать, чтобы выжить, если всего N людей.

Линейное решение — O(n)

Есть простой линейный (O(n))алгоритм на основе рекуррентного соотношения:

g(1, k) = 0
g(n, k) = (g(n-1, k) + k) % n


где g(n, k) это индекс безопасного места в массиве (0 <= g(n, k) < n). Для примера
в вопросе (отсчёт от единицы):

public class Josephus {
  public static void main(String[] argv) {
      System.out.println(safe_position(10, 3));
  }
  public static int safe_position(int n, int k) {
      int g = 0;
      for (int i = 0; i < n; ++i)
          g = (g + k) % (i + 1);
      return g + 1;
  }
}


Реализация транслирована на Java из решения на Питоне. 

O(k log n)

Для маленьких k и больших n можно использовать O(k log n) решение:

public class JosephusLog {
    public static void main(String[] argv) {
        System.out.println(safe_position_log(2147483647, 3));
    }
    public static int safe_position_log(int n, int k) {
        double x = k * (double) n;
        while(x > n) {
            x = (long)((k * (x - n) - 1) / (k - 1));
        }
        return (int)x;
    }
}


Замкнутая формула — O(1)

Могут существовать и замкнутые формулы (O(1) решение для n,k размером с машинное
слово). К примеру, для k=2 (достаточно старший бит в конец записать). Вот реализация
на Java O(1) решения для k=3 (за постоянное время, не зависящее от n), из статьи The
Josephus Problem by Lorenz Halbeisen:

public class Josephus3 {
    public static void main(String[] argv) {
        System.out.println(safe_position3(10));
    }
    public static int safe_position3(int n) {
        // j(n, k, n-l) = (n - c_m) * k + d_m;
        // return j(n, 3, n) + 1;
        switch(n) {
        case 1:
        case 4:
            return 1;
        case 2:
        case 3:
            return 2;
        default:
            assert(n >= 5);
            int k = 3;
            double alpha = 0.8111352513650005; // theorem 2 [jos] k = 3; l = 0;
            double q = k / (double)(k-1);
            long m = Math.round(Math.log(n / alpha) / Math.log(q)); // n >= 5
            double e_m = alpha * Math.pow(q, m);
            long c_m = Math.round(e_m);
            if (c_m > n) {
                m -= 1;
                e_m /= q;
                c_m = Math.round(e_m);
            }
            assert(c_m <= n);  // c_m <= n < c_m_plus_1
            int d_m = (e_m - c_m) < 0 ? 1 : 0;
            return (int)((n - c_m) * k + d_m + 1);
        }
    }
}


Решение работает для всех int n от 1 до 2147483647.


Ответ 2

package com.company;
import java.util.ArrayList;

public class MyClass {
    public static void main(String[] args) {
        ArrayList  list1 = new ArrayList();
        int n = 10;
        int k = 3;
        for (int i = 0; i