Đề bài
Một chuỗi Markov chuyển ngẫu nhiên giữa các trạng thái, và trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại. transition[i][j] là xác suất chuyển từ trạng thái i sang trạng thái j, nên mỗi hàng có tổng bằng 1.
Nếu p là xác suất đang ở mỗi trạng thái lúc này, phân phối sau một bước là:
p_next[j] = Σ theo i của p[i] × transition[i][j]
Hãy viết markov_distribution(transition, start, steps) và áp dụng phép cập nhật này steps lần.
Đầu vào
transition: Ma trận n × n có tổng mỗi hàng bằng 1.
start: Phân phối ban đầu (n giá trị có tổng bằng 1).
steps: Số bước cần đi.
Đầu ra
Trả về phân phối sau steps bước.
Ràng buộc
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000
0 ≤ mỗi xác suất ≤ 1
Ví dụ
Đầu vào:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Kết quả mong đợi:
expected = [0.86, 0.14]Đầu vào:
std::vector<double> start = {1.0, 0.0};
long long steps = 2;
std::vector<std::vector<double>> transition = {
{0.9, 0.1},
{0.5, 0.5}
};
Kết quả mong đợi:
std::vector<double> expected = {0.86, 0.14};Đầu vào:
double[] start = new double[] {1.0, 0.0};
long steps = 2;
double[][] transition = new double[][] {
new double[] {0.9, 0.1},
new double[] {0.5, 0.5}
};
Kết quả mong đợi:
double[] expected = new double[] {0.86, 0.14};Giải thích
Hãy hình dung ngày nắng (0) và ngày mưa (1), bắt đầu từ ngày nắng. Sau một bước: [0.9, 0.1]. Sau hai bước: nắng = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 và mưa = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Đầu vào:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Kết quả mong đợi:
expected = [0.75, 0.25]Đầu vào:
std::vector<double> start = {0.25, 0.75};
long long steps = 3;
std::vector<std::vector<double>> transition = {
{0.0, 1.0},
{1.0, 0.0}
};
Kết quả mong đợi:
std::vector<double> expected = {0.75, 0.25};Đầu vào:
double[] start = new double[] {0.25, 0.75};
long steps = 3;
double[][] transition = new double[][] {
new double[] {0.0, 1.0},
new double[] {1.0, 0.0}
};
Kết quả mong đợi:
double[] expected = new double[] {0.75, 0.25};Giải thích
Chuỗi này luôn đổi trạng thái, nên mỗi bước hoán đổi hai xác suất. Sau 3 lần hoán đổi: [0.75, 0.25].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Phân phối kế tiếp được tính bằng cách đẩy khối xác suất qua mọi chuyển trạng thái từ phân phối hiện tại.
Gợi ý 2
Hãy xem như phép nhân ma trận-vector lặp lại, từng bước một.
Gợi ý 3
Khi steps bằng 0, hãy trả về phân phối ban đầu không đổi.
Độ phức tạp mong đợi
thời gian O(steps * n^2), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.