这种算法在哪种情况下失败？

-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; 
}

来源

2012-08-12 h4ck3d

你知道它失败吗？或者你要求人们进行代码审查吗？ – mathematician1975 2012-08-12 09:36:43

它失败。我无法弄清楚哪种情况，但 – h4ck3d 2012-08-12 09:37:59

你怎么知道它失败？ – celtschk 2012-08-12 09:47:07

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

更一般地说，如果在输入集合中只有一个零和至少一个非零，它就会失败。

来源

2012-08-12 09:47:41

这种情况下的输出将如何成为'1 0'？ {0 * 1,2 * 1,2 * 0}应该是输出的权利？ – h4ck3d 2012-08-12 13:15:47

第一位数字是计数（见'cin >> n'）。数据集为“0 1”，大小为“2”。 – 2012-08-13 01:21:48

正如已经指出的那样，问题是其中一个输入为零，而您尝试除以零。为了正确地计算产品，需要一种只执行乘法和不分割的算法，例如下面的算法。

#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 *日志（n））的时间也没有多余的空间，除了由递归使用的O（日志（n））的空间。虽然它很好理解，但它不是最佳的;见this question。

来源

2012-08-12 11:03:48

这种算法在哪种情况下失败？

回答

相关问题