2015年 9月21日 总结

2015年9月21日  格雷码的心得

格雷码的特点：
格雷码属于可靠性编码，是一种错误最小化的编码方式。因为，虽然自然二进制码可以直接由数/模转换器转换成模拟信号，但在某些情况，例如从十进制的3转换为4时二进制码的每一位都要变，能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它在相邻位间转换时，只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同，因而在用于方向的转角位移量－数字量的转换中，当方向的转角位移量发生微小变化（而可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠，即可减少出错的可能性。
格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
由于格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算，也不能直接转换成液位信号，要经过一次码变换，变成自然二进制码，再由上位机读取。
典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为2^i-1(设最低位i=1)。
格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。

异或转换

二进制码→格雷码（编码）：

此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：

1. 对n位二进制的码字，从右到左，以0到n-1编号
2. 如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）[3]

公式表示：

  

（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。

0 xor 0=0，所以g3=0

0 xor 1=1，所以g2=1

1 xor 0=1，所以g1=1

0 xor 1=1，所以g0=1

因此所转换为之格雷码为0111

格雷码→二进制码（解码）：

从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

公式表示：

  

（G：格雷码，B：二进制码）

原码：p[n:0]；格雷码：c[n:0](n∈N）；编码：c=G(p）；解码：p=F(c）；

书写时按从左向右标号依次减小，即MSB->LSB，编解码也按此顺序进行

举例：

如果采集器器采到了格雷码：1010

就要将它变为自然二进制：

0 与第四位 1 进行异或结果为 1

上面结果1与第三位0异或结果为 1

上面结果1与第二位1异或结果为 0

上面结果0与第一位0异或结果为 0

因此最终结果为：1100 这就是二进制码即十进制 12

当然人看时只需对照表1一下子就知道是12

...................c[n]=p[n]，

解码：

利用卡诺图

利用卡诺图相邻两格只有一位变化以及卡诺图的变量取值以低阶格雷码的顺序排布的特征，可以递归得到高阶格雷码。由于此方法相对繁琐，使用较少。生成格雷码的步骤如下：

1. 将卡诺图变量分为两组，变量数目相近（最好相等）
2. 以逻辑变量高位在左低位在右建立卡诺图
3. 从卡诺图的左上角以之字形到右上角最后到左下角遍历卡诺图，依次经过格子的变量取值即为典型格雷码的顺序

三位格雷码（三位格雷码由建立在二位基础上）

AB╲ C	0	1
00	0→	1↓
01	↓2	←3
11	6→	7↓
10	4	←5

格雷码次序：000起点→001→011→010→110→111→101→100终点

四位格雷码

AB╲CD	00	01	11	10
00	0→	1→	3→	2↓
01	↓4	←5	←7	←6
11	12→	13→	15→	14↓
10	8	←9	←11	←10

格雷码次序：0000起点→0001→0011→0010→0110→0111→0101→0100→1100→1101→

1111→1110→1010→1011→1001→1000终点

使用异或乘除

用异或代替加减进行二进制竖式乘除，称为异或乘除，它的特点是无进退位。

如：10101除以11将变成1100余1。

二进制转格雷码：

只要异或乘以二分之三，即二进制的1.1，然后忽略小数部分；也可以理解成异或乘以三（即11），再右移一位。

格雷码转二进制：

异或除以三分之二，即除以1.1，忽略余数；或者左移一位，再异或除以三，忽略余数。

关于Gray码Google的面试题目（运用递归的思想来解决）：http://blog.csdn.net/beiyeqingteng/article/details/7044471

Python中的random模块用于生成随机数。下面介绍一下random模块中最常用的几个函数。

random.random

random.random()用于生成一个0到1的随机符点数: 0 <= n < 1.0

random.uniform

　　random.uniform的函数原型为：random.uniform(a, b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。如果a > b，则生成的随机数n: a <= n <= b。如果 a <b， 则 b <= n <= a。

printrandom.uniform(10,20)
printrandom.uniform(20,10)
#----结果（不同机器上的结果不一样）
#18.7356606526
#12.5798298022

print random.uniform(10, 20) print random.uniform(20, 10) #---- 结果（不同机器上的结果不一样） #18.7356606526 #12.5798298022

random.randint

　　random.randint()的函数原型为：random.randint(a, b)，用于生成一个指定范围内的整数。其中参数a是下限，参数b是上限，生成的随机数n: a <= n <= b

printrandom.randint(12,20)#生成的随机数n:12<=n<=20
printrandom.randint(20,20)#结果永远是20
#printrandom.randint(20,10)#该语句是错误的。下限必须小于上限。

print random.randint(12, 20) #生成的随机数n: 12 <= n <= 20 print random.randint(20, 20) #结果永远是20 #print random.randint(20, 10) #该语句是错误的。下限必须小于上限。

random.randrange

　　random.randrange的函数原型为：random.randrange([start], stop[, step])，从指定范围内，按指定基数递增的集合中 获取一个随机数。如：random.randrange(10, 100, 2)，结果相当于从[10, 12, 14, 16, ... 96, 98]序列中获取一个随机数。random.randrange(10, 100, 2)在结果上与 random.choice(range(10, 100, 2) 等效。

random.choice

　　random.choice从序列中获取一个随机元素。其函数原型为：random.choice(sequence)。参数sequence表示一个有序类型。这里要说明一下：sequence在python不是一种特定的类型，而是泛指一系列的类型。list, tuple, 字符串都属于sequence。有关sequence可以查看python手册数据模型这一章。下面是使用choice的一些例子：

printrandom.choice("学习Python")
printrandom.choice(["JGood","is","a","handsome","boy"])
printrandom.choice(("Tuple","List","Dict"))

print random.choice("学习Python") print random.choice(["JGood", "is", "a", "handsome", "boy"]) print random.choice(("Tuple", "List", "Dict"))

random.shuffle

　　random.shuffle的函数原型为：random.shuffle(x[, random])，用于将一个列表中的元素打乱。如:

p=["Python","is","powerful","simple","andsoon..."]
random.shuffle(p)
printp
#----结果（不同机器上的结果可能不一样。）
#['powerful','simple','is','Python','andsoon...']

p = ["Python", "is", "powerful", "simple", "and so on..."] random.shuffle(p) print p #---- 结果（不同机器上的结果可能不一样。） #['powerful', 'simple', 'is', 'Python', 'and so on...']

random.sample

　　random.sample的函数原型为：random.sample(sequence, k)，从指定序列中随机获取指定长度的片断。sample函数不会修改原有序列。

list=[1,2,3,4,5,6,7,8,9,10]
slice=random.sample(list,5)#从list中随机获取5个元素，作为一个片断返回
printslice
printlist#原有序列并没有改变。

随机整数：
>>> import random
>>> random.randint(0,99)
21

随机选取0到100间的偶数：
>>> import random
>>> random.randrange(0, 101, 2)
42

随机浮点数：
>>> import random
>>> random.random()
0.85415370477785668
>>> random.uniform(1, 10)
5.4221167969800881

随机字符：
>>> import random
>>> random.choice('abcdefg&#%^*f')
'd'

多个字符中选取特定数量的字符：
>>> import random
random.sample('abcdefghij',3)
['a', 'd', 'b']

多个字符中选取特定数量的字符组成新字符串：
>>> import random
>>> import string
>>> string.join(random.sample(['a','b','c','d','e','f','g','h','i','j'], 3)).r
eplace(" ","")
'fih'

随机选取字符串：
>>> import random
>>> random.choice ( ['apple', 'pear', 'peach', 'orange', 'lemon'] )
'lemon'

洗牌：
>>> import random
>>> items = [1, 2, 3, 4, 5, 6]
>>> random.shuffle(items)
>>> items
[3, 2, 5, 6, 4, 1]

关系型数据库简介

　　关系型数据库以行和列的形式存储数据，以便于用户理解。这一系列的行和列被称为表，一组表组成了数据库。用户用查询(Query)来检索数据库中的数据。一个Query是一个用于指定数据库中行和列的SELECT语句。关系型数据库通常包含下列组件：
　　客户端应用程序(Client)
　　数据库服务器(Server)
　　数据库(Database)
Structured Query Language(SQL)Client端和Server端的桥梁，Client用SQL来象Server端发送请求，Server返回Client端要求的结果。现在流行的大型关系型数据库有IBM DB2、IBM UDB、Oracle、SQL Server、SyBase、Informix等。
关系型数据库并不是唯一的高级数据库模型，也完全不是性能最优的模型，但是关系型数据库确实是现今使用最广泛、最容易理解和使用的数据库模型。大多数的企业级系统数据库都采用关系型数据库，关系型数据库的概念是掌握数据库开发的基础，所以本节的问题也成为.NET面试中频繁出现的问题之一。
所涉及的知识点
关系型数据库的概念
关系型数据库的优点分析问题关系型数据库的概念
所谓关系型数据库，是指采用了关系模型来组织数据的数据库。关系模型是在1970年由IBM的研究员E.F.Codd博士首先提出，在之后的几十年中，关系模型的概念得到了充分的发展并逐渐成为数据库架构的主流模型。简单来说，关系模型指的就是二维表格模型，而一个关系型数据库就是由二维表及其之间的联系组成的一个数据组织。下面列出了关系模型中的常用概念。
关系：可以理解为一张二维表，每个关系都具有一个关系名，就是通常说的表名。
元组：可以理解为二维表中的一行，在数据库中经常被称为记录。
属性：可以理解为二维表中的一列，在数据库中经常被称为字段。
域：属性的取值范围，也就是数据库中某一列的取值限制。
关键字：一组可以唯一标识元组的属性。数据库中常称为主键，由一个或多个列组成。
关系模式：指对关系的描述，其格式为：关系名（属性1，属性2，…，属性N）。在数据库中通常称为表结构。
关系型数据库的优点
关系型数据库相比其他模型的数据库而言，有着以下优点：
容易理解：二维表结构是非常贴近逻辑世界的一个概念，关系模型相对网状、层次等其他模型来说更容易理解。
使用方便：通用的SQL语言使得操作关系型数据库非常方便，程序员甚至于数据管理员可以方便地在逻辑层面操作数据库，而完全不必理解其底层实现。
易于维护：丰富的完整性（实体完整性、参照完整性和用户定义的完整性）大大降低了数据冗余和数据不一致的概率。
近几年来，非关系型数据库在理论上得到了飞快的发展，例如：网状模型、对象模型、半结构化模型等。网状模型拥有性能较高的优点，通常应用在对性能要求较高的系统中；对象模型符合面向对象应用程序的思想，可以完美地和程序衔接，而不需要另外的中间转换组件，例如现在很多的O\R Mapping组件；半结构化模型随着XML的发展而得到发展，现在已经有了很多半结构化的数据库模型。但是，凭借其理论的成熟、使用的便捷以及现有应用的广泛，关系型数据库仍然是系统应用中的主流方案。