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

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进制可以很好玩,可以很有用……

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

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

栗子博客 日报 举个栗子:N进制这么好玩,你知道吗? https://www.lizi.tw/ribao/2161.html

建筑工地上施工员,闲暇时弄个博客打发时间,

常见问题
  • 1、杰齐1.7仅适用于PHP5.2 2、需Zend支持 3、尽量使用宝塔面板 4、尽量使用Windows 系统,关关对Linux支持不太友好。
查看详情

相关文章

评论
暂无评论
举个栗子:N进制这么好玩,你知道吗?-海报

分享本文封面