Rút gọn cường độ (strength reduction) là kỹ thuật thay một phép toán "đắt" bên trong vòng lặp (như phép nhân) bằng một phép toán "rẻ" hơn (phép cộng), tận dụng tính chất biến chạy tăng đều. Xét vòng lặp nguồn:
i = a0
for k = 0..n-1:
t = i * c
<dùng t>
i = i + d
Sau khi rút gọn cường độ, trình biên dịch sinh mã tương đương nhưng chỉ thực hiện phép nhân đúng hai lần, ở ngoài vòng lặp:
t = a0 * c
step = d * c
for k = 0..n-1:
<dùng t>
t = t + step
Cho bốn số nguyên a0,c,d,n (n có thể bằng 0, 0≤n≤105, các số khác có thể âm), hãy mô phỏng đúng đoạn mã đã rút gọn cường độ ở trên: khởi tạo t = a0*c, step = d*c; sau đó với mỗi k=0,…,n−1 ghi lại giá trị hiện tại của t (là giá trị "được dùng" ở vòng lặp thứ k), rồi cập nhật t = t + step.
Ví dụ: a0=1,c=2,d=3,n=4: t=1*2=2, step=3*2=6; các giá trị dùng ở 4 vòng lặp lần lượt là 2,8,14,20 (đúng bằng (a0+kd)⋅c với k=0,1,2,3).
Một dòng duy nhất gồm 4 số nguyên a0 c d n, cách nhau bởi khoảng trắng.
In ra 2 dòng:
t được dùng ở mỗi vòng lặp k=0,…,n−1 theo đúng thứ tự, cách nhau bởi một dấu cách (nếu n=0 thì đây là một dòng trống).a0*c và d*c cách nhau một dấu cách — chính là hai phép nhân duy nhất được thực hiện sau khi rút gọn cường độ.Ví dụ:
Đầu vào:
1 2 3 0
Đầu ra:
2 6
Đầu vào:
1 2 3 4
Đầu ra:
2 8 14 20
2 6
Đang tải editor...