一、今天观麦的一个笔试题，感觉有点意思
给一个字符串"123456789",
在任意字符中间插入“+”、“-”、“*”、“/”四种运算符，使最后的计算结果等于50。
例如你可以如此插入：1*2*3*4-56-7+89，使这个式子的最终结果等于50。
输出所有可能的式子结果
我的思路一开始是穷举，然后是想着用动态规划的思想去做了，将问题分而治之，使用50 + - * / “空”去计算处理0到i个因子，然后其结果，同最后length-i 个数组成最大值，也就是后面的所有位数不做任何变化，即使最大的（如：78*9<78*10=780<789）所以做比较如果左乘法<50,那么这条路劲就不行，
同理除法>50，加法<50，减法>50；都是结束条件。
以上尝试均失败23333
最后成功还是用了递归啊！
1 """ 2 给一个字符串"123456789", 3 在任意字符中间插入“+”、“-”、“*”、“/”四种运算符，使最后的计算结果等于50。 4 例如你可以如此插入：1*2*3*4-56-7+89，使这个式子的最终结果等于50。 5 输出所有可能的式子结果。 6 """ 7 rvs_op = { 8 "+":"-", 9 "-":"+", 10 "*":"/", 11 "/":"*", 12 } 13 result = [] 14 15 def inner_make(operator, pos, lastret, remain_num, acc_ret): 16 # 如果操作符为空就将原来的remain 原样返回，并且 pos+1 17 remain_num = remain_num.replace(pos, pos + operator) 18 if operator == "+" or operator == "-": 19 temp = remain_num.split(operator) 20 remain_num = temp[1] 21 lastret = eval(acc_ret + temp[0]) 22 acc_ret += temp[0]+operator 23 if pos == "8": 24 ret = eval(acc_ret+remain_num) 25 if ret==50: 26 result.append(acc_ret+remain_num) 27 return 28 pos = str(int(pos) + 1) 29 30 for i in ["+", "-", "*", "/", ""]: 31 inner_make(i, pos, lastret, remain_num, acc_ret) 32 33 def make_50(nums: str) -> list: 34 inner_make("", "0", 1, nums, "") 35 return result 36 37 38 39 40 # 不要修改下面的部分 41 if __name__ == "__main__": 42 results = make_50("123456789") 43 for result in results: 44 assert eval(result) == 50 45 print("OK")
D:projectvenvScriptspython.exe E:/chromeDownload/problem1.py 1+2+3+4+5*6-7+8+9 1+2+3+4+56*7/8-9 1+2+3+4-56+7+89 1+2+3-4+5+6*7-8+9 1+2+3-4+56-7+8-9 1+2+3-4-5+6+7*8-9 1+2+3*4+5+6+7+8+9 1+2+3*4+5-6*7+8*9 1+2+3*4-5*6+7*8+9 1+2+3*4-5*6-7+8*9 1+2+3*45-6+7-89 1+2+34-5-6+7+8+9 1+2+34-56+78-9 1+2-3+4+5+6*7+8-9 1+2-3+4+5-6+7*8-9 1+2-3+4+56+7-8-9 1+2-3+4*5+6+7+8+9 1+2-3+4*5-6*7+8*9 1+2-3+45-67+8*9 1+2-3-4+5*6+7+8+9 1+2-3-4-5+6*7+8+9 1+2-3-4-5-6+7*8+9 1+2-3-4-5-6-7+8*9 1+2-34+5-6-7+89 1+2-34-56/7+89 1+2*3+4-5*6+78-9 1+2*3+45+6-7+8-9 1+2*3-4-5+6*78/9 1+2*3-4*5-6+78-9 1+2*3-45+6-7+89 1+2*3*4+56/7+8+9 1+2*3*4-5+6+7+8+9 1+2*3*4-5-6*7+8*9 1+2*3*4*5-6+7-8*9 1+2*3*4*5-6-7*8-9 1+2*34-5-6-7+8-9 1+23+4+5*6-7+8-9 1+23-4+5+6*7-8-9 1+23-45+6+7*8+9 1+23-45+6-7+8*9 1-2+3-4+5-6*7+89 1-2+3-4-5*6-7+89 1-2+3-4*5+67-8+9 1-2+3-45+6+78+9 1-2+3-456+7*8*9 1-2+3*4-5*6+78-9 1-2+3*45-67-8-9 1-2+3/4*5+6*7/8*9 1-2+34+5+6+7+8-9 1-2+34-5-67+89 1-2+34-5*6+7*8-9 1-2-3+4+56-7-8+9 1-2-3-4+5+6+7*8-9 1-2-3-4+56*7/8+9 1-2-3-4-5-6+78-9 1-2-3*4-5+67-8+9 1-2-34-5-6+7+89 1-2*3+4*5*6+7-8*9 1-2*3+4*5*6-7*8-9 1-2*3-4*5+6+78-9 1-2*3*4+5+67-8+9 1-2*3*4+56/7*8+9 1-2*3*4*5/6+78-9 1-2*34+5*6+78+9 1-23+4+5-6+78-9 1-23+4-5-6+7+8*9 1-23+4*5+6*78/9 1-23-4+5+6+7*8+9 1-23-4+5+6-7+8*9 1-23-4-5-6+78+9 1*2+3+4*5+6*7-8-9 1*2+3+45+6-7-8+9 1*2+3+45-6+7+8-9 1*2+3-4-5*6+7+8*9 1*2+3-45-6+7+89 1*2+3*4+5*6+7+8-9 1*2+3*4-5+6*7+8-9 1*2+3*4-5-6+7*8-9 1*2+3*4*5-6-7-8+9 1*2+3/4*56+7+8-9 1*2-3+4-5+6*78/9 1*2-3+4*5*6-78+9 1*2-3-4+5+67-8-9 1*2-3-4+56/7*8-9 1*2-3-4*5+6+7*8+9 1*2-3-4*5+6-7+8*9 1*2*3+4+5*6-7+8+9 1*2*3+4+56*7/8-9 1*2*3+4-56+7+89 1*2*3-4+5+6*7-8+9 1*2*3-4+56-7+8-9 1*2*3-4-5+6+7*8-9 1*2*3*4-56-7+89 1*2*345/6+7-8*9 1*2*345/6-7*8-9 1*2/3*4+56-78/9 1*23+4+5-6+7+8+9 1*23+4-56+7+8*9 1*23+45+6-7-8-9 1*23-4-56+78+9 1*23-4*5-6*7+89 1*23*4+5+6*7-89 1/2+345/6-7+8-9 12+3+4-56+78+9 12+3-4-5*6+78-9 12+3*4-56-7+89 12+3*4*5+67-89 12-3+4*5*6-7-8*9 12-3+45+6+7-8-9 12-3-4-5+67-8-9 12-3*4+56-7-8+9 12*3+4+5-67+8*9 12*3+4+56/7/8+9 12*3-45+6*7+8+9 12*3-45-6+7*8+9 12*3-45-6-7+8*9 12*3/4*5-67+8*9 12*34/56*7+8-9 12/3+4-5-6*7+89 12/3-4+56-7-8+9 12/3-4*5+67+8-9 12/3*4*5+6*7-8*9 12/3*4*5-6-7-8-9 12/3/4-5*6+7+8*9 12/3/4*56-7-8+9 123+4-5*6-7*8+9 123+4*5-6-78-9 123-4*5-6-7*8+9 123-4*5*6+7*8-9 123/4+5+6*7/8+9 OK Process finished with exit code 0