你在这里

N进制漫谈

成长吧啊,数学,成长吧啊,www.czbaa.com,数学

【按:几个有趣的N进制小游戏,您准备好了吗?卡片魔术背后的数学、数学家抓编程bug、有限区间内实数数目不可数的巧妙证明,本文作者将告诉您,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进制可以很好玩,可以很有用……

http://www.scipark.net/archives/16993