【算法题】24点问题.

【算法题】24点问题.

3 years ago

source link: https://www.guofei.site/2017/08/29/intersting4.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

2017年08月29日

Author: Guofei

文章归类: 趣文，文章编号:

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2017/08/29/intersting4.html

Edit

问题

给定4个整数，进行加减乘除四则运算后结果可能为24，输出所有这样的运算方法，要求：

运算式中的数字不改变顺序
可以任意加括号，以改变运算有限顺序

4*((5-6)+7)=24
4*(5-(6-7))=24

分析

考虑4种运算的实现方法(不考虑括号)
a?b?c?d
用一个函数cal(a,b,op)来表示a?b
考虑括号的实现方法(不考虑运算符)
总共有5种情况
（代码里把5种情况一一列出来，有点丑，似乎可以用二叉树做，但没有思路。如果你有好的做法，请告诉我）

代码实现

def cal(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        return a / b


def cal_mod1(a, b, c, d, op1, op2, op3):
    temp1 = cal(a, b, op1)
    temp2 = cal(temp1, c, op2)
    temp3 = cal(temp2, d, op3)
    return temp3


def cal_mod2(a, b, c, d, op1, op2, op3):
    temp1 = cal(a, b, op1)
    temp2 = cal(c, d, op3)
    temp3 = cal(temp1, temp2, op2)
    return temp3


def cal_mod3(a, b, c, d, op1, op2, op3):
    temp1 = cal(b, c, op2)
    temp2 = cal(a, temp1, op1)
    temp3 = cal(temp2, d, op3)
    return temp3


def cal_mod4(a, b, c, d, op1, op2, op3):
    temp1 = cal(b, c, op2)
    temp2 = cal(temp1, d, op3)
    temp3 = cal(a, temp2, op1)
    return temp3


def cal_mod5(a, b, c, d, op1, op2, op3):
    temp1 = cal(c, d, op3)
    temp2 = cal(b, temp1, op2)
    temp3 = cal(a, temp2, op1)
    return temp3


def cal_problem(a, b, c, d):
    for op1 in list('+-*/'):
        for op2 in list('+-*/'):
            for op3 in list('+-*/'):
                if cal_mod1(a, b, c, d, op1, op2, op3) == 24:
                    print('(({}{}{}){}{}){}{}=24'.format(a, op1, b, op2, c, op3, d))
                if cal_mod2(a, b, c, d, op1, op2, op3) == 24:
                    print('({}{}{}){}({}{}{})=24'.format(a, op1, b, op2, c, op3, d))
                if cal_mod3(a, b, c, d, op1, op2, op3) == 24:
                    print('({}{}({}{}{})){}{}=24'.format(a, op1, b, op2, c, op3, d))
                if cal_mod4(a, b, c, d, op1, op2, op3) == 24:
                    print('{}{}(({}{}{}){}{})=24'.format(a, op1, b, op2, c, op3, d))
                if cal_mod5(a, b, c, d, op1, op2, op3) == 24:
                    print('{}{}({}{}({}{}{}))'.format(a, op1, b, op2, c, op3, d))


cal_problem(4, 5, 6, 7)
cal_problem(5, 4, 3, 8)

output：

4*((5-6)+7)=24
4*(5-(6-7))=24
((5+4)/3)*8=24
(5+4)/(3/8)=24
((5-4)*3)*8=24
(5-4)*(3*8)=24

5种情况一一列出来，有点丑，你有没有更好的实现方法呢？

您的支持将鼓励我继续创作！

Recommend

rollingstarky.github.io 5 years ago
Cache

基本算法问题的 Python 解法（递归与搜索） | StarryLand

基本算法问题的 Python 解法（递归与搜索） ...

www.cnblogs.com 4 years ago
Cache

Python的多继承问题-MRO和C3算法

Python 中的方法解析顺序（Method Resolution Order, MRO）定义了多继承存在时 Python 解释器查找函数解析的正确方式。当 Python 版本从 2.2 发展到 2.3 再到现在的 Python 3，MRO算法也随之发生了相应的变化。这种变化在很多时候影响了我...