Ai là tù trưởng

Kỹ năng luyện tập trong bài: đệ quy, lập trình từ trên xuống, sử dụng con trỏ liên kết

Bộ lạc Ai-ui-gui ở vùng Hu-đu-nâu cách đây 8 thế kỉ chọn tù trưởng theo cách như sau: sau khi tù trưởng qua đời, toàn bộ đàn ông trưởng thành trong bộ lạc đứng thành vòng tròn thực hiện nghi lễ chọn tù trưởng mới. Nếu coi vị trí của người đầu tiên là số 1, có tất cả n người, ta gọi n-1 vị trí tiếp theo theo chiều kim đồng hồ là 2, 3, ..., n. Nghi lễ như sau:

người đầu tiên đếm 1,

người đứng kề bên trái người đầu tiên đếm 2,

người tiếp theo bên trái đếm 3, người này ra khỏi vị trí, nhảy lò cò một vòng rồi ra ngoài - coi như đã bị loại ra khỏi vòng.

người tiếp theo bên trái đếm 1,

người tiếp theo bên trái đếm 2,

người tiếp theo bên trái đếm 3, người này ra khỏi vị trí, nhảy lò cò một vòng rồi ra ngoài - coi như đã bị loại.

...cứ tiếp tục như vậy cho đến khi chỉ còn một người trong vòng tròn. Người đó sẽ trở thành tù trưởng mới.

Hãy viết chương trình ChiefFinder.java giả lập nghi lễ này để tính xem, nếu ông Trời muốn chọn ai làm tù trưởng thì sẽ phải xui người đó đến đứng tại vị trí nào trong n vị trí 1, 2,.., n ban đầu. Input là giá trị n nhập từ bàn phím. Output in ra màn hình. Ngoài ra, nếu muốn, bạn có thể in ra màn hình từng giai đoạn của nghi lễ để dễ kiểm tra bằng mắt xem chương trình chạy như thế nào. (nếu bạn đã biết cách sử dụng GUI thì càng hay)

Gợi ý:

Về cấu trúc dữ liệu: Hãy viết lớp Candidate (ứng cử viên), mỗi đối tượng Candidate có chứa các thuộc tính (field):

index: số hiệu vị trí ban đầu của mình,
left: tham chiếu tới ứng cử viên hiện đang đứng bên trái mình,
right: tham chiếu tới ứng cử viên hiện đang đứng bên phải mình;

và các phương thức:

out() thực hiện việc người đó ra khỏi vòng và kết nối lại vòng tròn giữa người đứng bên phải và người đứng bên trái mình (điều chỉnh các thuộc tính left, right).
count() thực hiện việc người đó đếm. Hàm này trả về giá trị gì hay nhận tham số gì là tùy bạn quyết định.

Về giải thuật: Bạn có thể dùng vòng lặp trên một cấu trúc danh sách để gọi các hàm out() và count() cho các candidate, nhưng cài thuật toán này khá phức tạp. Có một phương án đơn giản hơn nhiều, đó là dùng count() và out() gọi nhau theo đúng mô tả nghi lễ, không cần dùng đến vòng lặp với array hay list. Cấu trúc Candidate như trên hỗ trợ rất tốt phương án này. Bạn có thể thử cả hai phương án hoặc chọn một trong hai.

Cho trước nội dung file ChiefFinder như dưới đây. Các bạn tùy ý sửa đổi.

package chieffinder;

import java.util.Scanner;

public class ChiefFinder {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n;
        System.out.print("Number of candidates: ");
        n = input.nextInt();

		
        System.out.print("New chief should be at position " + n);
    }
}