Câu đố về mảng sản phẩm trong C ++?

Ở đây chúng ta sẽ thấy một vấn đề thú vị liên quan đến mảng. Có một mảng với n phần tử. Chúng ta phải tạo một mảng khác gồm n phần tử. Nhưng vị trí thứ i của mảng thứ hai sẽ chứa tích của tất cả các phần tử của mảng đầu tiên ngoại trừ phần tử thứ i. Và một hạn chế là chúng ta không thể sử dụng toán tử chia trong bài toán này.

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

Ở đây chúng tôi đang giải quyết vấn đề này bằng cách tạo hai mảng riêng biệt. bên trái và bên phải. [i] bên trái sẽ chứa tích của tất cả các phần tử ở bên trái của mảng [i] không bao gồm mảng [i] và bên phải [i] sẽ chứa tích của tất cả các phần tử ở bên phải của arr [i] ngoại trừ arr [i]. Giải pháp này sẽ mất O (n) thời gian. Nhưng nó sẽ tốn thêm dung lượng.

Thuật toán

productArray (arr, n)

begin
   define two arrays left and right of size n
   define an array called res of size n
   the first element of left and last element of right is set as 1
   for i in range 1 to n, do
      left[i] = left[i-1] * arr[i-1]
   done
   for i in range n-1 down to 1, do
      right[i] = right[i+1] * arr[i+1]
   done
   for i in range 1 to n, do
      res[i] = left[i] * right[i];
   done
   return res
end

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) {
   //create left right array
   int *left = new int[sizeof(int)*n];
   int *right = new int[sizeof(int)*n];
   //set the first element of left[] and last element of right[] as 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];
   }
   //get product array using left and right array
   for(int i = 0; i<n; i++) {
      product[i] = left[i] * right[i];
   }
}
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);
}

Đầu ra

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