1. 猜数游戏

1.1 游戏规则

【 游戏双方 】防守者和攻击者。

【 游戏准备 】防守者在1~1000内任选一个自然数作为神秘数，并暗自记住，然后开始游戏。

【 游戏过程 】每轮游戏的过程如下

• 攻击者猜一个数，问防守者这个数是否是神秘数。

• 防守者要根据事实给出下面3个答案中的一个：

￮ 这个数就是神秘数

￮ 这个数比神秘数小

￮ 这个数比神秘数大

• 又下可持续多轮

【 游戏结果 】如果攻击者猜中神秘数，则算攻击者赢；否则，算防守者赢。

1.2 不限猜测次数的游戏的必胜攻略

不限猜猜测次数，攻击者必胜攻略

总共1000个数，攻击者可以从1开始猜，1不正确就猜2，2不正确就猜3，以此类推，一直猜到1000，肯定能够猜到神秘数。

该问题为查找问题——在1~1000这1000个整数中找到对手预设的神秘数（目标数）

编程实现必胜算法

tn = 165

found = False

for i in range(1,1001):

if i == tn:

print("secrete number is", i)

found = True

break

if not found:

print("failed")

代码解析：

tn = 165 # 定义一个变量tn，赋值为165

found = False # 定义一个变量found，初始值为False，表示尚未找到tn

for i in range(1,1001): # 从1到1000（不包括1001）创建一个整数序列，并将每个整数赋值给变量i

if i == tn: # 如果变量i等于变量tn的值

print("secrete number is", i) # 打印“secrete number is”和当前的i值（注意：这里的单词应为"secret number is"）

found = True # 将found变量的值改为True，表示找到了tn

break # 退出当前的for循环

if not found: # 如果在循环结束后found仍然为False

print("failed") # 打印“failed”

当执行这段修正后的代码时，它会进行以下操作：

1. 定义一个变量tn并赋值为165。

2. 定义一个变量found并初始化为False，表示尚未找到目标数字。

3. 使用for循环遍历从1到1000的整数。

4. 在循环内部，检查当前的整数i是否等于tn。

5. 如果找到匹配的数字，打印出“secret number is”和该数字，将found设置为True，然后使用break语句退出循环。

6. 如果循环正常结束而没有找到匹配的数字，则打印出“failed”。

在这个特定的例子中，代码将打印出“secret number is 165”，因为165确实在1到1000的范围内。如果tn的值不在1到1000的范围内，它将打印出“failed”。

1.3 限猜测次数的游戏

更新游戏规则：【 游戏结果 】如果攻击者在10次（含）之内猜中神秘数，则算攻击者赢；否则，算防守者赢。

如保证攻击者胜利，需要算法在1~1000这1000个数字中查找一个数字，保证最多查找10次就能查找到。这个算法是二分查找。

2. 二分查找：从原理到形式化描述

2.1 二分查找的原理

二分查找是一种在有序数列中查找某个特定元素（目标数）的查找算法

• 最初的待查数列和目标数由用户定义

• 查找过程是一个迭代（循环）过程

￮ 待查数列不为空时进入循环，否则查找失败——查找过程结束

￮ 每次循环从待查数列的中心元素开始。

▪ 如果中心元素正好等于目标数，则查找成功——查询过程结束

▪ 如果目标数大于或小于中心元素，则数列大于或小于中心元素的那一半称为新的待查数据列

2.2 二分查找的变成实现

形式化流程控制

从流程到代码

实现1～1000数列的二分查找算法

arr = list(range(1,1001))

tn = 635

low = 0

high = len(arr)-1

while low <= high:

m = int((high - low )/ 2) + low

if arr[m] == tn:

print("Succeeded! The target number is: ",arr[m])

break

else:

if arr[m] < tn:

low = m + 1

else:

high = m - 1

if low > high:

print("Search failed.")

另一种写法

tn = 635

low = 1

high = 1000

while low <= high:

m = int((high - low)/ 2) + low

if m == tn:

print("Succeeded! The target number is: ", m)

break

else:

if m < tn:

low = m + 1

else:

high = m - 1

if low > high:

print("Search failed.")