[已解决]24点题目，求助大佬，要写程序！

zhangjinxuan

顶一顶

hveagle

import sys, os

n4 = []
ans = [0]
oplist = ["+", "-", "*", "/"]
anslist = []
wanted = 24
given = 4

def cal(a, b, signal):
    if not b and signal == "/":
        return False
    if signal == "+":
        return a + b
    elif signal == "-":
        return a - b
    elif signal == "*":
        return a * b
    elif signal == "/":
        return a/b


def digui(numlist):
    
    if len(numlist) == 2:
        a, b = tuple(numlist)
        for op in oplist:
            if cal(a, b, op) == wanted :
                anslist.append(str(a) + op + str(b) + "=" + str(wanted))
                ans[0] += 1
                print(anslist)
                anslist.pop()

    else:
        for i in range(len(numlist)):
            nx = numlist[:]
            a = nx.pop(i)
            for j in range(len(nx)):
                b = nx[j]
                for op in oplist:
                    result = cal(a, b, op)
                    if result == 0:
                        continue
                    else:
                        nx[j] = result
                        anslist.append(str(a) + op + str(b) + "=" + str(result))
                        digui(nx)
                        anslist.pop()
                nx[j] = b
                
    return ans[0]


for i in range(1,given+1):
    temp = int(input("请输入第%d个数字:" % i))
    n4.append(temp)

if digui(n4) == 0:
    print('no answer')

zhangjinxuan

hveagle 发表于 2022-12-4 09:23

C++!

zhangjinxuan

hveagle 发表于 2022-12-4 09:23

你明明是懂算法的人，为什么每周一练出那么简单？

zhangjinxuan

顶一顶？

zhangjinxuan

有人吗！

zhangjinxuan

tommyyu 发表于 2022-12-2 09:39
这个程序的大致思路是选两个数并进行运算

我应该写不了快期末了，还要复习，这个周末还有一 ...

我想了想，我觉得就只能像你这么说的思路来了

就是先生成一个1到n的排列，表示数字的顺序，再用 O(4 ^ (n - 1)) 的算法枚举每一个运算符，最后生成一个 1 ~ n - 1 的排列，表示运算的顺序，最后用O(2n)开始运算，运算结果对了就返回，再最终处理表达式，O(n)……

所以，这个程序的准确时间复杂度就是 O(n! * 4 ^ (n - 1) * (n - 1)! * 2n + n)，除非可以剪枝，6个数字不可能过去

而且搞全排列也不一定是 O(n!)，用传统方法搞全排列应该是 O(n ^ n)，你可以想一想，所以最终算法最坏的准确复杂度就是：
O(n^n * 4 ^ (n - 1) * (n - 1)^(n - 1) * 2n + n)
这算5个数字都感觉比较悬

zhangjinxuan

高山 发表于 2022-12-4 19:10
这个要求对算法太有难度了，我曾经研究一段时间24点算法，也写过一些程度，但的确没有找到完美的算法，难度 ...

好的，我研究研究

高山

zhangjinxuan 发表于 2022-12-4 19:15
好的，我研究研究

如果不过的话我再问问他

jhq999

高山 发表于 2022-12-4 19:10
这个要求对算法太有难度了，我曾经研究一段时间24点算法，也写过一些程度，但的确没有找到完美的算法，难度 ...

((3/8-3)/8)=-21/8/8=-21/64？
8/(3-8/3)=24

高山

jhq999 发表于 2022-12-4 19:19
((3/8-3)/8)=-21/8/8=-21/64？

我也没看，问别人的
重金悬赏问别人的
(转载https://wenda.so.com/q/1669972919218592）

zhangjinxuan

高山 发表于 2022-12-4 19:10
这个要求对算法太有难度了，我曾经研究一段时间24点算法，也写过一些程度，但的确没有找到完美的算法，难度 ...

(((3/8)-3)/8) 不对

我觉得可以定义两个新运算 _ 和 |，定义 a _ b = b - a, a | b = b / a，这样的话可以避免了一些从左往右计算的缺陷，但代价就是有写一个函数

zhangjinxuan

高山 发表于 2022-12-4 19:18
如果不过的话我再问问他

我觉得有一种思路，就是先生成一个1到n的排列，表示数字的顺序，再用 O(4 ^ (n - 1)) 的算法枚举每一个运算符，最后生成一个 1 ~ n - 1 的排列，表示运算的顺序，最后开始运算，运算结果对了就返回

你觉得呢？

zhangjinxuan

zhangjinxuan 发表于 2022-12-4 19:21
(((3/8)-3)/8) 不对

我觉得可以定义两个新运算 _ 和 |，定义 a _ b = b - a, a | b = b / a，这样的话 ...

但你这个也考虑了，我就有点懵逼了

zhangjinxuan

高山 发表于 2022-12-4 19:20
我也没看，问别人的
重金悬赏问别人的
(转载https://wenda.so.com/q/1669972919218592）

啊这，我还以为

jhq999

我对分数的思路
8/(3-8/3)=8*3/(3*(3-8/3))=24/((9-8))==24;
a/(b-c/d)=a*d/(b*d-c)=8*3/(3*3-8)=24
(a/b)/(c/d)=(a/b)*bd/(c/d*bd)=ad/bc

zhangjinxuan

jhq999 发表于 2022-12-4 19:37
我对分数的思路
8/(3-8/3)=8*3/(3*(3-8/3))=24/((9-8))==24;
a/(b-c/d)=a*d/(b*d-c)=8*3/(3*3-8)=24

我觉得没必要，毕竟double精度那么高，也丢不了多少吧

jhq999

zhangjinxuan 发表于 2022-12-4 19:38
我觉得没必要，毕竟double精度那么高，也丢不了多少吧

能避免八哥尽量避免

zhangjinxuan

jhq999 发表于 2022-12-4 19:39
整除

但重点不在分数

tommyyu

zhangjinxuan 发表于 2022-12-4 18:32
我想了想，我觉得就只能像你这么说的思路来了

就是先生成一个1到n的排列，表示数字的顺序，再用 O(4 ^ ...

这样的枚举方法不仅会超时，还有可能有重复输出，原因是这样可能会有等价的等式被计算，而我说的是任选两个数，并对其进行六种运算方式之一，并进行递归，时间复杂度不会太高，但是对写代码的人的程序细节要求会比较高，对于n个数，时间复杂度是
C22 * C23 * C24 * ... * C2n * 4^(n-1)，大概可以撑住7个数左右，但是写完程序之后我感觉至少得优化并修bug一两个小时