C++从两个相同大小的不同整数数组中求最小商数

Question

我有两个不同的数组numerator []，分母[]和int大小是9.它们都由9个不同的整数组成，我需要找到两个数组中的最小商数为 （百分比 - （分子[]）/（分母[]）））。我会如何去做这件事？

Answer 1

是否要返回百分比或商（无余数）？ 以下代码返回百分比。如果你想要商，则将double更改为int。

#include<limits> 
double lowestQuotient(const int *numerator, const int *denominator) 
{ 
    double min=DBL_MAX; 
    double quotient; 
for(i=0;i<9;i++) 
{ 
    if (denominator[i]==0) 
     continue; 
    quotient = (double)numerator [i]/denominator [i]; 
    if (i==0 || quotient<min) 
    min=quotient; 
} 
return min; 

} 

Answer 2

编辑：这个答案写问题陈述改为澄清说，其意图并不是每个组合比较前，而是仅仅采取成对商。这很简化了这个问题，并使我冗长的解决方案在这里矫枉过正。这也写在涉及浮点值的解决方案之前;我假设提问者对两个整数的商的数学定义感兴趣，这个整数本身就是一个整数。尽管如此，我会在这里把这个留给后人...

编辑2：修正编译错误 - 詹姆斯感谢为根指出错误。

这是一个数学问题，第二个是编程问题。

简单的实现方法是计算第一个数组的分子除以第二个数组中的分母的每个组合，跟踪最小商，并计算结果。

这看起来像下面这样：

#include <climits> 
#include <algorithm> 

int minimum_quotient(int numerator[], int denominator[], int size) 
{ 
    int minimum = INT_MAX; // minimum quotient 
    for (int i = 0; i < size; ++i) 
     for (int j = 0; j < size; ++j) 
      if (denominator[j] != 0) // avoid division by 0 
       minimum = std::min(minimum, numerator[i]/denominator[j]); 
    return 0; 
} 

随着size是已知的，数量不多，这应该是足够了。但是，如果我们担心size变得非常大的情况，我们可能希望避免上述书面解决方案，该解决方案与输入大小的平方成比例。

这是一个解决方案的想法，可以用更大的尺寸进行扩展。具体而言，它与输入的大小呈线性关系。我们可以利用以下事实：

如果分子和分母都具有相同符号，则最小商将来自绝对值最小的分子和绝对值最大的分子。

如果分子和分母的符号相反，则情况正好相反：对于最小商，我们希望分子具有最大绝对值，分母具有最小绝对值。

我们可以通过这两个列表重复一次，累积最大和最小的分子和分母，然后比较这些在年底寻找最小商：

#include <climits> 
#include <algorithm> 

int minimum_quotient(int numerator[], int denominator[], int size) 
{ 
    int min_num = INT_MAX, min_den = INT_MAX; 
    int max_num = INT_MIN, max_den = INT_MIN; 
    for (int i = 0; i < size; ++i) 
    { 
     min_num = std::min(min_num, numerator[i]); 
     max_num = std::max(max_num, numerator[i]); 
     min_den = std::min(min_den, denominator[i]); 
     max_den = std::max(max_den, denominator[i]); 
    } 
    int minimum = INT_MAX; 
    if (min_den != 0) 
    { 
     minimum = std::min(minimum, min_num/min_den); 
     minimum = std::min(minimum, max_num/min_den); 
    } 
    if (max_den != 0) 
    { 
     minimum = std::min(minimum, min_num/max_den); 
     minimum = std::min(minimum, max_num/max_den); 
    } 
    return minimum; 
}