• 欢迎访问举个栗子网站
  • 小说APP下载 xsz.tw 不带广告的小说站

举个栗子:N进制这么好玩,你知道吗?

日报 举个栗子 2年前 (2017-11-16) 272次浏览 0个评论 扫描二维码

举个栗子:N 进制这么好玩,你知道吗?

【一个传统小游戏】

设计四张卡片:

第一张写有  1, 3, 5, 7, 9,11,13,15

第二张写有  2, 3, 6, 7,10,11,14,15

第三张写有  4, 5, 6, 7,12,13,14,15

第四张写有  8, 9,10,11,12,13,14,15

某甲心里想一个 0-15 间的整数,告诉你此数共在哪些卡片里有。你将这些卡片的第一个数加起来,就得到某甲心里想的那个数。

这个游戏很多人见过,但未必都知道其背后的数学道理就是二进制。解释如下:

第一张卡片中是 0-15 间所有二进制表示为 xxx1 的数,而其第一个数是 0001。第二张卡片中是 0-15 间所有二进制表示为 xx1x 的数,而其第一个数是 0010。后两张类推。

例如,某甲心里想的数是 13,这个数的二进制表示是 1101,因此它在第一、三、四张卡片里有,而且正等于 0001 + 0100 + 1000。

【几个 IT 相关的二进制问题】

1.在美国的公司刚刚工作不久的一天,一位计算机专业的小伙子跑来找我,说他新装的 VB6 是有 BUG 的,让我看看。他的即时窗口里显示: 3.0 – 2.99 = 0.00999999999999979。

我告诉他有一个文件叫 IEEE754,可以解惑,他坚持让我说。于是我告诉他:double 数型有 64 个二进制位,其中第 1 位是表示正负符号的,第 2 至 12 位是表示带偏移的指数的,后 52 位是表示“小数”的。2.99 无法用二进制精确表示,所以才造成他看到的结果。这是 double 与生俱来的,不是 VB6 的 BUG。

2.不久,公司一位波兰女孩找我,说公司让她编的“四舍五入”函数会出现工作异常。

我看了代码,发现她所写的 round( r, n ) 函数,基本上等于是 floor( r*10^n + 0.5 ) / 10^n。这代码里也有 double 之二进制存储产生的问题。

例如,round(1.005, 2)=1.01。但是,1.005 不能用 double 精确表示,它的表示约为 1.0049999999999998。因此,以上代码计算的“r*10^2 + 0.5”约等于 100.999999999998,取整后为 100。结果,其代码给出的答案是 1.00,错了。

3.在做偏微分方程的迭代求解时,我发现迭代 N 次后的结果在 debug 模式与 release 模式下不一致。仔细分析代码,发现类似 1.0 + 0.25*DBL_EPSILON + 0.25*DBL_EPSILON 的计算式,在两种模式之下的计算结果分别为 1.0 与 1.0+DBL_EPSILON。原因在于后一种模式默认某种“优化”计算……不细说。

还有其他问题,很多都牵涉到 double 在计算机内部的二进制表示。了解 IEE754 的规定,才能够找到问题所在以及解决办法。这个知识点对 IT 高手不是问题,但相对入门级的新手很有用。

【用三进制证明( 0, 1 )中的实数不可数】

首先,把( 0, 1 )中的实数用三进制表示;其次,用反证法,假设( 0, 1 )中的实数是可数个。

由于是可数个数,因此可以将所有这些数写成数列 x(n)。

构造一个三进制小数 y:其第一位小数取数与 x(1)的第一位不同,且不取 2;从第二位小数开始,第 n 位取不同于 x(n)的第 n 位,且与 y 已经取得的前一位不同——例如,设 x(10)为 2,y 的第 9 位已经取 0,则 y 的第 10 位取 1。

不难证明,此 y 是( 0, 1 )中的实数,且不等于数列 x(n)中的任何一个。也就是说,数列 x(n)不可能包括全部( 0, 1 )中的实数。

这证明,( 0, 1 )中的实数是不可数个,也就是说:不可能把( 0, 1 )中的实数一一对应到自然数集上。

【康威十三进制数】

文不对题一下,我们只考虑使用十一进制,康威十三进制数留给好奇者去探索。

用 A 记 10,用十一进制表示所有( 0, 1 )中的实数。

在所有这些十一进制表示的( 0, 1 )中的实数里,考虑 A 仅出现有限次的那些数。对一个这种数 x,去掉其最后出现的 A 之前的所有数字,把 A 改成“0.”,则得到一个新的小数 y。把 y 解读为十进制小数,则我们构造了一个从( 0, 1 )到( 0, 1 )的映射。

关键是,这个映射中,( 0, 1 )内的每一个数都有无穷多个原像。也就是说( 0, 1 )可以映满( 0, 1 )无穷多次。

其实,( 0, 1 )可以映满( 0, 1 ) * ( 0, 1 )。证明怎么构造,这里先不说了……

总之,N 进制可以很好玩,可以很有用……

(作者:惊鹤闻风,南京大学数学系副教授)


举个栗子 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:举个栗子:N 进制这么好玩,你知道吗?
喜欢 (0)
举个栗子
关于作者:
建筑工地上施工员,闲暇时弄个博客打发时间,
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址