算法演练----24点游戏

给定4个整数,数字范围在1~13之间任意使用+-*/(),构造出一个表达式,使得最终结果为24,

方法一 算法分析:加括号和取出重复表达式
# 导入精确除法模块,使得在Python2中除法运算的行为更接近Python3(Python3中除法默认是精确除法)
from __future__ import division
# 导入组合函数,用于生成给定元素的不同组合情况
from itertools import combinations
import re
import numpy as np# Solver类用于解决通过给定数字组合,利用四则运算及一些扩展运算来得到特定目标值(这里目标值默认为24)的问题
class Solver:# 定义目标值为24,即期望通过运算得到的结果target = 24# 定义可使用的运算符列表,包含常规四则运算以及扩展的重复减和重复除('--','//'),虽然在常规数学中不太常见,但这里作为一种自定义运算来丰富组合可能性ops = ['+', '-', '*', '/', '--', '//']# 类的初始化方法,接收一个参数precise_mode(默认为False),用于控制是否精确处理运算表达式中的括号等细节def __init__(self, precise_mode=False):self.precise_mode = precise_mode# solution方法是主要的对外接口,用于寻找能得到目标值的表达式,接收一个数字列表nums作为参数def solution(self, nums):result = []# 调用dimensionality_reduction方法对输入的数字列表进行降维处理(简化数字和运算组合的复杂度),得到不同的分组情况groups = self.dimensionality_reduction(self.format(nums))for group in groups:for op in self.ops:# 调用assemble方法根据给定的两个表达式(或数字)和运算符构建一个新的表达式exp = self.assemble(group[0], group[1], op)['exp']# 调用check方法检查构建的表达式计算结果是否接近(在一定精度范围内)目标值,并且确保该表达式不在结果列表中(避免重复添加)if self.check(exp, self.target) and exp not in result:result.append(exp)# 将找到的满足条件的表达式添加等于目标值的后缀,例如 "表达式 = 24" 的形式return [exp + '=' + str(self.target) for exp in result]# dimensionality_reduction方法用于对输入的表达式(或数字)列表进行降维处理,尝试通过不同的组合和运算逐步简化def dimensionality_reduction(self, nums):result = []# 如果输入的列表长度大于2,说明还有多个元素需要进一步组合运算if len(nums) > 2:# 使用group方法对nums进行分组,每次取2个元素为一组for group in self.group(nums, 2):for op in self.ops:# 调用assemble方法将每组的两个元素根据当前运算符进行组合,得到一个新的元素(包含运算后的表达式和运算符信息),与剩余元素组成新的列表继续进行降维处理new_group = [self.assemble(group[0][0], group[0][1], op)] + group[1]result += self.dimensionality_reduction(new_group)else:# 如果列表长度小于等于2,直接返回该列表作为一种基本情况(无法再进一步分解组合了)result = [nums]return result# assemble方法根据两个表达式(或数字)以及运算符构建一个新的表达式,同时处理一些特殊情况(如交换律、括号添加等)def assemble(self, exp1, exp2, op):# 如果运算符是重复减或重复除,交换两个表达式的顺序并递归调用assemble方法,将运算符还原为单减或单除进行处理(因为重复减和重复除可能是自定义的一种处理逻辑,这里转换为常规运算来构建表达式)if op == '--' or op == '//':return self.assemble(exp2, exp1, op[0])# 如果运算符是乘或除,给两个参与运算的表达式都添加括号,以明确运算顺序(按照数学运算规则,乘除运算优先级高于加减,添加括号可以更准确地体现运算顺序)if op in "*/":exp1 = self.add_parenthesis(exp1)exp2 = self.add_parenthesis(exp2)# 如果处于精确模式(precise_mode为True),根据不同运算符进一步处理括号添加情况if self.precise_mode:if op == '-':exp2 = self.add_parenthesis(exp2)elif op == '/':exp2 = self.add_parenthesis(exp2, True)# 调用convert方法对构建好的表达式进行格式转换(可能涉及一些字符串处理,比如调整运算顺序等,具体看convert方法实现),得到最终的表达式字符串exp = self.convert(exp1['exp'] + op + exp2['exp'], op)return {'op': op, 'exp': exp}# add_parenthesis方法根据条件决定是否给表达式添加括号,用于明确运算顺序或者遵循精确模式的要求@staticmethoddef add_parenthesis(exp, is_necessary=False):# 如果满足必要添加括号的条件(比如is_necessary为True且表达式不是单纯数字,或者运算符是加减),则添加括号if (is_necessary and not exp['exp'].isdigit()) or exp['op'] in "+-":result = {'exp': '(' + exp['exp'] + ')','op': exp['op']}else:result = expreturn result# check方法用于检查给定的表达式计算结果是否在一定精度范围内接近目标值,同时捕获除零异常(因为在eval运算表达式时可能出现除数为0的情况)@staticmethoddef check(exp, target, precision=0.0001):try:# 使用eval函数计算表达式的值,然后判断与目标值的差值是否小于给定精度,若小于则认为接近目标值,返回Truereturn abs(eval(exp) - target) < precisionexcept ZeroDivisionError:return False# convert方法用于对表达式字符串进行格式转换,主要涉及根据运算符调整表达式中各部分的顺序等操作@staticmethoddef convert(exp, op):# 如果运算符是加减,定义一个正则表达式模式,用于匹配包含乘除运算或者数字的部分,然后在表达式前添加正号(可能是为了统一处理符号相关逻辑)if op in "+-":pattern = r'([\+\-]((\(.+\)|\d+)[\*\/](\(.+\)|\d+)|\d+))'exp = '+' + expelse:# 如果运算符是乘除,定义另一种正则表达式模式,用于匹配乘除运算和数字部分,然后在表达式前添加乘号(同样可能是为了统一处理逻辑)pattern = r'([\*\/](\(.+?\)|\d+))'exp = '*' + exp# 使用正则表达式查找所有匹配的部分,提取并排序后拼接成新的字符串,目的可能是为了对表达式中的各运算部分进行一种规范化整理result = ''.join(sorted([i[0] for i in re.findall(pattern, exp)]))if len(result)!= len(exp):result = expreturn result[1:]# format方法将输入的数字列表转换为包含表达式和空运算符的字典列表,方便后续统一处理(将数字视为一种简单的表达式形式)@staticmethoddef format(nums):return [{'op': ' ', 'exp': str(num)} for num in nums]# group方法用于将输入的表达式(或数字)列表按照指定数量进行分组,生成不同的分组组合情况@staticmethoddef group(exp_list, counter):index_list = [i for i in range(len(exp_list))]combination = list(combinations(index_list, counter))for group1 in combination:group2 = list(set(index_list) - set(group1))yield [[exp_list[g1] for g1 in group1],[exp_list[g2] for g2 in group2]]if __name__ == "__main__":# 定义一个变量auto_input用于控制是否自动生成输入数字,如果为True则自动生成随机数字作为输入,否则手动从用户输入获取数字auto_input = Falseif auto_input:# 使用numpy的随机数生成功能,生成4个范围在1到20之间的整数作为输入数字列表customer_input = np.random.randint(1, 20, size=4).tolist()else:customer_input = []customer_input.append(input('请输入第一个数字:'))customer_input.append(input('请输入第二个数字:'))customer_input.append(input('请输入第三个数字:'))customer_input.append(input('请输入第四个数字:'))# 创建Solver类的实例,使用默认的precise_mode(False)task = Solver()# 调用solution方法寻找能得到目标值的表达式answer = task.solution(customer_input)if len(answer) == 0:print('No solution')else:for a in answer:print(a)

第二种方案:列表切片操作实现排列组合
以下代码用于获取用户输入的四个数字,不过目前处于注释状态,如果要使用,取消注释即可
a = int(input("请输入第1个数字:"))
b = int(input("请输入第2个数字:"))
c = int(input("请输入第3个数字:"))
d = int(input("请输入第4个数字:"))
list1 = [a, b, c, d]# 定义四则运算的符号列表,包含加、减、乘、除四种符号,后续将通过这些符号的不同组合来构建表达式进行运算
symbols = ["+", "-", "*", "/"]# 外层的三个嵌套循环,用于遍历所有可能的运算符号组合
# 通过三重循环可以生成所有符号的排列情况,例如:先固定第一个符号,遍历第二个和第三个符号的所有可能组合,然后再更换第一个符号,重复此过程
for s1 in symbols:for s2 in symbols:for s3 in symbols:# 内层的四层嵌套循环,用于尝试所有数字的排列组合进行运算# 通过不断改变数字的排列顺序以及结合外层循环的符号组合,来穷举所有可能的四则运算表达式情况for i in range(4):# 取出当前排列中索引为i的数字,作为第一个参与运算的数字,赋值给oneone = list1[i]# 通过列表切片操作,获取除去当前索引为i的数字后的剩余数字列表,赋值给list2# 例如:如果i为0,那么list2就是[b, c, d];如果i为1,list2就是[a, c, d],以此类推list2 = list1[0:i] + list1[i + 1:]for j in range(3):# 从剩余数字列表list2中取出索引为j的数字,作为第二个参与运算的数字,赋值给twotwo = list2[j]# 再次通过列表切片操作,获取除去当前索引为j的数字后的剩余数字列表,赋值给list3list3 = list2[0:j] + list2[j + 1:]for k in range(2):# 从剩余数字列表list3中取出索引为k的数字,作为第三个参与运算的数字,赋值给threethree = list3[k]# 通过列表切片操作获取最后一个参与运算的数字,赋值给four# 例如:如果k为0,那么four就是list3[1];如果k为1,four就是list3[0]four = (list3[0:k] + list3[k + 1:])[0]# 根据当前取出的数字和符号组合,构建一个四则运算表达式的字符串格式,后续将通过eval函数对其进行求值运算express = "(({0}{1}{2}){3}({4}){5}{6})".format(one, s1, two, s2, three, s3, four)try:# 使用eval函数对构建好的表达式字符串进行求值运算,eval函数会按照Python的运算规则解析并计算表达式result = eval(express)# 判断运算结果是否等于24,如果等于,则表示找到了满足条件的表达式if result == 24:# 输出找到的能得到24的表达式,并在表达式后面添加 " = 24" 进行标识,然后直接退出程序print(express + " = 24")# 找到结果为24的表达式后直接退出程序,避免继续不必要的循环计算exit(0)except ZeroDivisionError:# 捕获除零异常,因为在使用除法符号构建的表达式中,可能出现除数为0的情况,# 当出现这种情况时,捕获异常并跳过本次运算,继续尝试其他数字和符号的组合continue# 如果经过所有的数字排列组合和符号组合尝试后,都没有找到结果为24的表达式,则输出提示信息
print("无法算出")
#第三种itertools 模块实现排列组合
import itertools
import copy# 获取用户输入的四个数字
a = int(input("请输入第1个数字:"))
b = int(input("请输入第2个数字:"))
c = int(input("请输入第3个数字:"))
d = int(input("请输入第4个数字:"))
inputList = [a, b, c, d]listAll = []
listSignIndex = []
listSign = []
listSet = list(itertools.permutations(inputList, 4))
# 将生成的数字全排列结果转换为列表形式,并添加到listAll列表中,
# 这样listAll中就包含了输入的四个数字的所有不同排列情况
for i in listSet:listAll.append(list(i))# 该函数的功能是根据listSignIndex列表中的索引值,将对应的运算符号添加到listSign列表中
# 索引0对应 +,索引1对应 -,索引2对应 *,索引3对应 /
def changIndexToSign():for i in listSignIndex:if i == 0:listSign.append("+")elif i == 1:listSign.append("-")elif i == 2:listSign.append("*")elif i == 3:listSign.append("/")last = []# start函数用于尝试通过不同的运算组合(四则运算),利用输入的四个数字来得到结果为24的表达式
def start():global last# 遍历所有数字的排列情况(listAll列表中的每一组数字排列)for list1 in listAll:val = list1[0]  # 先取出当前排列的第一个数字作为初始值last = copy.deepcopy(list1)  # 深拷贝当前的数字排列,用于后续构建表达式字符串# 循环遍历四种运算符号,这里通过索引来对应不同的运算符号,0表示 +,1表示 -,2表示 *,3表示 /for i in range(4):if i == 0:val += list1[1]  # 如果索引为0,执行加法运算elif i == 1:val -= list1[1]  # 如果索引为1,执行减法运算elif i == 2:val *= list1[1]  # 如果索引为2,执行乘法运算elif i == 3:val /= list1[1]  # 如果索引为3,执行除法运算val2 = val  # 保存当前运算后的结果,用于内层循环结束后恢复值# 开始内层循环,再次遍历四种运算符号,用于对第三个数字进行运算for j in range(4):if j == 0:val += list1[2]elif j == 1:val -= list1[2]elif j == 2:val *= list1[2]elif j == 3:val /= list1[2]val1 = val  # 保存当前运算后的结果,用于最内层循环结束后恢复值# 最内层循环,同样遍历四种运算符号,用于对第四个数字进行运算for k in range(4):if k == 0:val += list1[3]elif k == 1:val -= list1[3]elif k == 2:val *= list1[3]elif k == 3:val /= list1[3]# 如果经过一系列运算后,结果等于24,则记录当前使用的运算符号索引if val == 24:listSignIndex.append(i)listSignIndex.append(j)listSignIndex.append(k)changIndexToSign()return  # 找到满足条件的组合后,直接返回,结束函数else:val = val1  # 如果结果不等于24,恢复到上一次内层循环运算后的结果,继续尝试其他运算符号val = val2  # 内层循环结束后,恢复到第二次运算后的结果,继续尝试其他运算符号val = list1[0]  # 外层循环每次开始时,恢复初始值,重新进行不同运算符号组合的尝试start()
listSign.append("")
lastStr = "(("
# 构建最终的表达式字符串,根据运算符号和数字的顺序进行拼接
for i in range(4):if i == 1 or i == 2:lastStr += str(last[i]) + ")" + listSign[i]else:lastStr += str(last[i]) + ")" + listSign[i]# 输出构建好的表达式字符串,并在末尾添加 =24,表示期望的结果为24
print(lastStr + "=24")输出结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470381.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

YUM 的使用

YUM 是一个用于 Fedora 和 Red Hat 以及 CentOS 操作系统的前端软件包管理器&#xff0c;它可以自动处理依赖关系并一次性安装所有必需的软件包。 镜像站点选择 1. 备份原有的镜像源配置文件 系统默认的 yum 镜像源配置文件存储在 /etc/yum.repos.d/ 目录下&#xff0c;可以…

第三十六章 Vue之路由重定向/404页面设置/路径模式设置

目录 一、路由重定向 1.1. 使用方式 1.2. 完整代码 1.2.1. main.js 1.2.2. App.vue 1.2.3. index.js 1.2.4. Search.vue 1.2.5. Home.vue 1.3. 运行效果 二、设定404错误页面 2.1. 使用方式 2.2. 完整代码 2.2.1. index.js 2.2.2. NotFound.vue 2.2.3. 运行效…

鸿蒙进阶篇-属性动画-animateTo转场动画

大家好啊&#xff0c;这里是鸿蒙开天组&#xff0c;今天我们来学习属性动画-animateTo&转场动画&#xff0c;咱们先来学习属性动画-animateTo 属性动画-animateTo 属性动画 animation是作为属性使用&#xff0c;而animateTo显示动画是一个系统的内置函数&#xff0c;可以…

[CKS] K8S ServiceAccount Set Up

最近准备花一周的时间准备CKS考试&#xff0c;在准备考试中发现有一个题目关于Rolebinding的题目。 ​ 专栏其他文章: [CKS] Create/Read/Mount a Secret in K8S-CSDN博客[CKS] Audit Log Policy-CSDN博客 -[CKS] 利用falco进行容器日志捕捉和安全监控-CSDN博客[CKS] K8S Netwo…

Autosar CP DDS规范导读

Autosar CP DDS 主要用途 数据通信 中间件协议&#xff1a;作为一种中间件协议&#xff0c;DDS实现了应用程序之间的高效数据通信&#xff0c;能够在不同的软件组件和ECU之间传输数据&#xff0c;确保数据的实时性和可靠性。跨平台通信&#xff1a;支持在AUTOSAR CP平台上的不同…

wafw00f源码详细解析

声明 本人菜鸟一枚&#xff0c;为了完成作业&#xff0c;发现网上所有的关于wafw00f的源码解析都是这抄那那抄这的&#xff0c;没有新东西&#xff0c;所以这里给出一个详细的源码解析&#xff0c;可能有错误&#xff0c;如果有大佬发现错误&#xff0c;可以在评论区平和的指出…

字节、快手、Vidu“打野”升级,AI视频小步快跑

文&#xff5c;白 鸽 编&#xff5c;王一粟 继9月份版本更新之后&#xff0c;光锥智能从生数科技联合创始人兼CEO唐家渝朋友圈获悉&#xff0c;Vidu大模型将于本周再次进行版本升级&#xff0c;Vidu-1.5版本即将上线。 此版本更新方向仍是重点延伸大模型的泛化能力和主体…

LeetCode【0036】有效的数独

本文目录 1 中文题目2 求解方法&#xff1a;python内置函数set2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 请根据以下规则判断一个 9 x 9 的数独是否有效。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线…

STM32 GPIO 配置

GPIO 八种工作模式 STM32的GPIO八种模式明解STM32—GPIO理论基础知识篇之八种工作模式stm32cubemx hal学习记录&#xff1a;GPIO输入输出[STM32G4系列] GPIO筆記 - CubeMX GPIO整理與應用 模拟量输入输出 ADC 【STM32】HAL库 STM32CubeMX教程九—ADC[通俗易懂] DAC STM32C…

Xcode 16 使用 pod 命令报错解决方案

原文请点击这个跳转 一、问题现象&#xff1a; 有人会遇到 Xcode 升级到 16 后&#xff0c;新建应用然后使用 pod init 命令会报错如下&#xff1a; Stack Ruby : ruby 3.3.5 (2024-09-03 revision ef084cc8f4) [x86_64-darwin23]RubyGems : 3.5.22Host : macOS 15.0 (24A335…

使用 Flask 和 ONLYOFFICE 实现文档在线编辑功能

提示&#xff1a;CSDN 博主测评ONLYOFFICE 文章目录 引言技术栈环境准备安装 ONLYOFFICE 文档服务器获取 API 密钥安装 Flask 和 Requests 创建 Flask 应用项目结构编写 app.py创建模板 templates/index.html 运行应用功能详解文档上传生成编辑器 URL显示编辑器回调处理 安全性…

机器学习——损失函数、代价函数、KL散度

&#x1f33a;历史文章列表&#x1f33a; 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…

vxe-table 3.10+ 进阶高级用法(一),根据业务需求自定义实现筛选功能

vxe-table 是vue中非常强大的表格的&#xff0c;公司项目中复杂的渲染都是用 vxe-table 的&#xff0c;对于用的排序。筛选之类的都能支持&#xff0c;而且也能任意扩展&#xff0c;非常强大。 默认筛选功能 筛选的普通用法就是给对应的列指定参数&#xff1a; filters&#…

推荐一款好用的postman替代工具2024

Apifox 是国内团队自主研发的 API 文档、API 调试、API Mock、API 自动化测试一体化协作平台&#xff0c;是非常好的一款 postman 替代工具。 它通过一套系统、一份数据&#xff0c;解决多个系统之间的数据同步问题。只要定义好接口文档&#xff0c;接口调试、数据 Mock、接口…

MTSET可溶于DMSO、DMF、THF等有机溶剂,并在水中有轻微的溶解性,91774-25-3

一、基本信息 中文名称&#xff1a;[2-(三甲基铵)乙基]甲硫基磺酸溴&#xff1b;MTSET巯基反应染料 英文名称&#xff1a;MTSET&#xff1b;[2-(Trimethylammonium)ethyl]methanethiosulfonate Bromide CAS号&#xff1a;91774-25-3 分子式&#xff1a;C6H16BrNO2S2 分子量…

如何为电子课程创造创意

为电子课程创造一个想法&#xff0c;首先要深刻理解是什么让知识对学习者既相关又吸引人。第一步是专注于可以分解为可教部分的特定技能或专业领域。通常&#xff0c;人们从他们熟悉的东西开始&#xff0c;但真正的挑战在于将这些知识转化为一种可访问且引人入胜的学习体验。这…

安全生产管理的重要性:现状、痛点与改进之路

当前&#xff0c;安全生产管理已经成为企业管理中的关键环节&#xff0c;但现实中仍然存在诸多痛点。近年来&#xff0c;随着工业化和现代化的快速推进&#xff0c;企业在追求效益的同时&#xff0c;忽视安全管理的现象屡见不鲜。据统计&#xff0c;安全事故的发生频率仍然较高…

深度学习之 LSTM

1.1 LSTM的产生原因 ​ RNN在处理长期依赖&#xff08;时间序列上距离较远的节点&#xff09;时会遇到巨大的困难&#xff0c;因为计算距离较远的节点之间的联系时会涉及雅可比矩阵的多次相乘&#xff0c;会造成梯度消失或者梯度膨胀的现象。为了解决该问题&#xff0c;研究人…

机器学习基础02_特征工程

目录 一、概念 二、API 三、DictVectorize字典列表特征提取 四、CountVectorize文本特征提取 五、TF-IDF文本1特征词的重要程度特征提取 六、无量纲化预处理 1、MinMaxScaler 归一化 2、StandardScaler 标准化 七、特征降维 1、特征选择 VarianceThreshold 底方差…

Linux第四讲:Git gdb

Linux第四讲&#xff1a;Git && gdb 1.版本控制器Git1.1理解版本控制1.2理解协作开发1.3Git的历史1.4Git的操作1.4.1仓库创建解释、仓库克隆操作1.4.2本地文件操作三板斧1.4.3文件推送详细问题 2.调试器 -- gdb/cgdb使用2.1调试的本质是什么2.2watch命令2.3set var命令…