Bài toán mảng tích (Product Array Puzzle) trong C

Mảng là chứa các phần tử cùng kiểu dữ liệu. Trong bài toán mảng tích, tìm tích tất cả phần tử.

Yêu cầu: tìm tích tất cả phần tử mảng trừ phần tử tại vị trí đó. Điều kiện: không dùng phép chia và lưu vào mảng khác.

Giải pháp: tạo hai mảng tích, một tích các phần tử bên trái, một tích các phần tử bên phải. Sau đó nhân hai mảng này để được kết quả.

Ví dụ

#include <stdio.h>
#include <stdlib.h>
void productfind(int arr[], int n) {
    int *left = (int*)malloc(sizeof(int) * n);
    int *right = (int*)malloc(sizeof(int) * n);
    int *prod = (int*)malloc(sizeof(int) * n);
    int i, j;
    left[0] = 1;
    right[n-1] = 1;
    for (i = 1; i < n; i++)
        left[i] = arr[i-1] * left[i-1];
    for (j = n-2; j >= 0; j--)
        right[j] = arr[j+1] * right[j+1];
    for (i = 0; i < n; i++)
        prod[i] = left[i] * right[i];
    for (i = 0; i < n; i++)
        printf("%d ", prod[i]);
    return;
}
int main() {
    int arr[] = {10, 3, 5, 6, 2};
    printf("Mang goc: \n");
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\nMang tich: \n");
    productfind(arr, n);
}

Kết quả

Mang goc: 10 3 5 6 2
Mang tich: 180 600 360 300 900