有限状态机(FSM)是一个根据输入改变状态的机器或程序。用图表示 FSM 相当简明， 下图中的矩形(或圆形)称为节点，节点之间带箭头的线段称为边(或弧)。
上图给出了一个简单的例子。每个节点代表一个程序状态，每个边代表从一个状态到另一个状态的转换。一个节点被指定为初始状态，在图中用一个输入箭头指出。其余的状态可以用数字或字母来标示。一个或多个状态可以指定为终止状态，用粗框矩形表示。终止状态表示程序无出错的结束状态。
FSM 是一种被称为有向图的更一般结构的特例。有向图就是一组节点，它们用具有特定方向的边进行连接。
验证输入字符串
读取输入流的程序往往要通过执行一定量的错误检查来验证它们的输入。比如，编程语言编译器可以用 FSM 来扫描程序，将文字和符号转换为记号(通常是指关键字、算法运算符和标识符)。
用 FSM 来验证输入字符串时，常常是按字符进行读取。每一个字符都用图中的一条边(转换)来表示。FSM 有两种方法检测非法输入序列：
下一个输入字符没有对应到当前状态的任何一个转换。
输入已经终止，但是当前状态是非终止状态。
字符串示例现在根据下面两条原则来验证一个输入字符串：
该字符串必须以字母“x”开始，以字母“z”结束。
第一个和最后一个字符之间可以有零个或多个字母，但其范围必须是 {a,....,y}。
下图的 FSM 显示了上述语法。每一个转换都是由特定类型的输入来标识。比如，仅当从输入流中读取字母 x 时，才能完成状态 A 到状态 B 的转换。输入任何非“z”的字母，都会使得状态 B 转换为其自身。而仅当从输入流中读取字母 z 时，才会发生状态 B 到状态 C 的转换。
如果输入流已经结束，而程序只出现了状态 A 和状态 B，那么就生成出错条件，因为只有状态 C 才能标记终止状态。下述输入字符串能被该 FSM 认可：
xaabcdefgz
xz
xyyqqrrstuvz
验证有符号整数
下图表示的是 FSM 解析一个有符号整数。输入包括一个可选的前置符号，其后跟一串数字。图中没有对数字个数进行限制。
有限状态机很容易转换为汇编代码。图中的每个状态(A、B、C…)代表了一段有标号的程序。每个标号执行的操作如下：
1) 调用输入程序读入下一个输入字符。
2)    如果是终止状态，则检查用户是否按下 Enter 键来结束输入。
3)    一个或多个比较指令检查从状态发岀的所有可能的转换。每个比较指令后面跟一个条件跳转指令。
比如，在状态 A，如下代码读取下一个输入字符并检查到状态 B 的可能的转换：
StateA:
Cal1 Getnext                          ;读取下一个字符，并送入 AL
cmp    al, '+'                        ;前置+ ?
je    StateB                          ;到状态 b
cmp    al, '-'                        ;前置 - ?
je    StateB                          ;到状态 B
call    IsDigit                       ;如果 AL 包含数字，则 ZF = 1
jz    StateC                          ;到状态 C
call    DisplayErrorMsg               ;发现非法输入
jmp Quit
下面来更详细地检查这段代码。首先，代码调用 Getnext，从控制台输入读取下一个字符，送入 AL 寄存器。接着检查前置 + 或 -，先将 AL 的值与符号“+”进行比较，如果匹配，就发生到标号 StateB 的跳转：
StateA:
call Getnext                         ;读取下一个字符，并送入 al
cmp al, ' + '                        ;前置 + ?
je StateB                            ;到状态 B
现在，再次查看上图，发现只有输入 + 或 - 时，才发生状态 A 到状态 B 的转换。所以，代码还需检查减号：
cmp al, '-'                                  ;前置 - ？
je StateB                                    ;到状态 B
如果无法发生到状态 B 的转换，就可以检查 AL 寄存器中是否为数字，这可以导致到状态 C 的转换。调用 IsDigit 子程序，当 AL 包含数字时，零标志位置 1：
call IsDigit                                 ;如果AL包含数字，贝U ZF=1
jz StateC                                    ;到状态 C
最后，状态 A 没有其他可能的转换。如果发现 AL 中的字符既不是前置符号，又不是数字，程序就会调用 DisplayErrorMsg (在控制台上显示一条错误消息)子程序，并跳转到标号 Quit 处：
call DisplayErrorMsg                         ;发现非法输入
jmp Quit
标号 Quit 标识程序的出口，位于主程序的结尾：
Quit:
call Crlf
exit
main ENDP
完整的有限状态机程序
如下程序实现上图所示的有符号整数 FSM：
; 有限状态机              (Finite.asm)
INCLUDE Irvine32.inc
ENTER_KEY = 13
.data
InvalidInputMsg BYTE "Invalid input",13,10,0
.code
main PROC
call Clrscr
StateA:
call    Getnext               ; 读取下一个字符，并送入AL
cmp    al,'+'                 ; 前置+ ?
je    StateB                  ; 到状态 B
cmp    al,'-'                 ; 前置 - ?
je    StateB                  ; 到状态 B
call    IsDigit               ; 如果 AL 包含数字 ，则 ZF = 1
jz    StateC                  ; 到状态 C
call    DisplayErrorMsg       ; 发现非法输入
jmp    Quit
StateB:
call    Getnext               ; 读取下一个字符，并送入AL
call    IsDigit               ; 如果AL包含数字，则 ZF = 1
jz    StateC
call    DisplayErrorMsg       ; 发现非法输入
jmp    Quit
StateC:
call    Getnext               ; 读取下一个字符，并送入AL
call    IsDigit               ; 如果AL包含数字，则 ZF = 1
jz    StateC
cmp    al,ENTER_KEY           ; 按下Enter键?
je    Quit                    ; 是：Quit
call    DisplayErrorMsg       ; 否: 发现非法输入
jmp    Quit
Quit:
call    Crlf
exit
main ENDP
;-----------------------------------------------
Getnext PROC
;
; 从标准输入读取一个字符
; 接收: 无
; 返回: 字符保存在AL中
;-----------------------------------------------
call ReadChar            ; 从键盘输入
call WriteChar           ; 显示在屏幕上
ret
Getnext ENDP
;-----------------------------------------------
DisplayErrorMsg PROC
;
; 显示一个错误消息以表示
; 输入流中包含非法输入
; 接收: 无.
; 返回: 无
;-----------------------------------------------
push  edx
mov      edx,OFFSET InvalidInputMsg
call  WriteString
pop      edx
ret
DisplayErrorMsg ENDP
END main
IsDigit子程序
有限状态机示例程序调用 IsDigit 子程序，该子程序属于本教程的链接库。现在来看看 IsDigit 的源程序，程序把 AL 寄存器作为输入，其返回值设置零标志位：
;----------------------------------------------------
IsDigit PROC
;
;确定 AL 中的字符是否为有效的十进制数字。
;接收：AL= 字符
;返回：若 AL 为有效的十进制字符，ZF=1;否则，ZF=0
;---------------------------------------------------
cmp    al,'0'
jb    ID1                                 ;跳转发生，ZF=0
cmp    al, '9'
ja    ID1                                 ;跳转发生，ZF = 0
test    ax, 0                             ;设置 ZF=1
ID1: ret
IsDigit ENDP
在查看 IsDigit 的代码之前，先回顾十进制数字的十六进制 ASCII 码，如下表所示。由于这些值是连续的，因此，只需要检查第一个和最后一个值：
字符
'0'
'1'
'2'
'3'
'4'
'5'
'6'
'7'
'8'
'9'
ASCII 码(十六进制)
30
31
32
33
34
35
36
37
38
39
IsDigit 子程序中，开始的两条指令将 AL 寄存器中字符的值与数字 0 的 ASCII 码进行比较。如果字符的 ASCII 码小于 0 的 ASCII 码，程序跳转到标号 ID1：
cmp al, '0'
jb ID1                       ;跳转发生，ZF=0
但是有人可能会问了，如果 JB 将控制传递给标号 ID1，那么，怎么知道零标志位的状态呢？答案就在 CMP 指令的执行方式里——它执行一个隐含的减法操作，从 AL 寄存器的字符中减去 0 的 ASCII 码(30h)。如果 AL 中的值较小，那么进位标志位置 1，零标志位清除(你可能想用调试器来单步执行这段代码来验证这个事实)。JB 指令的目的是，当 CF=1 且 ZF=0 时，将控制传递给一个标号。
接下来，IsDigit 子程序代码把 AL 与数字 9 的 ASCII 码进行比较。如果 AL 的值较大，代码跳转到同一个标号：
cmp al, '9'
ja ID1                ;跳转发生，ZF=0
如果 AL 中字符的 ASCII 码大于数字 9 的 ASCII 码(39h)，清除进位标志位和零标志位。这也正好是使得 JA 指令将控制传递到目的标号的标志位组合。
如果没有跳转发生(JA 或 JE)，又假设 AL 中的字符确实是一个数字，则插入一条指令确保将零标志位置 1。将 0 与任何数值进行 test 操作，就意味着执行一次隐含的与全 0 的 AND 运算。其结果必然为 0：
test ax, 0          ; 置 ZF=1
前面 IsDigit 中的 JA 和 JB 指令跳转到了 TEST 指令后面的标号。所以，如果发生跳转，零标志位将清零。下面再次给出完整的过程：
Isdigit PROC
cmp al,'0'
jb ID1             ;若跳转发生，则 ZF=0
cmp al,'9'
ja ID1             ;若跳转发生，则 ZF=0
test ax,0          ;置 zf=1
ID1: ret
Isdigit ENDP
在实时或高性能应用中，程序员常常利用硬件特性的优势，来对其代码进行充分优化。IsDigit 过程就是这种方法的例子，它利用 JB、JA 和 TEST 对标志的设置，实际上返回的是一个布尔结果。

二叉树结构

 


1.递归思想

大学时期对递归一直不是很清晰，其实大部分情况下能通循环最好就使用循环，因为递归不断调用函数会导致程序运行效率下降。递归的有点在简化思路，程序员只需要考虑当前步骤需要做什么，我的理解中递归的实现需要的是可重复的步骤以及递归的终止条件，在实际情况中，很多问题用循环实现会很难实现，简单的例子就是快速排序算法，使用递归思路很简单，而使用循环。。。那可能还需要一个栈的数据结构存放节点。 



前几天看到的找零问题就可以使用递归的思路，轻松解决问题。 

题目是这样的：


  
小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。 

  魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币 魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币 

  小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。


只看算法部分：



def Exchange(target):
    if target==0:
        return
    elif target%2:
        target=(target-1)/2
        Exchange(target)
        print(1)
    else:
        target=(target-2)/2
        Exchange(target)
        print(2)

只需要从最后一步开始，每一步向前推进一个步骤，函数只需要考虑当前步骤需要做的事情即可。



2.二叉树的定义


  
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。




二叉树的五种基本形态 

 1. 空二叉树 

 2. 只有一个根节点 

 3. 根节点只有左子树 

 4. 根节点只有右子树 

 5. 根节点既有左子树又有右子树



3.二叉树相关性质

 

 1. 在二叉树第i层上最多有2^(i-1)个节点。 

 2. 深度为k的二叉树最多有2^k-1个节点 

 3. 对于任何一个二叉树T，如果其终端节点数为n0，度为二的根节点数为n2则n0=n2+1 

 4. 具有n个节点的完全二叉树的深度为\log 2_n +1 


4.二叉树的遍历


 
前序遍历 

总是先查找根节点，之后查找左子树，最后查找右子树。(根左右) 

上图按照前序遍历应该为:ABDEC 

中序遍历 

总是先查找左子树，再查找根，最后查找右子树。(左根右) 

上图按照中序遍历就应该为:DBEAC 

后序遍历 

总是先查找左子树，再查找右子树，最后查找根节点。(左右根) 

上图按照后序遍历就应该为:DEBCA 


出了前序遍历和后序遍历的组合外，任意两个遍历方法值都能确定一个二叉树。 



5.建立二叉树

 

因为一种遍历方式的值并不能唯一确定一个二叉树，所以需要用两种遍历值来确定，当然还有一种更简单的方法,空出来的节点用一个特殊字符表示，这里选择用’#’来表示空的节点。上图进行变换后应该如下图所示。 


此时如果采用前序遍历那么结果应该是:ABD##E##C##,此时该二叉树是唯一确定的。 
 
 
采用前序遍历的结果作为生成二叉树的依据。 

**构建时采用递归思路，每一个步骤都是写入根节点，开辟左节点内存，右节点内存，进入左节点，进入右节点。 

终止条件是：当该节点的值为’#’时，写入根节点，不再开辟左右几点内存，返回** 


C/C++实现如下:



//节点类
class TreeNode
{
public:
    int date;
    TreeNode*LeftChild;
    TreeNode*RightChild;
};

二叉树类型：



class BiTree
{
public:
    TreeNode*Root;
    void CreateTree(TreeNode**ptr,int *s);
    int Deepth(TreeNode*ptr);
    BiTree(int*s);//构造函数 使用int数组来构造树
    int GetDeepth();//获得二叉树的深度
};

这里为了后面的搜索二叉树，存放的不再是字符(char类型)而换成了(int类型)，-1代表空，也就是说将’#’换成-1。 
 

构造方法： 


BiTree::BiTree(int*s)
{
    Root = new TreeNode;
    CreateTree(&Root,s);
}

void BiTree::CreateTree(TreeNode**ptr, int*s)
{
    static int index = 0;
    if (s[index] == -1)
    {
        (*ptr)->date = -1;
        (*ptr)->LeftChild = NULL;
        (*ptr)->RightChild = NULL;
        index++;
    }
    else
    {//根左右的前序遍历方法
        (*ptr)->LeftChild = new TreeNode;
        (*ptr)->RightChild = new TreeNode;
        (*ptr)->date = s[index++];
        CreateTree(&(*ptr)->LeftChild, s);
        CreateTree(&(*ptr)->RightChild, s);
    }
}

该构造函数需要输入的int数组是正确符合前序遍历的，否则可能出现数组越界问题。

 

获取二叉树深度 




int BiTree::GetDeepth()
{
    return Deepth(Root);
}

int BiTree::Deepth(TreeNode*ptr)
{
    if (ptr->date == -1)
    {
        return 0;
    }
    int nLeft = Deepth(ptr->LeftChild);
    int nRight = Deepth(ptr->RightChild);
    return nLeft > nRight ? nLeft + 1 : nRight + 1;
}