PYTHON第三次实验

实验3.1 设计和实现尼姆游戏(人机对战)

一、实验目的

• 理解尼姆游戏规则
• 了解多个函数的定义与调用
• 理解并熟练运行while循环
• 理解带else子句的循环结构执行流程
• 理解循环语句的break语句的作用
• 了解使用循环和异常处理结构对用户输入进行约束的用法
• 养成时刻注意各级代码缩进级别的习惯

二、实验内容

​ 尼姆游戏是一个著名的游戏，有很多变种玩法。两个玩家轮流从一堆物品中拿走一部分。在每一步中，玩家可以自由选择拿走多少物品，但是必须至少拿走一个并且最多只能拿走一半物品，然后轮到下一个玩家。拿走最后一个物品的玩家输掉游戏。

​ 在聪明模式中，计算机每次拿走一定数量的物品使得堆的大小是2的幂次方减1—也就是2，7，15，31，63等。如果有一定数量的剩余物品，计算就随机拿走一些。

​ 编写程序，模拟聪明版及非聪明版的尼姆游戏。并进行两种的比较及分析。给出聪明版比非聪明版的胜算结论。

三、实验步骤

（1）需要知道的函数以及用法

计算对数函数：math库中的log2(), log()函数等

python中的while else 语句的详细用法：

(45条消息) python中while。。。。else的用法_慕云-CSDN博客_python中while和else

以及try except语句的用法：

(45条消息) Python之异常（try的用法）_蓝七star的博客-CSDN博客_python try

assert断言函数的使用：

(45条消息) Python assert 断言函数_hunyxv的博客-CSDN博客_assert函数python

（2）代码设计思路

首先是先选择游戏模式，1为普通模式，2为聪明模式

普通模式和聪明模式的过程差不多，只是在电脑取数时会有不同

普通模式下，电脑随机选择处于[1, n//2]之间的数

def computer_getnormal(n):
    a = random.randint(1, int(n / 2))
    return a

聪明模式下，电脑尽可能选择能使剩下的数为2的幂次减1的数，也就是尽可能地使剩下的数为2，7，15，31，63等

def getnum(n):
    a = int(math.log2(n))
    target = pow(2, a) - 1
    get = n - target
    return get

def computer_getsmart(n):
    a=getnum(n)
    if a>int(n/2):
        a=random.randint(1,int(n/2))
    return a

（3）总代码

import math
import random

def getnum(n):
    a = int(math.log2(n))
    target = pow(2, a) - 1
    get = n - target
    return get

def computer_getsmart(n):
    a=getnum(n)
    if a>int(n/2):
        a=random.randint(1,int(n/2))
    return a

def computer_getnormal(n):
    a = random.randint(1, int(n / 2))
    return a

def compusmart():
    n = random.randint(1, 100)
    while n>1:
        print('现在有{}个物品'.format(n))
        #from here
        while True:
            try:
                person=int(input("请你输入你要拿走的物件个数："))
                assert 1<=person<=n//2
                break
            except:
                print("请输入1到{}的数".format(n//2))
        #till here
        n = n - person
        if n==1:
            print('你赢啦！')
            break
        else:
            computernum=computer_getsmart(n)
            print('电脑取走{}个物品'.format(computernum))
            n=n-computernum
        print('现在还有{}个物品'.format(n))
    else:
        print('你输啦！')

def compunormal():
    n = random.randint(1, 100)
    while n>1:
        print('现在有{}个物品'.format(n))
        # from here
        while True:
            try:
                person = int(input("请你输入你要拿走的物件个数："))
                assert 1 <= person <= n // 2
                break
            except:
                print("请输入1到{}的数".format(n // 2))
        # till here
        n = n - person
        if n==1:
            print('你赢啦！')
            break
        else:
            computernum=computer_getnormal(n)
            print('电脑取走{}个物品'.format(computernum))
            n=n-computernum
        print('现在还有{}个物品'.format(n))
    else:
        print('你输啦！')


choice = int(input('1是普通模式，2是聪明模式，请选择游戏模式：'))
if choice == 1:
    print('-------------------普通模式---------------------')
    compunormal()
else:
    print('-------------------聪明模式---------------------')
    compusmart()

---

实验3.2 计算小明爬楼梯的爬法数量

一、 实验目的

• 理解并熟练使用序列解包
• 理解递归函数的工作原理
• 能够编写递归函数代码解决实际问题
• 理解Python字典的用法
• 养成检查和测试循环结构边界条件的习惯
• 养成时刻注意各级代码缩进级别的习惯

二、 实验内容

假设15个台阶，小明一步最多能上3个台阶。编写程序计算小明上这段楼梯一共有多少种方法。要求给出递推法和递归法两种实现代码。

F(n) = F(n-1) + F(n-2) + F(n-3)

F(1) = 1

F(2) = 2

F(3) = 4

三、实验步骤

递推：数学上的概念，主要指递推式、递推数列或递推函数。一个数列的下一项由它前面几项的一种运算（或函数）构成，如 a [ n ] = a [ n − 1 ] + a [ n − 2 ] a[n]=a[n-1]+a[n-2]a[n]=a[n−1]+a[n−2]。
递归：计算机中的概念，主要指计算机上的递归函数，（计算机中的‘函数’不同于数学上的‘函数’，这里指一段代码），即指会调用自己的函数。

def ditui(n):
    a,b,c=1,2,4#预先设置好前三个台阶的走法
    for i in range(n-3):
        temp1,temp2,temp3=a,b,c
        a=temp2
        b=temp3
        c=temp1+temp2+temp3
    return c


def digui(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    elif n==3:
        return 4
    else:
        return digui(n-1)+digui(n-2)+digui(n-3)


n=int(input('请输入一个数：'))
result1=ditui(n)
result2=digui(n)

print('递推的结果为：{}'.format(result1))
print('递归的结果为：{}'.format(result2))

实验3 语义分析

实验目的

1．   巩固对语义分析的基本功能和原理的认识。

2．   能够基于语法指导翻译的知识进行语义分析。

3．   掌握类高级语言中基本语句所对应的语义动作。

4．   理解并处理语义分析中的异常和错误。

实验内容

在语法分析器的基础上设计实现类高级语言的语义分析器，基本功能如下：

（1）    能分析以下几类语句，并生成中间代码（三地址指令和四元式形式）：

Ø 声明语句（包括变量声明、数组声明、记录声明和过程声明）

Ø 表达式及赋值语句（包括数组元素的引用和赋值）

Ø 分支语句：if_then_else

Ø 循环语句：do_while

Ø 过程调用语句

（2）具备语义错误处理能力，包括变量或函数重复声明、变量或函数引用前未声明、运算符和运算分量之间的类型不匹配（如整型变量与数组变量相加减）等错误，能准确给出错误所在位置，并采用可行的错误恢复策略。输出的错误提示信息格式如下：

Error at Line [行号]：[说明文字]

（3）系统的输入形式：要求能够通过文件导入测试用例。测试用例要涵盖第（1）条中列出的各种类型的语句，以及第（2）条中列出的各种类型的错误。

（4）系统的输出分为两部分：一部分是打印输出符号表。另一部分是打印输出三地址指令和四元式序列，格式如下图所示（以输入语句“while a<b do if c<d then x=y+z else x=y-z”为例）：

 

1  : (j<, a , b ,  3 )               if a < b  goto 3

2  : (  j , - ,  - , 11)           goto 11

3  : (j<,  c , d , 5 )               if c < d  goto 5

4  :(  j ,  - ,  -, 8 )         goto8

5  :( + ,  y , z ,  t₁)            t₁ = y + z

6  :( = , t₁ ,  - ,  x )          x= t₁

7  : (  j , - ,  - ,  1 )        goto1

8  : (  - ,  y, z ,  t₂)        t₂ = y - z

9  : (= ,  t₂ ,  - , x )           x = t₂

10 : ( j  ,   -,  - , 1 )          goto 1

11:

 

除此之外，可以实现一些额外功能，例如自动类型转换，识别其它类型语义错误，如过程返回类型与声明类型不匹配；过程调用时实参与形参数目或类型不匹配；对非数组型变量使用数组访问操作符“[…]”；对普通变量使用过程调用操作符“call”；数组访问操作符“[…]”中出现非整数等。

圈重点！！！

实验指导书：http://download.csdn.net/download/qq_32285991/10125108

源代码：https://github.com/JiayanFighting/SemanticAnalysis

1. 概述

本文使用wireshark捕获客户端（10.240.89.99） 向服务端（ 47.95.47.253）请求页面http://blog.csdn.net/hry2015/过程中的包。先介绍TCP的三次握手协议，数据传送过程以及四次挥手协议，然后结合捕获的包学习这些协议

需要注意的是，文章接下来的部分依然使用相对序列号/确认号

2. 三次握手协议

2.1. 理论

客户端和服务端是通过三次握手协议建立TCP会话连接。建立连接的理论图如下：

第一次握手：建立连接时，客户端发送SYN到服务器，并进入SYN_SENT状态
第二次握手：服务器收到请求后，回送SYN+ACK信令到客户端，此时服务器进入SYN_RECV状态；
第三次握手：客户端收到SYN+ACK包，向服务器发送确认ACK包，客户端进入ESTABLISHED状态，服务器收到请求后也进入ESTABLISHED状态，完成三次握手，此时TCP连接成功，客户端与服务器开始传送数据

下面结合抓包学习三次握手
客户端（10.240.89.99） 向服务端（ 47.95.47.253）建立连接3个包如下：

下面介绍每个包详细信息。

2.2. 第一次握手

第一次握手：建立连接时，客户端发送SYN到服务器，并进入SYN_SENT状态
数据包一些关键的属性如下：

SYN ：标志位，表示请求建立连接
Seq = 0 ：初始建立连接值为0，数据包的相对序列号从0开始，表示当前还没有发送数据
Ack =0：初始建立连接值为0，已经收到包的数量，表示当前没有接收到数据
WIN = 8192 来自Window size: 8192
Len = 0
MSS = 1460 来自 Maximum segment size: 1460 byte ，最长报文段，TCP包所能携带的最大数据量，不包含TCP头和Option。一般为MTU值减去IPv4头部(至少20字节)和TCP头部(至少20字节)得到
WS = 4 来自windows scale : 2 (multiply by 4)： 窗口扩张，放在TCP头之外的Option，向对方声明一个shift count，作为2的指数，再乘以TCP定义的接收窗口，得到真正的TCP窗口
SACK_PERM = 1 来自SACK permitted

2.3. 第二次握手

第二次握手：服务器收到请求后，回送SYN+ACK信令到客户端，此时服务器进入SYN_RECV状态；

数据包一些关键的属性如下：

[SYN + ACK]: 标志位，同意建立连接，并回送SYN+ACK
Seq = 0 ：初始建立值为0，表示当前还没有发送数据
Ack = 1 : 表示当前端成功接收的数据位数，虽然客户端没有发送任何有效数据，确认号还是被加1，因为包含SYN或FIN标志位。尽管客户端没有发送任何有效数据，确认号还是被加1，这是因为接收的包中包含SYN或FIN标志位（并不会对有效数据的计数产生影响，因为含有SYN或FIN标志位的包并不携带有效数据
其它标志和第一包相同，略

2.4. 第三次握手

第三次握手：客户端收到SYN+ACK包，向服务器发送确认ACK包，客户端进入ESTABLISHED状态，服务器收到请求后也进入ESTABLISHED状态，完成三次握手，此时TCP连接成功，客户端与服务器开始传送数据。

数据包一些关键的属性如下：

ACK ：标志位，表示已经收到记录
Seq = 1 ：表示当前已经发送1个数据
Ack = 1 : 表示当前端成功接收的数据位数，虽然客户端没有发送任何有效数据，确认号还是被加1，因为包含SYN或FIN标志位。尽管客户端没有发送任何有效数据，确认号还是被加1，这是因为接收的包中包含SYN或FIN标志位（并不会对有效数据的计数产生影响，因为含有SYN或FIN标志位的包并不携带有效数据)

2.5. TCP建立连接为什么是三次握手

这个问题的本质是, 信道不可靠, 但是通信双发需要就某个问题达成一致. 而要解决这个问题, 无论你在消息中包含什么信息, 三次通信是理论上的最小值. 所以三次握手不是TCP本身的要求, 而是为了满足”在不可靠信道上可靠地传输信息”这一需求所导致的.

也是为了最小的代价验证会话双方的收发功能正常:

• 第一次握手成功：说明客户端的数据可以被服务端收到，说明客户端的发功能可用，说明服务端的收功能可用。但客户端自己不知道数据是否被接收
• 第二次握手成功：说明服务端的数据可以被客户端收到，说明服务端的发功能可用，说明客户端的收功能可用。同时客户端知道自己的数据已经正确到达服务端，自己的发功能正常。但是服务端自己不知道数据是否被接收
• 第三次握手成功：说明服务端知道自己的数据已经正确到达客户端端，自己的发功能正常。至此服务成功建立

3. 客户端和服务端数据交互的过程

客户端和服务端建立连接后，开始传送数据。下面对以下场景的交互包进行分析：
客户端（10.240.89.99） 和服务端（ 47.95.47.253）建立连接后，客户端向服务端传送要访问页面的信息，服务端完全接收请求后进行处理，然后服务端返回数据给服务端客户端， 客户端对收到的数据进行的确认，最后完成操作。
全部的包如下：

简化之后的数据如下：

下面结合包，详细说明传输过程中seq, ack，len的变化

3.1. 客户端（10.240.89.99）向服务端发送请求，服务端对收到数据进行确认

客户端（10.240.89.99）向服务端发送请求

包内关键信息如下：

Seq = 1 ：表示当前已经发送1个数据
Next Sequence number：在完成这次的发送后，当发送新的数据时，Seq从2167开始编码
Ack = 1 : 表示当前端成功接收的1个数据位数
TCP playload：Hypertext Transfer Protocol 部分的数据量，本次传送的数据量为2166 byte

服务端（47.95.47.253）接受发送过来的2166个字节数据，在接收请求过程中，发送两次ACK包
第一次发送ACK包

Seq: 1
Ack: 1449: 说明现在共收到1449字节数据

第二次发送ACK包

Seq: 1
Ack: 2167: 说明现在共收到2167字节数据，说明我们已经接收到全部的数据。

3.2. 服务端（47.95.47.253）向对方推送数据，在发送的过程中，服务端（10.240.89.99）同时接收数据并向发送方发送确认的消息

由于服务端向客户端发送14117字节数据，已经知道测试网络Ethernet II 帧一次最大负载值为1502，再加上分析包我们发现每个包最大的数据负载为1448字节，所有此数据被拆分成10个TCP包进行发送。客户端采用延迟确信，平均收到2个数据包发送一个确认包

这里先分析第一组里数据，即第一个框3个包的信息
服务端（47.95.47.253）第一次推送记录：1448字节的数据

ACK
Seq = 1
# Next Sequence number：在完成这次的发送后，当发送新的数据时，Seq从1449开始编码
Ack = 2167

服务端（47.95.47.253）第二次推送记录：1448字节的数据

ACK
Seq = 1449
Next Sequence number：在完成这次的发送后，当发送新的数据时，Seq从2897开始编码
Ack = 2167

客户端（10.240.89.99）第一次对收到的数据进行确认

ACK
Seq = 2167
Ack = 2897：已经收到 2896（2897-1）个字节数据

后面还有四次类似操作。虽然最后一次显示的是http(实质也是tcp）但和之前的交互实质是相同的，最后一次推送的数据大小是1139。后面的包就不一一说明。

显示为http的协议的包特殊说明：
和之前tcp包，不同的是有个特殊字段“[10 Reassembled TCP Segmetns （14117 bytes): ….] ”：此字段表明从#254(1448)到 #267(1085)共10个数据包组成一个完整http内容，也说明这次的HTTP的请求的内容被拆分为10个包给客户端

4. 四次挥手：关闭TCP连接

客户端和服务端交互数据完毕后，开始通过四次挥手结束TCP会话连接。

4.1. 理论

1. 第一次挥手：客户端 发送一个[FIN+ACK]，表示自己没有数据要发送了，想断开连接，并进入FIN_WAIT_1状态（不能再发送数据到服务端，但能够发送控制信息ACK到服务端）。
2. 第二次挥手：服务端收到FIN后，知道不会再有数据从客户端传来，发送ACK进行确认，确认序号为收到序号+1（与SYN相同，一个FIN占用一个序号），服务端进入CLOSE_WAIT状态。
3. 第三次挥手：服务端发送FIN给对方，表示自己没有数据要发送了，服务端进入LAST_ACK状态，然后直接断开TCP会话的连接，释放相应的资源。
4. 第四次挥手：客户端收到了服务端对FIN的ACK后，进入FIN_WAIT2状态（等待服务端完成资源释放的一系列工作：然后释放你为创建这个连接所分配的资源，并通知我你关闭了）; 客户端收到了服务端的FIN信令后，进入TIMED_WAIT状态，并发送ACK确认消息。客户端在TIMED_WAIT状态下，等待2MSL一段时间，没有数据到来的，就认为对面已经收到了自己发送的ACK并正确关闭了进入CLOSE状态，自己也断开了到服务端的TCP连接，释放所有资源。当服务端收到客户端的ACK回应后，会进入CLOSE状态，并关闭本端的会话接口，释放相应资源。

TIME_WAIT状态持续2MSL(MSL是数据分节在网络中存活的最长时间）

网络上比较主流的文章都说关闭TCP会话是四次挥手，但是实际上为了提高效率通常合并第二、三次的挥手，即三次挥手。下方中的抓包也证明了这一点

4.2. 为什么需要四次挥手协议

TCP协议是一种面向连接的、可靠的、基于字节流的传输层通信协议。TCP是全双工模式，需要两边的连接全部关闭，此TCP会话才算完全关闭，四次挥手使得TCP的全双工连接能够可靠的终止。另外TIMED_WAIT也使得连接终止后网络上残余的发送给该连接的数据被丢弃而不至于被新连接接收.

下面根据客户端（10.240.89.99) 向 服务端（47.95.47.253) 发起关闭连接请求的抓包进行学习挥手协议

4.3. 第一次握手

第一次握手 客户端（10.240.80.99) 发送ACK ，通过FIN通知对方关闭连接

包关键属性如下：

ACK + FIN ： 标志位
seq = 2167 ：已经发送的数据字节
Ack = 14118 ：已经收到的数据字节+SYN包

4.4. 第二、三次握手

第二、三次握手：服务端（47.95.47.253)关闭的连接，通过FIN通知对方关闭连接

包关键属性如下：

ACK + FIN ： 标志位
Seq = 14118：已经发送的数据字节
Ack = 2168 ：已经收到的数据字节+SYN包+ FIN包,Ack = 原Ack + 1, SYN标志位和FIN标志位也要占1位

4.5. 第四次握手

第四次握手客户端（10.240.80.99 )关闭连接，并发送ACK值和Ack确认号( Ack的值+1)
包关键属性如下：

ACK ： 标志位
Seq = 2168：已经发送的数据字节
Ack = 14119 ：已经收到的数据字节+SYN包+ FIN包,Ack = 原Ack + 1, SYN标志位和FIN标志位也要占1位