这种算法在哪种情况下失败?
它是做什么的 - 索引'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;
}
失败的最简单情况是2 0 1
。正确的结果是1 0
,你的结果是0 0
。
更一般地说,如果在输入集合中只有一个零和至少一个非零,它就会失败。
这种情况下的输出将如何成为'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。
你知道它失败吗?或者你要求人们进行代码审查吗? – mathematician1975 2012-08-12 09:36:43
它失败。我无法弄清楚哪种情况,但 – h4ck3d 2012-08-12 09:37:59
你怎么知道它失败? – celtschk 2012-08-12 09:47:07