Bài toán mảng tích (không gian O(1)) trong C++?

Chúng ta sẽ xem bài toán mảng tích với ràng buộc không dùng phép chia và phải giải tại chỗ (in-place) mà không dùng không gian bổ sung.

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.

Ở đây ta giải bằng cách dùng một biến temp, tìm tích phần bên trái và bên phải. Giá trị này sẽ được đặt vào mảng kết quả. Vì vậy không tốn không gian thêm.

Thuật toán

productArray(arr, n)

bắt đầu
  định nghĩa mảng res kích thước n
  điền mảng res bằng 1
  temp := 1
  for i trong khoảng 1 đến n, thực hiện
    res[i] := temp;
    temp := temp * arr[i]
  done
  for i trong khoảng n-1 giảm xuống 0, thực hiện
    res[i] = res[i] * temp
    temp := temp * arr[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) {
  int temp = 1;
  for(int i = 0; i < n; i++) {
    product[i] = 1; // đặt tất cả phần tử của product là 1
  }
  for(int i = 0; i < n; i++) { // temp giữ tích phần tử bên trái trừ arr[i]
    product[i] = temp;
    temp *= arr[i];
  }
  temp = 1;
  for(int i = n - 1; i >= 0; i--) { // temp giữ tích phần tử bên phải trừ arr[i]
    product[i] *= temp;
    temp *= arr[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