java - 比较一对 3 个变量的数学方法
问题描述
我被分配在 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,但我总是发现一对不同的情况,并且陈述是正确的。
有任何想法吗?
编辑:
我已经发了作业,老师说我的回答是真的。我是出于好奇而问的。
解决方案
TL;博士
比较每个三元组的总和、每个三元组的乘积以及每个三元组所有可能组合的乘积之和。
坚韧不拔
根据代数基本定理,对于 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, a3
并且b1, b2, b3
是等价的。
这值得么?
从实际的角度来看,让我们看看这是否确实比 OP 所示的蛮力检查更有效。
第一次检查:总结和比较。这需要 4 次总加法和 1 次相等性检查。
检查总数 = 5;运行总数 = 5
第二次检查:Product、Sum 和 Compare。这需要总共 6 次乘法,总共 4 次加法和 1 次相等性检查。
检查总数 = 11;运行总数 = 16
第三次检查:产品和比较。这需要 4 次总乘法和 1 次相等性检查。
检查总数 = 5;运行总数 = 21
将两个逻辑与运算相加,“生成多项式方法的系数”的二进制运算总数只需要:
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的所有整数分区,取它们的乘积,找到重复项,然后选择一对。
推荐阅读
- python - 如何在 Django 模板中打印“更改字段”的值
- php - 将 Wordpress 中的 JSON 链接读入表格
- javascript - 在数组内映射数组
- c++ - 从别名模板中提取模板参数的值
- c++ - 我正在尝试从文本文件中读取并将它们分类为不同的结构成员,但我不知道哪里出错了
- javascript - Slonik 通过 sql 标签动态插入查询
- python - python sqlite - 条件为空
- python - 如何替换 tkinter 中的文本/图像?
- java - BufferedReader 超时
- compiler-errors - 以下 Fortran 代码有什么问题?(gfortran) (1) 处的 DTIO 虚拟参数必须是 ASSUMED SHAPE ARRAY