Giả sử n hành khách lên máy bay có đúng n ghế. Nếu hành khách đầu tiên mất vé và chọn ngẫu nhiên một ghế. Sau đó, các hành khách còn lại sẽ tuân theo các quy tắc:
Ngồi vào ghế của mình trên vé nếu ghế đó vẫn trống.
Chọn ngẫu nhiên ghế khác khi thấy ghế của mình bị chiếm.
Chúng ta phải tìm xác suất rằng người thứ n có được ngồi ở ghế của mình? Nếu đầu vào là 2, đầu ra sẽ là 0.5. Người thứ hai có xác suất 0.5 để ngồi vào ghế thứ hai (khi người đầu tiên ngồi vào ghế thứ nhất).
Để giải quyết, chúng ta làm theo các bước:
Nếu n là 1, trả về 1, ngược lại trả về 0.5.
Ví dụ (C++)
Hãy xem triển khai sau để hiểu rõ hơn:
class Solution {
public:
double nthPersonGetsNthSeat(int n) {
if (n == 1) return 1;
return 0.5;
}
};
Đầu vào
2
Đầu ra
0.50000