Hướng dẫn giải của Josephus

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, vudinhlong, nqtrung123, Giai_tich_2

Hiểu bài toán

Bài toán Josephus biến thể gồm hai phần: a) Có n người (1 đến n) đứng vòng. Bắt đầu từ người 1, đếm liên tục 1, 2, ..., S. Người được đếm thứ S bị loại. Tiếp tục đếm từ người tiếp theo cho đến khi chỉ còn một người. Tìm số hiệu người cuối cùng. b) Biết người cuối cùng là K, tìm người bắt đầu đếm (số hiệu) để người K sống sót.

Input: Dòng 1: n, S. Dòng 2: K. Constraints: n ≤ 100, S ≤ 100.

Các cách tiếp cận

Cách Mô phỏng bằng mảng (Brute Force)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, S, K;
    cin >> n >> S >> K;

    // Cau A: Danh dau nguoi song sót
    vector<bool> alive(n + 1, true);
    int count = n;
    int pos = 1; // Bat dau tu nguoi 1

    while (count > 1) {
        // Di chuyen S-1 buoc den nguoi truoc nguoi bi xoa
        for (int i = 0; i < S - 1; i++) {
            do {
                pos = (pos % n) + 1;
            } while (!alive[pos]);
        }
        // Xoa nguoi thu S
        alive[pos] = false;
        count--;
        // Tim nguoi tiep theo de bat dau dem
        do {
            pos = (pos % n) + 1;
        } while (!alive[pos]);
    }

    int ansA = 0;
    for (int i = 1; i <= n; i++) {
        if (alive[i]) {
            ansA = i;
            break;
        }
    }
    cout << ansA << endl;

    // Cau B: Thu nguoc lai
    // Thu tu nguoi bat dau tu 1 den n, ai la nguoi cuoi cung
    for (int start = 1; start <= n; start++) {
        alive.assign(n + 1, true);
        count = n;
        pos = start;

        while (count > 1) {
            for (int i = 0; i < S - 1; i++) {
                do {
                    pos = (pos % n) + 1;
                } while (!alive[pos]);
            }
            alive[pos] = false;
            count--;
            do {
                pos = (pos % n) + 1;
            } while (!alive[pos]);
        }

        int last = 0;
        for (int i = 1; i <= n; i++) {
            if (alive[i]) {
                last = i;
                break;
            }
        }

        if (last == K) {
            cout << start << endl;
            break;
        }
    }
    return 0;
}

Time Complexity: O(n^2)
Space Complexity: O(n)

Sử dụng mảng đánh dấu để mô phỏng quá trình loại bỏ.

Câu A: Bắt đầu từ 1, lặp S-1 bước để tìm người bị loại, đánh dấu false, lặp lại đến khi còn 1 người.
Câu B: Thử tất cả các giá trị bắt đầu từ 1 đến n. Với mỗi giá trị, thực hiện mô phỏng như câu A và kiểm tra xem người cuối cùng có phải là K không. Phức tạp thời gian O(n^2) do n lần lặp cho câu B, mỗi lần O(n), phù hợp với n ≤ 100.

Cách Danh sách liên kết (Linked List)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createList(int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    Node* cur = head;
    for (int i = 2; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        cur->next = newNode;
        cur = newNode;
    }
    cur->next = head; // Vòng
    return head;
}

int solveJosephus(Node* head, int n, int s, int startOffset) {
    if (n == 1) return head->data;

    // Di chuyển con trỏ về người bắt đầu
    Node* cur = head;
    if (startOffset > 1) {
        for (int i = 1; i < startOffset; i++)
            cur = cur->next;
    }

    // Mô phỏng
    while (cur->next != cur) {
        // Đếm s-1 bước
        for (int i = 1; i < s; i++) {
            cur = cur->next;
        }
        // Xóa node tiếp theo
        Node* temp = cur->next;
        cur->next = temp->next;
        free(temp);
        // Di chuyển sang người tiếp theo để bắt đầu đếm lại
        cur = cur->next;
    }
    return cur->data;
}

int main() {
    int n, s, k;
    scanf("%d %d %d", &n, &s, &k);

    // Cau A
    Node* head = createList(n);
    int ansA = solveJosephus(head, n, s, 1);
    printf("%d\n", ansA);

    // Cau B
    int ansB = 0;
    for (int i = 1; i <= n; i++) {
        head = createList(n);
        int res = solveJosephus(head, n, s, i);
        if (res == k) {
            ansB = i;
            break;
        }
    }
    printf("%d\n", ansB);
    return 0;
}

Time Complexity: O(n^2)
Space Complexity: O(n)

Sử dụng danh sách liên kết đơn vòng để mô phỏng.

Tạo vòng liên kết chứa các số từ 1 đến n.
Khi loại bỏ, thay đổi con trỏ next của node hiện tại để bỏ qua node bị xóa.
Câu A: Thực hiện từ node đầu tiên.
Câu B: Tạo lại danh sách và thử bắt đầu từ các node khác nhau (1 đến n) cho đến khi tìm được. Cách này mô phỏng đúng bản chất bài toán nhưng code phức tạp hơn mảng.

Cách Quy hoạch động (Dynamic Programming - Josephus)

#include <iostream>
#include <vector>
using namespace std;

int josephus(int n, int k) {
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

int main() {
    int n, s, k;
    cin >> n >> s >> k;

    // Cau A: Index 0-based
    cout << josephus(n, s) + 1 << endl;

    // Cau B: Tim nguoi bat dau
    // Gia su nguoi bat dau la X (index 1-based).
    // Thuat toan Josephus chuan luon bat dau tu 0.
    // Neu doi nguoi bat dau tu 1 sang X, thu tu giam sat tuong ung cung bi dich chuyen.
    // De giai, ta co the dao nguoc qua trinh:
    // Khi bat dau tu 1, nguoi cuoi cung la A (index 0-based).
    // Khi bat dau tu X, nguoi cuoi cung se la (A + (X-1)) % n.
    // Ta can nguoi cuoi cung la K (index 0-based).
    // K = (A + (X-1)) % n
    // => (X-1) = (K - A + n) % n
    // => X = (K - A + n) % n + 1

    int A = josephus(n, s); // Nguoi cuoi cung khi bat dau tu 1 (0-based)
    int K_index = k - 1;    // Yeu cau nguoi cuoi la K (0-based)

    int X_index = (K_index - A + n) % n;
    int ansB = X_index + 1;

    cout << ansB << endl;

    return 0;
}

Time Complexity: O(n)
Space Complexity: O(n)

Sử dụng công thức quy hoạch động của Josephus: J(n, k) = (J(n-1, k) + k) % n.

Câu A: Tính trực tiếp kết quả.
Câu B: Biết kết quả khi bắt đầu từ 1 là A. Nếu bắt đầu từ X, người chết sẽ được dịch chuyển theo chu kỳ. Ta có thể tính X dựa trên A, K và n bằng công thức đảo ngược: X = ((K - 1 - A) + n) % n + 1. Đây là phương pháp tối ưu nhất về thời gian.

Phân tích độ phức tạp

Cách tiếp cận	Time	Space	Tên
1	O(n^2)	O(n)	Mô phỏng bằng mảng (Brute Force)
2	O(n^2)	O(n)	Danh sách liên kết (Linked List)
3	O(n)	O(n)	Quy hoạch động (Dynamic Programming - Josephus)

Bài học kinh nghiệm

N n nhỏ (≤100), mô phỏng trực tiếp là cách tiếp cận an toàn và dễ hiểu nhất.
Bài toán Josephus có công thức quy hoạch động hiệu quả để tính người sống sót.
Câu hỏi ngược (tìm người bắt đầu) có thể được suy luận từ công thức toán học của Josephus hoặc giải bằng brute force.

Lỗi thường gặp

Lỗi vòng lặp vô hạn trong mô phỏng nếu không cập nhật đúng vị trí.
Sai lệch chỉ số mảng (0-based vs 1-based).
Quên trường hợp đặc biệt n=1.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.