Computer Number System

十进制

From helloboyxxx
从我们最熟悉的十进制开始搞起
十进制,满十进一嘛
对10进制,从低位到高位,依次要乘以100,101,102,103……,也就是1、10、100、1000
对2进制,从低位到高位,依次要乘以20,21,22,23……,也就是1、2、4、8、……
原来十进制咱们的数位叫 千位、百位、十位……
现在二进制数位变成了八位、四位、二位……


十进制和二进制展开对比:
十进制的9876 =9×103+8×102+7×102+6×100
二进制的1011 =1×23+0×22+1×21+1×20=1×8+0×4+1×2+1×1=8+2+1=11

二进制

对于比较简单的二进制:
比如13,我们把数位摆好八位、四位、二位,不能写十六了,因为一旦“十六”那个数位上的符号是“1”,那就表示有1个16,即便后面数位上的符号全部是“0”,把这个二进制数按权位展开后,在按照十进制的运算规律计算,得到的数也大于13了。那最多就只能包含“八”这个数位。 13-8=5,5当中有4,5-4=1。
好啦,我们知道13=1×8+1×4+0×2+1×1 把“1”、“1”、“0”、“1”这几个符号放到数位上去:
八位、四位、二位、一位
  1 1 0 1
于是十进制数13=二进制数1101

十进制转二进制的方法very easy,把十进制转成二进制,只需要除二取余,倒序排列。
假设有一个二进制数1000,把它转成十进制也十分easy,只需要把它从个位开始分别20,21,以此类推。

十六进制在数学中是一种逢 16 进 1 的进位制。一般用数字 0 到 9 和字母 A 到 F(或 a~f)表示,其中: A~F 表示 10~15。拥有十六进制数的原因就是因为它能和四位的二进制形成一一对应的关系。
如下图所示👇👇👇
decimal to hexadecimal

Graph Theory

Overview

一个图看起来是由一些小圆点(称为顶点或结点)和连接这些圆点的直线或曲线(称为)组成的

图 G 是由两个集合 V 和 E 组成 (记做 G = (V, E)):
V = {v1,v2,v3,...vn,} 是由 G 的结点 (vertex or node) 组成的集合
E = {e1,e2,e3,...en} 是由连接两个结点的边 (edge) 组成的集合

graph theory example

比如说上图,V={A,B,C,D};E={AB.AC,CD}

术语

在图上任取两顶点,分别作为起点(start vertex)和终点(end vertex),我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线,就是一条路径。两点之间存在路径,则称这 2 个顶点是连通的(connected)。

在图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点 i 到顶点 j 有路径相连(当然从 j 到 i 也一定有路径),则称 i 和 j 是连通的。

循环(Cycle)是一条路径,第一个顶点和最后一个顶点是相同的图如HGEH就是一个Cycle。

我们将用V表示给定图中的顶点数,用E表示边数。注意,E的取值范围从V到V2(或无向图中的V(V-1)/2——等差数列求和)。具有所有边的图称为完全图;边缘相对较少的图(例如小于Vlog(V))称为稀疏图;缺边相对较少的图称为密集图。

树是指没有循环的图,树的任意两个节点之间只有一条边连接。所以一个有V个节点的树,必然有V-1个边。还是这张图👇👇👇,这张图就是一个树。
graph theory - tree

有向图

directed graph example
对于这幅图
V={A,B,C,D,E}
E={AB,AC,AE,CD,DE,ED,DB}
我们可以看到D指向了B,但是B没有指向D,DB的方向是从D指向B的。

邻接矩阵

我们可以用矩阵来表示这个图👇👇👇
adjacency matrix example

[0110100000000100100100010]\begin{bmatrix} 0 & 1 & 1 & 0 & 1\\ 0& 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}

原理是这样的:我们可以用1表示A,2表示B,3表示C……
所以矩阵第一行代表A,第二行代表B……
第一列代表A,第二列代表B……
由此类推矩阵第i行,第j列描述第i个元素与第j个元素的连接关系。
如果把邻接矩阵提升到p次方,那么该邻接矩阵的第i行,第j列的值n就代表了该图中p的距离为n个。

详细推导过程点此

遍历性

哥尼斯堡七桥问题
Knigsberg Bridge Problem
是否可从某处出发经过每个桥一次,然后再回到起点?
欧拉证明出来这个问题是一个无解的问题:
他证明只有当连接边数为奇数的点数量为0和2时这个图可以一笔连通。并且当奇数点数量为2时,必须2个点有1点做起点,另1点做终点。

看上图:
A有3条边连接
B有3条边连接
C有5条边连接
所以哥尼斯堡七桥问题无解

Problems

  1. Solve for x where x16=36768.

  2. Solve for x in the following hexadecimal equation: x=F5AD16−69EB16

  3. Find the number of different cycles contained in the directed graph with vertices {A, B, C, D, E} and edges {AB, BA, BC, CD, DC, DB, DE}.

  4. In the following directed graph, find the total number of different paths from vertex A to vertex C of length 2 or 4
    graph theory problem 4

  5. Given the adjacency matrix, draw the directed graph.
    graph theory problem 5


Solutions

  1. One method of solution is to convert 36768 into base 10, and then convert that number into base 16 to yield the value of x.
    An easier solution, less prone to arithmetic mistakes, is to convert from octal (base 8)to hexadecimal (base 16) through the binary (base 2) representation of the number:

36768=0111101111102=0111101111102=7BE16\begin{aligned} 3676_8 &= 011\; 110\; 111\; 110_2\\ &=0111\; 1011\; 1110_2\\ &=7BE_{16} \end{aligned}

  1. One could convert the hex numbers into base 10, perform the subtraction, and then convert the answer back to base 16. However, working directly in base 16 isn't too hard. As in conventional decimal arithmetic, one works from right-to-left, from the least significant digits to the most.


    The rightmost digit becomes 2, because D-B=2.
    The next column is A-E. We need to borrow a one from the 5 column, and 1A-E=C
    In the next column, 4-9=B, again, borrowing a 1 from the next column.
    Finally, the leftmost column, E-6=8


    Combining these results of each column, we get a final answer of 8BC216.

  2. The graph is as follows:
    graph theory solution 3
    By inspection, the cycles are: ABA, BCDB, and CDC. Thus, there are 3 cycles in the graph.

  3. Let matrix M represent the graph. Recall that the number of paths from vertex i to vertex j of length p equals Mp. The values of M, M2 and M4 are:
    graph theory solution 4
    There is 1 path of length 2 from A to C (cell [1,3]) and 3 paths of length 4 (cell [1,3]).

  4. There must be exactly 4 vertices: V = {A, B, C, D}. There must be be exactly 7 edges: E = {AB, AD, BA, BD, CA, DB, DC}. Here are two valid drawings of the graph:
    graph theory solution 5


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!