Có n người đứng thành một vòng tròn, được đánh số thứ tự 1, 2, 3, 4,..., . Trò chơi bắt đầu

Trả lời Câu Fcs45 trang 65 SBT Tin học 11 sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

1 297 18/10/2023


Giải SBT Tin học 11 Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

Câu Fcs45 trang 65 SBT Tin học 11: Bài toán Josephus được phát biểu như sau:

Có n người đứng thành một vòng tròn, được đánh số thứ tự 1, 2, 3, 4,..., . Trò chơi bắt đầu từ người thứ nhất (đánh số 1). Mọi người sẽ lần lượt đếm 1 -2-1-2-1-2-... khi tới lượt của mình, bất kì ai sau khi đếm được số 2 thì phải bước ra khỏi vòng tròn. Trong toán học, người ta rút ra được một số công thức để tính ra được người còn sót lại cuối cùng trong vòng tròn, với luật chơi tổng quát (đểm tới k thay vì 2). Tuy nhiên, ở đây em lại quan tâm diễn biến của trò chơi này hơn. Em hãy dùng danh sách liên kết để mô phỏng lại trò chơi trên.

Dữ liệu: Dòng duy nhất chứa số nguyên n.

Dòng duy nhất chứa n số là số hiệu của những người chơi bị loại ra khỏi vòng tròn theo thứ tự.

Ví dụ:

Bài toán Josephus được phát biểu như sau Có n người đứng

Lời giải:

Hướng dẫn: Có thể áp dụng danh sách liên kết vòng để giải quyết bài toán trên. Thao tác xoá phần tử được vận dụng nhiều.

Chương trình mẫu:

Bài toán Josephus được phát biểu như sau Có n người đứng

1 297 18/10/2023


Xem thêm các chương trình khác: