solution

Một chương trình có $L$ vòng lặp độc lập (không lồng nhau). Vòng lặp thứ $k$ chạy đúng $N_k$ lần lặp, đánh số $j = 0, 1, \ldots, N_k-1$; biến chỉ số vòng lặp $i$ được khởi tạo $i = i0_k$ trước vòng lặp và tăng thêm $step_k$ mỗi lần lặp, tức tại lần lặp thứ $j$ ta có $i = i0_k + j \cdot step_k$. Trong vòng lặp có $V_k$ biến dẫn xuất (induction variable phụ) $u_1, \ldots, u_{V_k}$; theo cách tính CHƯA tối ưu, mỗi lần lặp biến $u_t$ được tính lại từ đầu bằng một phép NHÂN: $u_t = c_t \cdot i + d_t$ ($c_t, d_t$ cho trước).

Phép biến đổi giảm cường độ toán tử (strength reduction) thay việc tính lại $u_t$ bằng nhân, bởi: chỉ tính MỘT LẦN giá trị khởi tạo $u_t^{(0)} = c_t \cdot i0_k + d_t$ và lượng gia tăng cố định $c_t \cdot step_k$ trước khi vào vòng lặp (các phép nhân này KHÔNG tính là phép nhân "bên trong" vòng lặp), sau đó mỗi lần lặp $j \ge 1$ chỉ cần một phép CỘNG: $u_t^{(j)} = u_t^{(j-1)} + c_t \cdot step_k$.

Với mỗi vòng lặp $k$, hãy tính:

(a) Tổng số phép NHÂN thực hiện bên trong vòng lặp theo cách CHƯA tối ưu: $N_k \times V_k$.

(b) Tổng số phép NHÂN thực hiện bên trong vòng lặp SAU KHI giảm cường độ toán tử: luôn bằng $0$.

(c) Giá trị của tất cả các biến dẫn xuất $u_1, \ldots, u_{V_k}$ ở LẦN LẶP CUỐI CÙNG ($j = N_k - 1$); nếu $N_k = 0$ (vòng lặp không chạy lần nào) thì không có giá trị nào, in NONE.

Cuối cùng, in tổng số phép nhân tiết kiệm được trên TOÀN CHƯƠNG TRÌNH (tổng của (a) trừ tổng của (b) qua mọi vòng lặp — vì (b) luôn 0 nên bằng tổng của (a)).

Lưu ý: dù $N_k = 0$, các biểu thức khởi tạo $u_t^{(0)}$ và lượng gia tăng $c_t \cdot step_k$ vẫn được tính (đây là chi phí NGOÀI vòng lặp, không tính trong (a) hay (b)).