猜数游戏，比较三种算法

大家好，欢迎来到IT知识分享网。

猜数游戏一般的规则如下：

一个人（通常称为出题者）在心中想一个特定范围内的数字，比如 1 到 100 之间。另一个人（通常称为猜题者）通过不断猜测来试图猜出这个数字。

猜题者每次猜测后，出题者会告知猜测的数字是大了还是小了，猜题者根据这些提示继续猜测，直到猜对为止。

以1 到 100 之间为例，分别使用黄金分割搜索法、二分法、随机数法计算猜出数字所用的步数，以图表的形式进行比较

import math import matplotlib.pyplot as plt import random # 获取输入的最小值和最大值 min_num_input = input("请输入最小值：") max_num_input = input("请输入最大值：") # 将输入的字符串转换为整数，如果输入为空则使用默认值 min_num = int(min_num_input) if min_num_input else 1 max_num = int(max_num_input) if max_num_input else 100 if min_num > max_num: min_num, max_num = max_num, min_num # 确保最小值小于等于最大值 # 黄金分割搜索法的结果列表和步数列表 numbers_golden = [] steps_golden = [] def golden_section_search(min_num=1, max_num=100): """ 黄金分割搜索法的函数 遍历 1 到 100 的数字，使用黄金分割搜索法进行搜索 """ for num in range(min_num, max_num+1): low = 1 high = 100 step = 0 golden_ratio = (1 + math.sqrt(5)) / 2 while low <= high: ratio = high - low probe = low + ratio * (golden_ratio - 1) probe = int(probe) # 确保猜测的数字为整数 if probe == num: numbers_golden.append(num) steps_golden.append(step + 1) # print(f"Number {num} is guessed in {step + 1} steps.") break elif probe < num: low = probe + 1 else: high = probe - 1 step += 1 # 二分法的结果列表和步数列表 numbers_binary = [] steps_binary = [] def binary_search(min_num=1, max_num=100): """ 二分搜索法的函数 遍历 1 到 100 的数字，使用二分搜索法进行搜索 """ for num in range(min_num, max_num+1): low = 1 high = 100 step = 0 while low <= high: mid = int((low + high) // 2) # 确保猜测的数字为整数 if mid == num: numbers_binary.append(num) steps_binary.append(step + 1) # 输出结果并结束循环 # print(f"Number {num} is guessed in {step + 1} steps.") break elif mid < num: low = mid + 1 else: high = mid - 1 step += 1 # 随机猜测法的结果列表和步数列表，每次猜测后会缩小范围 numbers_random = [] steps_random = [] def random_guess_search(min_num=1, max_num=100): """ 随机猜测法的函数 遍历 1 到 100 的数字，使用随机猜测法进行搜索，并在每次猜测后缩小范围 """ for num in range(min_num, max_num+1): step = 0 low = 1 high = 100 while high - low > 1: # 缩小猜测范围 """ 在 high - low 的范围大于 1 时进行随机猜测 """ guess = random.randint(low, high) if guess == num: numbers_random.append(num) steps_random.append(step + 1) # 输出结果并结束循环 # print(f"Number {num} is guessed in {step + 1} steps.") break elif guess < num: low = guess else: high = guess step += 1 # 绘制图表 golden_section_search(min_num, max_num) binary_search(min_num, max_num) # 绘制搜索方法的图表 plt.plot(numbers_golden, steps_golden, label='Golden Section Search') plt.plot(numbers_binary, steps_binary, label='Binary Search') # plt.plot(numbers_random, steps_random, label='Random Guess Search') plt.xlabel('Numbers') plt.ylabel('Steps') plt.title('Comparison of Search Methods') plt.legend() plt.show() # 计算随机数法与其他两种方法的差值 random_guess_search(min_num, max_num) diff_golden = [steps_random[i] - steps_golden[i] for i in range(len(steps_random))] diff_binary = [steps_random[i] - steps_binary[i] for i in range(len(steps_random))] # 绘制差值图表 plt.subplot(212) plt.plot(numbers_random, diff_golden, label='Difference with Golden Section Search') plt.plot(numbers_random, diff_binary, label='Difference with Binary Search') plt.xlabel('Numbers') plt.ylabel('Difference in Steps') plt.title('Difference in Steps for Random Guess Search') plt.legend() plt.show()