趣题:用四个数学运算符号译出 EBCDIC 编码

ASCII 编码已经是非常直观了。 65 号字符就是大写字母 A , 66 号字符就是大写字母 B ,以此类推, 90 号字符就是大写字母 Z 。为了看出某个编码究竟对应字母表中的第几个字母,我们只需要用下面的函数关系即可:

f(x) = x - 64

整个函数关系极其简单,里面只包含一个数学运算符号。

当然,历史上也出现过很多非常不直观的字符编码方式。 EBCDIC 是由 IBM 提出的一种字符编码标准,它的编码方式十分古怪,可害苦了当年的那些程序员。据说,当年的程序员没有一个不痛恨 EBCDIC 的。因此, EBCDIC 也理所当然地成为了众人调侃的对象。 Wikipedia 上的 EBCDIC 页面甚至还专门有一节,讲述各种与 EBCDIC 有关的笑话。有一个经典的笑话说的就是,美国政府跑去 IBM ,想要研发一种数据加密标准,于是 EBCDIC 编码就诞生了。经典游戏 Zork 中, EBCDIC 也被用来形容艰涩难懂的文字:

一个大房间里,各式各样笨重的机器在呼呼作响,电阻烧焦了的味儿扑鼻而来。其中一面墙上有三个按钮,形状分别是圆形、三角形和正方形。自然,这些按钮上方的说明文字都是用 EBCDIC 书写的……

那么, EBCDIC 编码究竟有多诡异呢?让我们来看看大写字母 A 到 Z 在 EBCDIC 中的编码吧。

  A B C D E F G H I            
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
  J K L M N O P Q R            
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
    S T U V W X Y Z            
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239

首先,你会注意到,这些字母的编码并不是连续的。 Z 的编码减去 A 的编码并不等于 25 ,而是等于 40 。把基于 ASCII 编码的程序移植到基于 EBCDIC 编码的系统上,就会因为这件事儿而引起不小的麻烦。另外,编码中的两处间隙的长度甚至也不是相同的。从 I 到 J ,编码跳过了 7 个数;从 R 到 S ,编码却跳过了 8 个数。

如果要写出大写字母在 EBCDIC 中的编码和在字母表中的顺序之间的数学关系,这想必是非常困难的。不过,你相信吗,有一种方法可以让我们用四个数学运算符号就把这个数学关系表达出来。具体地说,存在一个只包含四个数学运算符号的函数 g(x) ,使得把上表中用到的编码代入后,所得的函数值正好表示,编码所对应的字母是字母表中的第几个字母。例如, g(193) 就等于 1 , g(233) 就等于 26 。这是怎么做到的呢?

这里所说的数学运算符号包括各种有名字的、能在科学计算器上找到的运算符号,比如加、减、乘、除、乘方、开方、取整、取模、取对数、取绝对值、取较大数、取较小数、取最大公约数、取最小公倍数,甚至是阶乘、三角函数、反三角函数、双曲函数等貌似更不可能派上用场的运算符号。

 

 

 

 

 

 

 

 

 

 

这是一个脑筋急转弯!下面的方法非常赖皮,但却完全符合题意!这个方法的核心思想就是两个字:查表!

g(x) =             ⌊ 26 25 24
23 22 21 20 19 00 00 00 00 00
00 00 00 18 17 16 15 14 13 12
11 10 00 00 00 00 00 00 00 09
08 07 06 05 04 03 02 01 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 ÷ 100x ⌋ mod 100

这里,除号前面是一个 468 位的大数,之前那个表格里的所有信息都写进了这个大数里。为了便于大家观察,我们把这个大数两位两位地分成一组,每 10 组一行。符号 ⌊ ⌋ 表示取下整,即不超过某个数的最大整数。 mod 100 表示取除以 100 后的余数。

这个问题改编自 IBM Ponder This 谜题站 2015 年 12 月的谜题。在计算机算法中允许使用任意大的数(并假设单次运算的复杂度仍为常数级别),这是不符合现实的,同时也是非常赖皮的。如果允许这样赖皮的话,很多算法的理论复杂度都能改进到非常荒谬的程度。这里有一个更有意思的例子: http://www.matrix67.com/blog/archives/1209

12 条评论

发表评论