比较一对 3 个变量的择偶方式

2022-09-04 22:04:17

我被赋予了在Java中比较一对3个正双精度变量的任务,同时忽略了它们的顺序。我做了以下操作:

if ((a1 == a2 && b1 == b2 && c1 == c2) ||
    (a1 == a2 && b1 == c2 && c1 == b2) ||
    (a1 == b2 && b1 == a2 && c1 == c2) ||
    (a1 == b2 && b1 == c2 && c1 == a2) ||
    (a1 == c2 && b1 == a2 && c1 == b2) ||
    (a1 == c2 && b1 == b2 && c1 == a2))
    // if true

我从老师那里听说,有一种数学方法可以比较这对3个数字。

到目前为止,我试图比较他们的加法,减法,他们的功数之和2,但我总是发现一个情况,即该对是不同的,并且陈述是正确的。

有什么想法吗?

编辑:

我已经发送了作业,老师说我的答案是真的。我是出于好奇问的。


答案 1

TL;DR

比较每个三元组的总和、每个三元组的乘积以及每个三元组所有可能组合的乘积之和。

细节

根据代数基本定理,对于N次多项式,我们必须有N个根。

利用这个事实,我们设零为 。现在,我们找到了这个多项式的系数。a1, a2, and a3

(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3) 
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3

x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)

如果两个多项式是等价的,它们必须具有相同的根(同样由FTA)。因此,我们需要做的就是比较生成的多项式的系数。

所以,如果,

(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
      ---equivalently---
a1 + a2 + a3 == b1 + b2 + b3

(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)

-1 * a1a2a3 == -1 * b1b2b3
      ---equivalently---
a1a2a3 == b1b2b3

然后我们可以得出三元组的结论,并且是等价的。a1, a2, a3b1, b2, b3

值得吗?

从实际的角度来看,让我们看看这是否确实比OP所示的蛮力检查更有效。

第一个检查:求和和比较。这需要总共增加4次和1次相等检查。

检查总数 = 5;运行总计 = 5

第二个检查:产品、总和和比较。这需要总共 6 次乘法,4 次加法,以及 1 次相等检查。

检查总数 = 11;运行总计 = 16

第三次检查:产品和比较。这需要总共 4 次乘法和 1 次相等检查。

检查总数 = 5;运行总计 = 21

将两个逻辑 AND 运算相加,“生成的多项式方法的系数”的二元运算总数只需要:

23 个二进制操作

暴力破解检查需要 18 个总相等检查、12 个逻辑 AND 比较和 5 个逻辑 OR 比较,总共需要:

35 个二进制操作

所以,严格来说,答案是肯定的,“生成的多项式方法的系数”确实更有效。然而,正如@WJS所指出的那样,蛮力方法有更多的短路机会,因此执行效率与数学方法相同/更有效。

完全彻底

我们不能跳过检查每个三元组的所有可能组合的乘积之和。如果我们撇开这一点,就会有无数的例子表明这失败了。考虑和 *(23, 32, 45)(24, 30, 46)

23 + 32 + 45 = 100
24 + 30 + 46 = 100

23 * 32 * 45 = 33120
24 * 30 * 46 = 33120

它们不等价,但给出相同的总和和乘积。但是,它们不会给出所有可能组合的乘积的相同和:

23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204

*如果有人好奇如何推导出与上面类似的示例,请首先生成长度为3的整数M的所有整数分区,获取它们的乘积,找到重复项,然后选择一对。


答案 2

如果允许您进行排序(a1 <= b1 <= c1 和 a2 <= b2 <= c2),请尝试将 2^a1*3^b1*5^c1 与 2^a2*3^b2*5^c2 进行比较(使用素数 2、3、5 作为基础)