为什么二进制数能表示所有整数 |
您所在的位置:网站首页 › 十进制整数有什么 › 为什么二进制数能表示所有整数 |
1. 一个显而易见的问题: 为什么二进制数(仅考虑无符号数)与正整数一一对应? 二进制和整数间的相互转换算法说明每个二进制串对应一个整数,同样每个整数都对应一个二进制串。但不能说明不同二进制串对应不同整数,即,任两个不同的二进制串是不等的。这个问题有一个很简单的证明方法: 假设有两个二进制串a1,a2,它们的最高位分别为k1, k2(最高位不为0)。如果这两个二进制串相等则它们的最高位相等(k1=k2)。 反证:假设 k1 > k2, 则有: 不过此时每个整数有多种表示。如果对整数的Fibonacci数表示加如下限制,则每个数有唯一表示: Fibonacci数的下标大于1。不能取连续的Fibonacci数。这样17只有17 = 13 + 3 + 1这一种表示。上述整数的Fibonacci表示法被称为Zeckendorf's theorem。 2. 完全数列如果去掉唯一表示这个条件,什么样的数列可以表示所有正整数呢? 1961年,John L.Brown.Jr提出了如下判定法则(Brown's Criterion): 一个非递减的正整数序列,若第一项的值为1,且任意一项的值都不大于它前面所有项的和加1,则这个序列是完全的(complete)。即可表示所有整数。形式化的表示为,一个数列{vi}是完全的,当: v1 = 1for all k = 2, 3, …… 这个法则的一个推论是:任一首项为1,每项都不大于它前一项两倍的数列是也完全的。显然,二进制和Fibonacci数列满足该条件。 比较有意思的是,如果把1添加到质数数列的第一项,构成数列(1, 2, 3, 5, 7, 13, ……),那么该数列也是完全的。 对任一完全数列{vi},任意正整数可以表示为该数列的一个二进制串形式,数列的值为二进制相应位的权重。即,对正整数n有: 参考文献Zeckendorf's theoremBWeisstein, Eric W. "Brown's Criterion." From MathWorld--A Wolfram Web Resource.Weisstein, Eric W. "Complete Sequence." From MathWorld--A Wolfram Web Resource. |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |