-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です。

より一般的には、入力セットにゼロが1つだけあり、ゼロ以外が少なくとも1つある場合は失敗します。

于 2012-08-12T09:47:41.297 に答える
0

すでに述べたように、問題は入力の 1 つがゼロで、ゼロで除算しようとした場合です。積を適切に計算するには、次のような乗算のみを実行し、除算を実行しないアルゴリズムが必要です。

#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 に答える