MathLabs

Bài 5

Có nn người ngồi thành vòng tròn. Tổng cộng có nknk đồng xu được phân phối, không nhất thiết đều. Một bước chuyển một đồng xu giữa hai người kề nhau. Hãy tìm thuật toán dùng ít bước nhất để cuối cùng mọi người có cùng số đồng xu.
Bước 5 trên 5: So sánh bước qua mép vòng và lặp lại
X→0X\to0
Phân tích chi tiết

Lặp bước làm giảm thế năng cho đến khi X=0X=0 nếu không có bước qua mép vòng tốt hơn. Đồng thời tính độ thay đổi của XX khi chuyển xu qua cạnh n,1n,1 theo cả hai hướng; nếu một hướng làm giảm hơn một đơn vị thì chọn hướng giảm nhiều hơn. Mỗi bước đều hợp lệ và làm XX giảm nghiêm ngặt, nên quá trình kết thúc khi mọi người có số xu bằng nhau và là tối ưu theo lập luận thế năng. XX