這種算法在哪種情況下失敗？

-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

這種算法在哪種情況下失敗？

回答

相關問題