Tính tổng của một mảng số thực sử dụng kỹ thuật prefix sums trong ngôn ngữ lập trình C++

4

(205 votes)

Trong lập trình, việc tính tổng của một mảng số thực là một công việc phổ biến và quan trọng. Một trong những kỹ thuật phổ biến để tính tổng này là sử dụng kỹ thuật prefix sums. Trong bài viết này, chúng ta sẽ tìm hiểu về kỹ thuật này và cách áp dụng nó trong ngôn ngữ lập trình C++. Kỹ thuật prefix sums là một phương pháp tối ưu để tính tổng của một mảng số thực. Ý tưởng chính của kỹ thuật này là tính toán tổng các phần tử từ đầu mảng đến vị trí hiện tại và lưu trữ kết quả vào một mảng mới. Điều này giúp chúng ta truy vấn tổng của một đoạn con trong mảng ban đầu chỉ trong thời gian O(1), thay vì phải tính toán lại từng phần tử trong đoạn đó. Để áp dụng kỹ thuật prefix sums trong ngôn ngữ lập trình C++, chúng ta có thể sử dụng một mảng bổ sung để lưu trữ tổng các phần tử từ đầu mảng đến vị trí hiện tại. Đầu tiên, chúng ta khởi tạo mảng bổ sung này với giá trị 0. Sau đó, chúng ta duyệt qua từng phần tử trong mảng ban đầu và tính tổng các phần tử từ đầu mảng đến vị trí hiện tại, lưu trữ kết quả vào mảng bổ sung. Cuối cùng, chúng ta có thể truy vấn tổng của một đoạn con trong mảng ban đầu bằng cách lấy hiệu của hai giá trị trong mảng bổ sung. Dưới đây là một ví dụ minh họa về cách tính tổng của một mảng số thực sử dụng kỹ thuật prefix sums trong ngôn ngữ lập trình C++: ```cpp #include <iostream > using namespace std; int main() { int n; cout < < "Nhap so phan tu cua mang: "; cin > > n; double arr[n]; cout < < "Nhap cac phan tu cua mang: "; for (int i = 0; i < n; i++) { cin > > arr[i]; } double prefixSum[n]; prefixSum[0] = arr[0]; for (int i = 1; i < n; i++) { prefixSum[i] = prefixSum[i-1] + arr[i]; } int left, right; cout < < "Nhap vi tri bat dau va ket thuc cua doan con: "; cin > > left > > right; double sum = prefixSum[right] - prefixSum[left-1]; cout < < "Tong cua doan con tu vi tri " < < left < < " den " < < right < < " la: " < < sum < < endl; return 0; } ``` Trong ví dụ trên, chúng ta nhập số phần tử của mảng và các phần tử của mảng từ người dùng. Sau đó, chúng ta tính tổng của mảng sử dụng kỹ thuật prefix sums và truy vấn tổng của một đoạn con trong mảng ban đầu. Kỹ thuật prefix sums là một công cụ hữu ích trong việc tính tổng của một mảng số thực trong ngôn ngữ lập trình C++. Nó giúp chúng ta tối ưu hóa thời gian tính toán và cung cấp một cách tiếp cận hiệu quả để truy vấn tổng của các đoạn con trong mảng.