Trả lời: Kiran Kumar – Người viết Code.
Đêm qua khi tôi đang xem bộ phim Nannaku Prematho (một bộ phim Ấn Độ).
Đó là vào phút thứ 56.23, tôi thật sự bị rối bởi câu hỏi từ nhân vật phản diện. Câu hỏi như thế này: Có 100 người đứng thành vòng tròn từ 1 đến 100. Người số 1 cầm một thanh kiếm. Anh ta giết người kế anh ta (số 2) và đưa thanh kiếm cho người tiếp theo (số 3). Tất cả mọi người đều làm như thế cho đến khi chỉ còn một người sống sót. Ai sẽ là người sống cuối cùng?
Tôi dừng bộ phim lại và ngay lập tức mở trình soạn thảo văn bản và bắt đầu viết một chương trình cho câu hỏi đó.
Ban đầu tôi nghĩ sử dụng cấu trúc dữ liệu Danh sách liên kết vòng (Circular Linked List) để giải quyết câu hỏi và tôi đã viết đoạn code sử dụng cấu trúc dữ liệu. (ảnh 1)
Bài toán được giải quyết. Vị trí số 73 là đáp án chính xác. (ảnh 2)
Nhưng sau đó, tôi nhận ra mình còn có thể sử dụng hàm Đệ quy* (ảnh 3).
(*) Giải thích về Đệ quy: http://pymi.vn/blog/print-recursively/
Sau khi giải quyết rất nhiều bài toán, tôi nghĩ não của mình đã tự tạo thói quen hình dung mọi bài toán bằng cách lập trình luôn rồi.
Mà lập trình thật sự thú vị đấy, hoan hô nào!!!!!!!
Ps: À,bộ phim cũng thật sự rất tuyệt vời đó.
—-
Bình luận:
– Yash Kothari: Câu hỏi này được gọi là Bài toán Josephus. Ta biểu diễn n = 2^a + l thì người sống sót cuối cùng ở vị trí là 2l +1. Trong trường hợp này n=100 thì a = 6, l=36.
-> Harshit Jaiswal:
Đúng rồi anh bạn ơi. Nó chính là Bài toán Joesphus. Nhưng chúng ta cũng có thể giải nó theo cách khác đấy.
Chúng ta có thể biển diễn mà không cần có đủ số con người (ở đây là 100) mà bằng cách nhị phân, chúng sẽ có dạng thế này 100=1100100. Rồi áp dụng MSB (Bit có giá trị cao nhất, là bit nằm tận cùng phía bên tay trái) và lấy bit đó đặt vào giống như này 1001001(**). Bây giờ thì chúng ta sẽ chuyển sang hệ thập phân từ dãy số nhị phân được chuyển đổi sẽ có được đáp án vị trí của người sống sót cuối cùng: 1001001=73.
(**) Lấy số ngoài cùng ở dãy số nhị phân ở trên, thêm nó vào cuối của đoạn nhị phân đó: 1100100 => 1001001.
Học hành hạnh phúc đê!!!
–>> Bihan Sen:
Cách giải quyết bạn đưa ra không có gì khác câu trả của Yash Kothari cả.
Khi bạn di chuyển bit có giá trị cao nhất từ phép biễu diễn nhị phân, chỉ là bạn đang cắt phần 2^a, đó là giá trị cao nhất của lũy thừa 2, nó bé hơn hoặc bằng n.
Bây giờ phần còn lại bạn nhận được chẳng có gì khác ngoài l trong câu trả lời của anh ấy.
Khi bạn thêm 1 vào cuối đoạn nhị phân nó giống như bạn đang dời số 1 về phía bên trái (của phép nhân 2) sau đó thêm dấu cộng vào để trở thành 2l + 1.
–>> Harshit Jaiswal
Ohh….tôi biết chứ. Nó chỉ là một cách khác tương ứng với 2l +1 thôi.
–>>Arjun Radhakrishnan
Tui chỉ ở đây để giới thiệu với mấy bồ video cho bạn nào không thể hiểu được chuyện quái gì đang xảy ra.
Link video:
– Tiếng Anh: https://www.youtube.com/watch?t=1s&v=uCsD3ZGzMgE&app=desktop;
– Tiếng Việt: http://genk.vn/cau-do-toan-hoc-nay-lam-ban-dau-dau-nhung… (cái này mình thêm vào thôi).
Theo: Nhã Trân