logo标签列表

寻找最小正数的最简洁/最快算法

c++algorithmoptimization
7

简单问题 - 在c++中，最简洁的方法是获取哪个数字（u0和u1）是最小的正数？（仍然有效）

我尝试的每种方法都涉及大量if语句或复杂的条件语句。

谢谢， 丹

这里是一个简单的例子：

bool lowestPositive(int a, int b, int& result)
{
    //checking code
    result = b;
    return true;
}


lowestPositive(5, 6, result);
抱歉，如果两个都是负数，答案是什么？ - Brent.Longborough
返回假！即不返回任何答案，我会编辑问题以提供示例... - Dan
结果应该是什么？0？不变？还是两者中的最小绝对值？ - Joel Coehoorn
16个回答
1

恕我直言，您的问题可能是英语短语描述问题时隐藏了一些复杂性（或至少有一些未解决的问题）。根据我的经验，在“现实世界”中，这是错误和/或未达到预期的常见原因。以下是我观察到的一些问题：

  • 有些程序员使用一种命名约定，其中前导u表示无符号，但您没有明确说明您的“数字”是无符号还是有符号的（或者说，它们是否甚至应该是整数！）

  • 我怀疑我们所有读者都认为，如果一个参数是正数而另一个参数不是，则（唯一的）正参数值是正确的响应，但这并没有明确说明。

  • 该描述还没有定义如果两个值都是非正数时所需的行为。

  • 最后，此帖子之前提供的一些回复似乎暗示回答者错误地认为0是正数！更具体的要求说明可能有助于防止任何误解（或清楚地表明在编写要求时尚未完全考虑到零的问题）。

我并不想过分挑剔；我只是建议更精确地编写要求可能会有所帮助，并且可能还会使您担心实现中的某些复杂性实际上隐含在问题的本质中变得清晰明了。

1

使用（滥用？）三元运算符的三行代码

int *smallest_positive(int *u1, int *u2) {
    if (*u1 < 0) return *u2 >= 0 ? u2 : NULL;
    if (*u2 < 0) return u1;
    return *u1 < *u2 ? u1 : u2;
}

不知道效率或者如果u1和u2都是负数该怎么办。我选择返回NULL（必须在调用者中进行检查）；返回指向静态-1的指针可能更有用。

编辑以反映原始问题中的更改 :)

bool smallest_positive(int u1, int u2, int& result) {
    if (u1 < 0) {
        if (u2 < 0) return false; /* result unchanged */
        result = u2;
    } else {
        if (u2 < 0) result = u1;
        else result = u1 < u2 ? u1 : u2;
    }
    return true;
}
1
由于我手头没有编译器，所以使用伪代码：
////0 if both negative, 1 if u0 positive, 2 if u1 positive, 3 if both positive
switch((u0 > 0 ? 1 : 0) + (u1 > 0 ? 2 : 0)) {
  case 0:
    return false; //Note that this leaves the result value undef.
  case 1:
    result = u0;
    return true;
  case 2:
    result = u1;
    return true;
  case 3:
    result = (u0 < u1 ? u0 : u1);
    return true;
  default: //undefined and probably impossible condition
    return false;
}

这是一个紧凑的代码，没有很多的if语句，而是依赖于三元运算符" ? : "，它只是一个紧凑的if-then-else语句。"(true ? "yes" : "no")"返回"yes"，"(false ? "yes" : "no")"返回"no"。

在普通的switch语句中，每个case后面都应该有一个break;来退出switch。但在这种情况下，我们使用了return语句，因此我们正在退出整个函数。

1
-1：抱歉，但这不是我想在生产中看到的代码类型。有更简洁的方法来获得OP想要的结果，并且您上面switch语句的注释表明您知道代码太“聪明”以至于不再可读。 - Juliet
1
uint lowestPos(uint a, uint b) { return (a < b ? a : b); }

你正在寻找最小的正数，在这种情况下只接受正值是明智的。你不必在函数中解决负值问题，应该在调用函数的早期解决它。出于同样的原因，我留下了布尔值。

前提条件是它们不相等，你会像这样使用它：

if (a == b)
  cout << "equal";
else
{
  uint lowest = lowestPos(a, b);
  cout << (lowest == a ? "a is lowest" : "b is lowest");
}

当你想要防止更改或引用以改变结果时，可以引入const。在正常情况下，计算机会优化甚至内联函数。

0
在我的第一篇帖子被拒绝后，让我建议您不要过早地优化问题，也不必担心有很多if语句。您正在编写的代码自然需要多个“if”语句，无论它们是用三元if运算符（A？B：C）还是经典的if块表示，执行时间都是相同的，编译器将优化几乎所有发布的代码为非常接近的逻辑。
关注您的代码的可读性和可靠性，而不是试图欺骗未来的自己或任何其他阅读代码的人。据我所知，每个发布的解决方案都是O（1），也就是说，每个解决方案对您的代码性能的贡献都微不足道。
我想建议将此帖子标记为“过早优化”，因为发帖者并不寻求优雅的代码。
0

我的想法基于使用最小值和最大值。并将结果分为三种情况：

  • min <= 0 且 max <= 0
  • min <= 0 且 max > 0
  • min > 0 且 max > 0

最好的一点是它看起来不太复杂。 代码：

bool lowestPositive(int a, int b, int& result)
{
    int min = (a < b) ? a : b;
    int max = (a > b) ? a : b;

    bool smin = min > 0;
    bool smax = max > 0;

    if(!smax) return false;

    if(smin) result = min;
    else result = max;

    return true;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接