Re: [征集]算24点全解无重复程序
发表于 : 2016年09月04日 13:26
4nums 网上有一些表达式形式归并的约定和理论
http://www.4nums.com/theory/
Given any quadruple that is solvable, we always want to know all the solutions. Some solutions are obviously different, some are obviously equivalent, some are less so.
We discuss our "theory" on how we present solutions in a less redudant way. i.e. we only present one solution out of all equivalent solutions. Furthermore, we'd like to present the most concise solution among all equivalent solutions.
Notations:
a, b, c, d are numbers (1,2,3 etc), x, y, z, w are expressions eg. 1, 1 + 2, (1 + 2 × 6) /5, etc.
Two expressions x and y are equivalent then we say x ? y, eg. a + b ? b + a, a - (b - c) ? a + c - b .
If two expressions x and y are equivalent, and we prefer y over x for its conciseness and/or easy human computer interaction, then we say x → y . For example: a - (b - c) ? a + c - b , but we prefer the latter, so we have a - (b - c) → a + c - b
± is + or -, and ×/ is × or /.
Part 1: elementary arithmetic equivalences
This part should be rather obvious. 1 × 2 × 3 × 4 and (4 × 3 × ( 2 × 1)) make no difference but obviously a lot of people prefer the first expression for its simplicity.
The rules in Part 1 can be summarized in one line: replace numbers with variables, and if two expressions have the same value for any choice of integer values, then these two expressions are equivalent. For example, for the quadruple {1,2,3,4} and two expressions: (3 + 2 + 1) × 4 and 4 × (1 + 2 + 3) : , we first replace 1 with a, 2 with b, 3 with c and 4 with d, now the two expressions become (c + b + a) × d and d × ( a + b + c). These two expressions have the same evaluation for any integer quadruple {a,b,c,d}. So we know that these two expressions are equivalent. Among (3 + 2 + 1) × 4 and 4 × (1 + 2 + 3), we prefer the former one. The reason is that for some human computer interface (think of calculators), brackets are not needed for (3 + 2 + 1) × 4. aka 4 × (1 + 2 + 3) → (3 + 2 + 1) × 4 . A general rule of thumb in determining our preference over equivalent expressions is that we prefer those with the more complicated part on the left most side.
Before giving the details of the Part 1 rules, we need one more footnote. For two expressions x and y (recall that x could be a + b), when we write x ×/ y, we add brackets around x or y when necessary.
(1) Commutativity: x ± y ? ± y + x ; x × y ? y × x ; x ×/ y ×/ z ? x ×/ z ×/ y
Preference 1: - and / on the right most side, eg. - a + b → b - a, a / b × c → a × c / b
Preference 2: those with more complicated expression(s) on the left, eg. c + a × b → a × b + c, a × (b + c) → (b + c) × a ...
(2) Associativity: x + y ± z ? ( x + y ) ± z ? x + (y ± z ) ; x × y ×/ z ? ( x × y ) ×/ z ? x × (y ×/ z ) ; ( x / y ) / z ? x / y / z
Preference: those with fewer brackets, e.g. (a + b) + c → a + b + c, (a / b) / c → a / b / c .
(3) Exchangeability between + and -, and, × and / : x - (y - z) ? x + z - y ; x × z / y ? x/(y/z) ; x /(y × z) ? x/y/z
Preference: those with fewer brackets, eg. a - (b - c) → a + c - b, a/(c/b) → a × b / c
(4) Less negativity is preferred: a - (b - c) ×/ d ? a + (c - b) ×/ d, note: this rule is not covered by rule (3).
Preferences: by preference in rule (3) we have: a - (b - c) ×/ d → (c - b) ×/ d + a
(5)Tie breakers: a × b × c × d or d × c × b × a, (a + b) × (c + d) or (d + c) × (a + b)?
Preferences: doesn't matter. I prefer my bigger numbers on the left most side, i.e. 1 × 2 × 3 × 4 → 4 × 3 × 2 × 1, (1 + 2) × (5 + 3) → (5 + 3) × (2 + 1)
Part 2: special rules for expressions with value 0 or 1
(6) Multiplication/Division with 1: x × y ? x / y, if the evaluation of y is 1.
Preference: x × y, eg. (13 + 11) / (5 - 4) → (13 + 11) × (5 - 4). Similarly (12 + 6 × 2) / 1 → (12 + 6 × 2) × 1.
(7) Placement of × z, when the value of z is 1: if z = 1, then we have: x + y × z ? x × z + y ? (x + y ) × z
Preferences: (x + y ) × z for symmetry
(8) The interesting case of {a, b, c, c} : a × b × c /c ? a × b + c - c, and ( a + b ) × c /c ? a + b + c - c .
Preference: a × b + c - c or a + b + c - c
(8.b) The final case of {a, b, 1, 1} : a × b × 1 × 1 ? a × b + 1 - 1, and ( a + b ) × 1 × 1 ? a + b + 1 - 1 .
Preference: a × b + 1 - 1 or a + b + 1 - 1
(8.c) The final final case of 24 : this case is only relevant when we play the bigger game where 24 is one of the 4 numbers.
24 × x / y → 24 + x - y, here x and y are two expressions with the same value
24 + a - b - c → 24 + b + c - a
24 + c - x is preferred over x + 24 - c where x is an expression composed of two numbers, obviously c and x has the same value.
The above three seemingly random rules cut a bunch of "gimmick" different solutions where 24 is envolved.
译文
给出任何一组可解的四个数时, 我们总想知道所有的解. 有些解显然不等价, 有些解显然等价, 有些解等价与否不那么明显.
我们用 "理论" 来阐述如何用最少的冗余形式来呈现解. 例如, 我们只从所有等价的解中抽取出一个. 而且, 我们想从所有等价的解中提出最简明的解.
记法约定:
a, b, c, d 表示数字 (1,2,3 等), x, y, z, w 表示表达式 例如 1, 1 + 2, (1 + 2 × 6) /5, 等.
两个表达式 x 和 y 等价, 我们表示为 x ? y, 例如 a + b ? b + a, a - (b - c) ? a + c - b .
若两个表达式 x 和 y 等价, 而且我们选择 y 代替 x 因为更简明 和/或 更易于人机交互, 我们表示为 x → y . 例: a - (b - c) ? a + c - b , 但我们更喜欢后者, 所以 a - (b - c) → a + c - b
± 表示 + 或 -, 另外 ×/ 表示 × 或 /.
1: 基本算术等价
此部分较明显. 1 × 2 × 3 × 4 和 (4 × 3 × ( 2 × 1)) 没有不同, 但显然人们更喜欢第一个表达式, 因为它简单.
此部分规则可以概总为一行: 数字替换成变量, 且当两个表达式应用于任何整数组时都得到相同的结果, 那么这两个表达式等价.
例如, 对四元组 {1,2,3,4} 和两个表达式: (3 + 2 + 1) × 4 和 4 × (1 + 2 + 3) : , 我们先把 1 替换成 a, 2 替换成 b, 3 替换成 c 以及 4 替换成 d, 现在两个表达式成为 (c + b + a) × d 和 d × ( a + b + c). 对于任意四元组 {a,b,c,d}, 这两个表达式都有相同的运算结果. 所以我们知道这两个表达式是等价的. 在 (3 + 2 + 1) × 4 和 4 × (1 + 2 + 3) 两者间, 我们更喜欢前者. 理由是对于一些人机交互 (想想计算器), 对于 (3 + 2 + 1) × 4, 括号是不需要的. 亦作 4 × (1 + 2 + 3) → (3 + 2 + 1) × 4 . 经验上, 在等价表达式中作选择的一般规则是, 我们更喜欢那些更复杂的部分在最左边的.
在给出第 1 部分的细节前, 我们需要一点脚注. 对两个表达式 x 和 y (设想 x 可能形如 a + b), 当我们写出 x ×/ y 时, 在必要时我们要把 x 或 y 用括号包起来.
(1) 交换律: x ± y ? ± y + x ; x × y ? y × x ; x ×/ y ×/ z ? x ×/ z ×/ y
偏爱 1: - 和 / 放在右边, 例 - a + b → b - a, a / b × c → a × c / b
偏爱 2: 更复杂的表达式在左边的, 例 c + a × b → a × b + c, a × (b + c) → (b + c) × a ...
(2) 结合律: x + y ± z ? ( x + y ) ± z ? x + (y ± z ) ; x × y ×/ z ? ( x × y ) ×/ z ? x × (y ×/ z ) ; ( x / y ) / z ? x / y / z
偏爱: 括号尽量少或者没有的, 例 (a + b) + c → a + b + c, (a / b) / c → a / b / c .
(3) + 和 -, 以及, × 和 / 的变换律 : x - (y - z) ? x + z - y ; x × z / y ? x/(y/z) ; x /(y × z) ? x/y/z
偏爱: 括号尽量少或者没有的, 例 a - (b - c) → a + c - b, a/(c/b) → a × b / c
(4) 更喜欢少用负号的: a - (b - c) ×/ d ? a + (c - b) ×/ d, 注意: 此规则不被规则 (3) 包含.
偏爱: 依规则 (3) 的偏爱有: a - (b - c) ×/ d → (c - b) ×/ d + a
(5)连串: 选 a × b × c × d 还是 d × c × b × a, 选 (a + b) × (c + d) 还是 (d + c) × (a + b)?
偏爱: 没关系. 我更喜欢更大的数在最左边, 例如 1 × 2 × 3 × 4 → 4 × 3 × 2 × 1, (1 + 2) × (5 + 3) → (5 + 3) × (2 + 1)
2: 表达式运算值为 0 或 1 的特殊规则
(6) 乘以或者除以 1: x × y ? x / y, 如果 y 的运算值为 1.
偏爱: x × y, 例 (13 + 11) / (5 - 4) → (13 + 11) × (5 - 4). 类似地 (12 + 6 × 2) / 1 → (12 + 6 × 2) × 1.
(7) 放置 × z, 当 z 的运算值为 1: 若 z = 1, 我们有: x + y × z ? x × z + y ? (x + y ) × z
偏爱: (x + y ) × z 更匀称
(8) {a, b, c, c} 是有趣的: a × b × c /c ? a × b + c - c, 还有 ( a + b ) × c /c ? a + b + c - c .
偏爱: a × b + c - c 或者 a + b + c - c
(8.b) 最后关于 {a, b, 1, 1} : a × b × 1 × 1 ? a × b + 1 - 1, 还有 ( a + b ) × 1 × 1 ? a + b + 1 - 1 .
偏爱: a × b + 1 - 1 or a + b + 1 - 1
(8.c) 最最后关于 24 : 这个只关于我们玩更大数值的游戏, 而 24 是四元组其中一个数时.
24 × x / y → 24 + x - y, 这里 x 和 y 是运算值相等的两个表达式
24 + a - b - c → 24 + b + c - a
选择 24 + c - x 而非 x + 24 - c , 此处 x 是包含两个数的表达式, 明显地, c 和 x 有相同的运算值.
当 24 被包含在四元组中时, 以上三个看起来随意的规则可以削减掉一堆花招不同的解.
http://www.4nums.com/theory/
Given any quadruple that is solvable, we always want to know all the solutions. Some solutions are obviously different, some are obviously equivalent, some are less so.
We discuss our "theory" on how we present solutions in a less redudant way. i.e. we only present one solution out of all equivalent solutions. Furthermore, we'd like to present the most concise solution among all equivalent solutions.
Notations:
a, b, c, d are numbers (1,2,3 etc), x, y, z, w are expressions eg. 1, 1 + 2, (1 + 2 × 6) /5, etc.
Two expressions x and y are equivalent then we say x ? y, eg. a + b ? b + a, a - (b - c) ? a + c - b .
If two expressions x and y are equivalent, and we prefer y over x for its conciseness and/or easy human computer interaction, then we say x → y . For example: a - (b - c) ? a + c - b , but we prefer the latter, so we have a - (b - c) → a + c - b
± is + or -, and ×/ is × or /.
Part 1: elementary arithmetic equivalences
This part should be rather obvious. 1 × 2 × 3 × 4 and (4 × 3 × ( 2 × 1)) make no difference but obviously a lot of people prefer the first expression for its simplicity.
The rules in Part 1 can be summarized in one line: replace numbers with variables, and if two expressions have the same value for any choice of integer values, then these two expressions are equivalent. For example, for the quadruple {1,2,3,4} and two expressions: (3 + 2 + 1) × 4 and 4 × (1 + 2 + 3) : , we first replace 1 with a, 2 with b, 3 with c and 4 with d, now the two expressions become (c + b + a) × d and d × ( a + b + c). These two expressions have the same evaluation for any integer quadruple {a,b,c,d}. So we know that these two expressions are equivalent. Among (3 + 2 + 1) × 4 and 4 × (1 + 2 + 3), we prefer the former one. The reason is that for some human computer interface (think of calculators), brackets are not needed for (3 + 2 + 1) × 4. aka 4 × (1 + 2 + 3) → (3 + 2 + 1) × 4 . A general rule of thumb in determining our preference over equivalent expressions is that we prefer those with the more complicated part on the left most side.
Before giving the details of the Part 1 rules, we need one more footnote. For two expressions x and y (recall that x could be a + b), when we write x ×/ y, we add brackets around x or y when necessary.
(1) Commutativity: x ± y ? ± y + x ; x × y ? y × x ; x ×/ y ×/ z ? x ×/ z ×/ y
Preference 1: - and / on the right most side, eg. - a + b → b - a, a / b × c → a × c / b
Preference 2: those with more complicated expression(s) on the left, eg. c + a × b → a × b + c, a × (b + c) → (b + c) × a ...
(2) Associativity: x + y ± z ? ( x + y ) ± z ? x + (y ± z ) ; x × y ×/ z ? ( x × y ) ×/ z ? x × (y ×/ z ) ; ( x / y ) / z ? x / y / z
Preference: those with fewer brackets, e.g. (a + b) + c → a + b + c, (a / b) / c → a / b / c .
(3) Exchangeability between + and -, and, × and / : x - (y - z) ? x + z - y ; x × z / y ? x/(y/z) ; x /(y × z) ? x/y/z
Preference: those with fewer brackets, eg. a - (b - c) → a + c - b, a/(c/b) → a × b / c
(4) Less negativity is preferred: a - (b - c) ×/ d ? a + (c - b) ×/ d, note: this rule is not covered by rule (3).
Preferences: by preference in rule (3) we have: a - (b - c) ×/ d → (c - b) ×/ d + a
(5)Tie breakers: a × b × c × d or d × c × b × a, (a + b) × (c + d) or (d + c) × (a + b)?
Preferences: doesn't matter. I prefer my bigger numbers on the left most side, i.e. 1 × 2 × 3 × 4 → 4 × 3 × 2 × 1, (1 + 2) × (5 + 3) → (5 + 3) × (2 + 1)
Part 2: special rules for expressions with value 0 or 1
(6) Multiplication/Division with 1: x × y ? x / y, if the evaluation of y is 1.
Preference: x × y, eg. (13 + 11) / (5 - 4) → (13 + 11) × (5 - 4). Similarly (12 + 6 × 2) / 1 → (12 + 6 × 2) × 1.
(7) Placement of × z, when the value of z is 1: if z = 1, then we have: x + y × z ? x × z + y ? (x + y ) × z
Preferences: (x + y ) × z for symmetry
(8) The interesting case of {a, b, c, c} : a × b × c /c ? a × b + c - c, and ( a + b ) × c /c ? a + b + c - c .
Preference: a × b + c - c or a + b + c - c
(8.b) The final case of {a, b, 1, 1} : a × b × 1 × 1 ? a × b + 1 - 1, and ( a + b ) × 1 × 1 ? a + b + 1 - 1 .
Preference: a × b + 1 - 1 or a + b + 1 - 1
(8.c) The final final case of 24 : this case is only relevant when we play the bigger game where 24 is one of the 4 numbers.
24 × x / y → 24 + x - y, here x and y are two expressions with the same value
24 + a - b - c → 24 + b + c - a
24 + c - x is preferred over x + 24 - c where x is an expression composed of two numbers, obviously c and x has the same value.
The above three seemingly random rules cut a bunch of "gimmick" different solutions where 24 is envolved.
译文
给出任何一组可解的四个数时, 我们总想知道所有的解. 有些解显然不等价, 有些解显然等价, 有些解等价与否不那么明显.
我们用 "理论" 来阐述如何用最少的冗余形式来呈现解. 例如, 我们只从所有等价的解中抽取出一个. 而且, 我们想从所有等价的解中提出最简明的解.
记法约定:
a, b, c, d 表示数字 (1,2,3 等), x, y, z, w 表示表达式 例如 1, 1 + 2, (1 + 2 × 6) /5, 等.
两个表达式 x 和 y 等价, 我们表示为 x ? y, 例如 a + b ? b + a, a - (b - c) ? a + c - b .
若两个表达式 x 和 y 等价, 而且我们选择 y 代替 x 因为更简明 和/或 更易于人机交互, 我们表示为 x → y . 例: a - (b - c) ? a + c - b , 但我们更喜欢后者, 所以 a - (b - c) → a + c - b
± 表示 + 或 -, 另外 ×/ 表示 × 或 /.
1: 基本算术等价
此部分较明显. 1 × 2 × 3 × 4 和 (4 × 3 × ( 2 × 1)) 没有不同, 但显然人们更喜欢第一个表达式, 因为它简单.
此部分规则可以概总为一行: 数字替换成变量, 且当两个表达式应用于任何整数组时都得到相同的结果, 那么这两个表达式等价.
例如, 对四元组 {1,2,3,4} 和两个表达式: (3 + 2 + 1) × 4 和 4 × (1 + 2 + 3) : , 我们先把 1 替换成 a, 2 替换成 b, 3 替换成 c 以及 4 替换成 d, 现在两个表达式成为 (c + b + a) × d 和 d × ( a + b + c). 对于任意四元组 {a,b,c,d}, 这两个表达式都有相同的运算结果. 所以我们知道这两个表达式是等价的. 在 (3 + 2 + 1) × 4 和 4 × (1 + 2 + 3) 两者间, 我们更喜欢前者. 理由是对于一些人机交互 (想想计算器), 对于 (3 + 2 + 1) × 4, 括号是不需要的. 亦作 4 × (1 + 2 + 3) → (3 + 2 + 1) × 4 . 经验上, 在等价表达式中作选择的一般规则是, 我们更喜欢那些更复杂的部分在最左边的.
在给出第 1 部分的细节前, 我们需要一点脚注. 对两个表达式 x 和 y (设想 x 可能形如 a + b), 当我们写出 x ×/ y 时, 在必要时我们要把 x 或 y 用括号包起来.
(1) 交换律: x ± y ? ± y + x ; x × y ? y × x ; x ×/ y ×/ z ? x ×/ z ×/ y
偏爱 1: - 和 / 放在右边, 例 - a + b → b - a, a / b × c → a × c / b
偏爱 2: 更复杂的表达式在左边的, 例 c + a × b → a × b + c, a × (b + c) → (b + c) × a ...
(2) 结合律: x + y ± z ? ( x + y ) ± z ? x + (y ± z ) ; x × y ×/ z ? ( x × y ) ×/ z ? x × (y ×/ z ) ; ( x / y ) / z ? x / y / z
偏爱: 括号尽量少或者没有的, 例 (a + b) + c → a + b + c, (a / b) / c → a / b / c .
(3) + 和 -, 以及, × 和 / 的变换律 : x - (y - z) ? x + z - y ; x × z / y ? x/(y/z) ; x /(y × z) ? x/y/z
偏爱: 括号尽量少或者没有的, 例 a - (b - c) → a + c - b, a/(c/b) → a × b / c
(4) 更喜欢少用负号的: a - (b - c) ×/ d ? a + (c - b) ×/ d, 注意: 此规则不被规则 (3) 包含.
偏爱: 依规则 (3) 的偏爱有: a - (b - c) ×/ d → (c - b) ×/ d + a
(5)连串: 选 a × b × c × d 还是 d × c × b × a, 选 (a + b) × (c + d) 还是 (d + c) × (a + b)?
偏爱: 没关系. 我更喜欢更大的数在最左边, 例如 1 × 2 × 3 × 4 → 4 × 3 × 2 × 1, (1 + 2) × (5 + 3) → (5 + 3) × (2 + 1)
2: 表达式运算值为 0 或 1 的特殊规则
(6) 乘以或者除以 1: x × y ? x / y, 如果 y 的运算值为 1.
偏爱: x × y, 例 (13 + 11) / (5 - 4) → (13 + 11) × (5 - 4). 类似地 (12 + 6 × 2) / 1 → (12 + 6 × 2) × 1.
(7) 放置 × z, 当 z 的运算值为 1: 若 z = 1, 我们有: x + y × z ? x × z + y ? (x + y ) × z
偏爱: (x + y ) × z 更匀称
(8) {a, b, c, c} 是有趣的: a × b × c /c ? a × b + c - c, 还有 ( a + b ) × c /c ? a + b + c - c .
偏爱: a × b + c - c 或者 a + b + c - c
(8.b) 最后关于 {a, b, 1, 1} : a × b × 1 × 1 ? a × b + 1 - 1, 还有 ( a + b ) × 1 × 1 ? a + b + 1 - 1 .
偏爱: a × b + 1 - 1 or a + b + 1 - 1
(8.c) 最最后关于 24 : 这个只关于我们玩更大数值的游戏, 而 24 是四元组其中一个数时.
24 × x / y → 24 + x - y, 这里 x 和 y 是运算值相等的两个表达式
24 + a - b - c → 24 + b + c - a
选择 24 + c - x 而非 x + 24 - c , 此处 x 是包含两个数的表达式, 明显地, c 和 x 有相同的运算值.
当 24 被包含在四元组中时, 以上三个看起来随意的规则可以削减掉一堆花招不同的解.