Bài toán xoá số trên vòng tròn

[Nobita004 (Kirito-kun)]

Cho em hỏi tên bài toán nổi tiếng này nhưng em quên rồi:

• Cho n số từ 1 đến n đuợc viết liên tiếp thành hình tròn. Ban đầu xoá số 1, sau đó bỏ qua k số và tiếp tục xoá. Xoá như vậy cho đến khi còn lại 1 số. Và số đó là số nào?
  Ví dụ: n=9 k=2 chẳng hạn. Ta có có số lần luợt bị xoá là: 1,4,7, 2, 6, 3, 9, 5. Và số còn lại là số 8.

Thanks!

[hungaya (Hung)]

The Josephus problem

Với k = 2 thì có công thức tổng quát, trong đó m ≥ 0, 0 ≤ p < 2^m:

• T(2^m + p) = 2p + 1

[thanhtrung2314 (Trung Nguyen)]

Mình không rành lắm giải thuật, mà bài này dùng queue rồi cứ xóa tới khi nào length = 1 thì xong

[rogp10]

Bẻ thẳng vòng tròn và tìm quy luật thôi

[tntxtnt]

C++17 ~6 dòng O(k logn) :V :V :V

int josephus(const int N, const int k)
{
    using namespace std;
    vector<pair<int, int>> pivots{{1, 1}};
    for (int n = 1, W = 1, m, r; n <= N; pivots.emplace_back(n, W))
        m = (n - W) / (k - 1) + 1, n += m, r = (W + k * m) % n, W = r ? r : n;
    auto [n, W] = *--upper_bound(begin(pivots), end(pivots), N,
                                 [](int n, auto& p) { return n < p.first; });
    return n == N ? W : W + k * (N - n);
}

edit: code ngắn hơn :V

edit: code ngắn hơn nữa, 4 dòng :V

int josephus(int N, int k)
{
    int n = 1, W = 1;
    for (int d, r; n + (d = (n - W) / (k - 1) + 1) < N)
        n += d, r = (W + k * d) % n ? W = r ? r : n;
    return n == N ? W : W + k * (N - n);
}

giải thích quá dài dòng nên để bạn đọc tự tìm hiểu :V

[rogp10]

Code này lấy được cả N người à

[tntxtnt]

lấy được cả N người là sao :V Cái này tính gộp, nếu giữ nguyên k tìm n với nhiều giá trị khác nhau thì có thể tách cái pivots ra và cái dòng tìm index ra nữa thì sẽ tính được với tất cả n = 1…N luôn trong O(N logk + N loglogN) thay vì O(N k logN) :V

std::vector<std::pair<int, int>> josephusPivots(const int N, const int k)
{
    std::vector<std::pair<int, int>> pivots{{1, 1}};
    for (int n = 1, W = 1, m, r; n <= N; pivots.emplace_back(n, W))
        m = (n - W) / (k - 1) + 1, n += m, r = (W + k * m) % n, W = r ? r : n;
    return pivots;
}

int josephusIndex(const int N, const int k,
                  const std::vector<std::pair<int, int>>& pivots)
{
    using namespace std;
    auto [n, W] = *--upper_bound(begin(pivots), end(pivots), N,
                                 [](int n, auto& p) { return n < p.first; });
    return n == N ? W : W + k * (N - n);
}

//
auto pivots_k4_N1000 = josephusPivots(1000, 4); //O(k logN), k = 4, N = 1000
std::cout << josephusIndex(123, 4, pivots_k4_N1000) << "\n"; //O(logk + loglogN), k = 4, N = 1000
std::cout << josephusIndex(234, 4, pivots_k4_N1000) << "\n";
std::cout << josephusIndex(345, 4, pivots_k4_N1000) << "\n";
//v.v...
//std::cout << josephusIndex(1234, 4, pivots_k4_N1000) << "\n"; //lỗi vì 1234 > 1000