一种比较三个变量对的数学方法

13

我被分配任务,在Java中比较一对3个正double变量,而忽略它们的顺序。

我进行了以下操作:

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

我听老师说有一种数学方法可以比较这三个数字。

到目前为止,我已经尝试过它们的加减、它们的平方和,但总会发现存在一种情况使得这三个数字不同且陈述是真实的。

有什么想法吗?

编辑:

我已经提交了作业,老师说我的答案是正确的。我只是出于好奇在问。


我投票关闭这个问题,因为我认为回答这个问题会帮助提问者作弊。如果老师说有答案,那么他或她肯定会在适当的时候揭示它。干涉并不是我们的职责。 - ControlAltDel
1
@ControlAltDel 这不算作弊,因为我已经提交了作业……我只是出于好奇在问。 - AceVentuRa
2
我们从什么时候开始不帮助别人做作业了? - WJS
你能添加那些情况吗,即“对不同的一对进行比较时,语句为真”? - Eritrean
2
@ControlAltDel 这不是离题,因为原帖明确指出了他们尝试的代码以及解决难点。对于作业问题并没有分类禁止。请参见关于主题的指南中的第三点。 - EJoshuaS - Stand with Ukraine
显示剩余5条评论
2个回答

11

简述

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

详细说明

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

利用这个事实,我们将零点设为a1、a2和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的所有整数分割,取它们的乘积,找到重复项并选择一对。


1
我希望我们能够使用LaTeX。 - Joseph Wood
1
但在您的FTA方法中,必须完成所有测试。在暴力方法中,一些比较将被短路。所以情况并不像看起来那么糟糕。 - WJS
2
@WJS,同意。你也可以说同样的事情,只是不像暴力方法那样极端。事实上,我敢打赌,在大多数情况下,由于短路机制,暴力方法可能会更快。说实话,如果我要编写这个代码,我可能会使用暴力方法,因为它更容易理解。 - Joseph Wood

-1

如果您可以进行排序(a1 <= b1 <= c1,并且a2 <= b2 <= c2),那么请尝试使用质数2、3、5作为基础,将2^a1 * 3^b1 * 5^c1与2^a2 * 3^b2 * 5^c2进行比较。


你能解释一下这个答案吗? - AceVentuRa
1
如果允许排序,那么你所需要做的就是比较a1 == b1、a2 = b2和a3 == b3。 - JB Nizet
@Bruno 我教授的意思是在if语句中,写出数学方式进行比较,而不需要排序。 - AceVentuRa
如何使用可能带有小数的双精度值来计算质数。 - WJS

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