-6

它做了什么 - 索引“i”处的元素是所有输入元素的乘积，但“i”处的输入元素除外。

例如，如果 arr = { 1, 2, 3, 4 }，那么

输出 = { 2*3*4, 1*3*4, 1*2*4, 1*2*3 }。

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int n;
    long long int arr[1000]={0},prod=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        prod*=arr[i];
    }
    if(prod!=0)
        for(int i=0;i<n;i++){
            cout<<(prod/arr[i])<<endl;
        }
    else
        for(int i=0;i<n;i++){
            cout<<"0"<<endl;
        }
    return 0;
}
4

2 回答 2

2

它失败的最简单的情况是 2 0 1. 正确的结果是1 0，你的结果是0 0。

更一般地，如果输入集中恰好有一个零和至少一个非零，则它会失败。

于 2012-08-12T09:47:41.297 回答
0

如前所述，问题是当输入之一为零时，您尝试除以零。为了正确计算乘积，需要一种只执行乘法而不执行除法的算法，例如以下算法。

#include <stdio.h>
#include <stddef.h>

// Input: an array of 2^(exp) doubles
// Output: an array of 2^(exp) doubles, where each one is the
//         product of all the numbers at different indices in
//         the input
// Return value: the product of all inputs
double products (unsigned int exp, const double *in, double *out)
{
    if (exp == 0) {
        out[0] = 1;
        return in[0];
    }

    size_t half_n = (size_t)1 << (exp - 1);

    double prod_left = products(exp - 1, in, out);
    double prod_right = products(exp - 1, in + half_n, out + half_n);

    for (size_t i = 0; i < half_n; i++) {
        out[i] *= prod_right;
        out[half_n + i] *= prod_left;
    }

    return prod_left * prod_right;
}

int main ()
{
    double in[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    double out[8];
    products(3, in, out);

    for (size_t i = 0; i < 8; i++) {
        printf("%f ", out[i]);
    }
    printf("\n");

    return 0;
}

这需要 O(n*log(n)) 时间并且没有额外的空间，除了递归使用的 O(log(n)) 空间。虽然它很好且易于理解，但它并不是最优的；看到这个问题。

于 2012-08-12T11:03:48.333 回答