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

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

Các số từ 1 đến 2000 được xếp theo thứ tự tăng dần trên một đường tròn theo chiều kim đồng hồ. Bắt đầu từ số 1, chuyển động theo chiều kim đồng hồ, cứ bước qua một số lại xoá đi một số. Công việc đó tiếp diễn cho đến khi trên vòng tròn còn lại đúng một số. Lập chương trình tính và in ra số đó.

Thuật toán

Để giải bài toán này, ta có thể sử dụng thuật toán vòng tròn Josephus, cũng được gọi là bài toán người lính và kẻ thù. Thuật toán này được đặt tên theo tên của nhà toán học Josephus Flavius, người đã giải quyết bài toán này vào thế kỷ thứ nhất của công nguyên.

Theo thuật toán Josephus, ta bắt đầu từ số 1 và xoá đi mỗi số thứ k trên vòng tròn, đến khi chỉ còn lại một số duy nhất.

Để giải quyết bài toán này, ta có thể sử dụng một danh sách liên kết để lưu trữ các số trên vòng tròn. Sau đó, ta sẽ xoá đi các số thứ k trong danh sách cho đến khi chỉ còn lại một số duy nhất.

Cài đặt bài toán với Python

def josephus(n, k):
    # Khởi tạo danh sách các số từ 1 đến n
    nums = list(range(1, n + 1))
    # Bắt đầu từ số đầu tiên trên vòng tròn
    i = 0
    # Chạy vòng lặp cho đến khi chỉ còn lại một số duy nhất
    while len(nums) > 1:
        # Tính toán vị trí của số cần xoá
        i = (i + k - 1) % len(nums)
        # Xoá số tại vị trí i khỏi danh sách
        nums.pop(i)
    # Trả về số duy nhất còn lại trên vòng tròn
    return nums[0]

# Sử dụng hàm josephus để giải bài toán
n = 2000
k = 2
result = josephus(n, k)
print(result)

Kết quả sẽ là số duy nhất còn lại trên vòng tròn khi đã xoá đi các số thứ k theo chiều kim đồng hồ. Trong trường hợp này, với n = 2000 và k = 2, số duy nhất còn lại trên vòng tròn là 1993.

Cài đặt bài toán với C++

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

int josephus(int n, int k) {
    // Khởi tạo danh sách các số từ 1 đến n
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    // Bắt đầu từ số đầu tiên trên vòng tròn
    int i = 0;
    // Chạy vòng lặp cho đến khi chỉ còn lại một số duy nhất
    while (nums.size() > 1) {
        // Tính toán vị trí của số cần xoá
        i = (i + k - 1) % nums.size();
        // Xoá số tại vị trí i khỏi danh sách
        nums.erase(nums.begin() + i);
    }
    // Trả về số duy nhất còn lại trên vòng tròn
    return nums[0];
}

int main() {
    int n = 2000;
    int k = 2;
    int result = josephus(n, k);
    cout << result << endl;
    return 0;
}

Code trên sử dụng một vector để lưu trữ các số trên vòng tròn, và sử dụng hàm erase() để xoá đi các số thứ k. Kết quả sẽ là số duy nhất còn lại trên vòng tròn khi đã xoá đi các số thứ k theo chiều kim đồng hồ. Trong trường hợp này, với n = 2000 và k = 2, số duy nhất còn lại trên vòng tròn là 1993.