Trong hướng dẫn này, ta sẽ viết chương trình tính thời gian cần thiết để tín hiệu lan truyền đến tất cả vị trí trong một chuỗi. Hãy giải thích qua ví dụ.
Ta có chuỗi chỉ chứa ký tự s và p. s là tín hiệu và p là vị trí. Tín hiệu bắt đầu tại s và lan truyền hai hướng trái và phải. Giả định cần 1 đơn vị thời gian để di chuyển sang vị trí liền kề. Nhiệm vụ: tính thời gian để chuyển tất cả vị trí thành tín hiệu.
Hãy xem một số ví dụ.
Đầu vào − pppppspss
Đầu ra − 5
Đầu vào − pspspsps
Đầu ra − 1
Đầu vào − ssssss
Đầu ra − 0
Hãy xem các bước giải quyết.
- Khởi tạo chuỗi và time = 0.
- Duyệt chuỗi.
- Đếm số p liên tiếp, lưu vào biến.
- Nếu ký tự hiện tại là s và số p > time trước, kiểm tra xem có s ở bên trái không.
- Nếu có s cả hai bên, chia số p làm đôi vì tín hiệu lan hai hướng.
- Đặt lại đếm p.
Ví dụ
Xem mã dưới đây:
#include <bits/stdc++.h> using namespace std; int timeToConvertToSignalString(string sample_string, int string_len) { int p_count = 0, time = 0; for (int i = 0; i <= string_len; i++) { if (sample_string[i] == 'p') { p_count++; } else { if (p_count > time) { bool is_present_left_side = false; if (((i - p_count) > 0) && (sample_string[i - p_count - 1] == 's')) { is_present_left_side = 1; } if (is_present_left_side) { p_count = ceil((double)p_count / 2); } time = max(time, p_count); } p_count = 0; } } return time; } int main() { string sample_string = "pppppspss"; int n = sample_string.size(); cout << timeToConvertToSignalString(sample_string, n) << endl; return 0; }
Đầu ra
Nếu thực thi chương trình trên, bạn sẽ nhận được kết quả sau:
5
Hãy thử chạy chương trình với các trường hợp khác để kiểm tra.
Kết luận
Nếu bạn có thắc mắc, hãy đề cập trong phần bình luận.