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

Question

我有 2 个不同的数组分子 [ ]、分母 [ ] 和整数大小为 9。它们都由 9 个不同的整数组成，我需要找到 2 个整数的最小商（百分比 - (numerator[ ])/(denominator[ ]) ）在两个数组中。我该怎么做？

Answer 1

您要return百分比还是商（没有余数）？以下代码 returns 百分比。如果您想要商，请将 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：修复了编译错误——感谢 James Root 指出错误。

这是一道数学题，其次是编程题。

天真的实现是计算第一个数组中的分子除以第二个数组中的分母的每个组合，跟踪最小商，然后计算结果。

这看起来像下面这样：

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

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

C++ Finding the minimum quotient from two different integer arrays of the same size

c++

arrays

minimum