Bài toán mảng tích trong C++?

Chúng ta sẽ xem một bài toán thú vị liên quan đến mảng. Có một mảng n phần tử. Cần tạo mảng khác n phần tử, trong đó vị trí thứ i của mảng thứ hai chứa tích tất cả phần tử của mảng thứ nhất trừ phần tử thứ i. Ràng buộc: không được sử dụng phép chia.

Nếu cho phép chia, ta dễ dàng giải bằng cách tính tích tất cả phần tử, sau đó chia cho phần tử thứ i của mảng đầu tiên và lưu vào vị trí i của mảng thứ hai.

Ở đây ta giải bằng cách tạo hai mảng riêng biệt: left và right. left[i] chứa tích tất cả phần tử bên trái của arr[i] trừ arr[i], right[i] chứa tích tất cả phần tử bên phải của arr[i] trừ arr[i]. Giải pháp này tốn O(n) thời gian nhưng cần không gian bổ sung.

Thuật toán

productArray(arr, n)

bắt đầu
  định nghĩa hai mảng left và right kích thước n
  định nghĩa mảng res kích thước n
  phần tử đầu tiên của left và phần tử cuối của right đặt là 1
  for i trong khoảng 1 đến n, thực hiện
    left[i] = left[i-1] * arr[i-1]
  done
  for i trong khoảng n-1 giảm xuống 1, thực hiện
    right[i] = right[i+1] * arr[i+1]
  done
  for i trong khoảng 1 đến n, thực hiện
    res[i] = left[i] * right[i];
  done
  trả về res
kết thúc

Ví dụ

#include <iostream>
using namespace std;

void printArray(int arr[], int n) {
  for(int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void productArray(int arr[], int product[], int n) {
  // tạo mảng left right
  int *left = new int[sizeof(int)*n];
  int *right = new int[sizeof(int)*n];
  // đặt phần tử đầu tiên của left[] và cuối của right[] là 1
  left[0] = right[n-1] = 1;
  for(int i = 1; i < n; i++) {
    left[i] = left[i-1] * arr[i-1];
  }
  for(int i = n-2; i >= 0; i--) {
    right[i] = right[i+1] * arr[i+1];
  }
  // lấy mảng tích dùng left và right
  for(int i = 0; i < n; i++) {
    product[i] = left[i] * right[i];
  }
}

int main() {
  int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
  int resArr[7];
  cout << "Initial Array: ";
  printArray(myArr, 7);
  productArray(myArr, resArr, 7);
  cout << "Final Array: ";
  printArray(resArr, 7);
  return 0;
}

Kết quả

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120