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

zhangjinxuan · 发表于 2022-12-3 12:33:13

顶一顶

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

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 · 发表于 2022-12-4 09:26:09

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

C++!

zhangjinxuan · 发表于 2022-12-4 09:56:22

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

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

zhangjinxuan · 发表于 2022-12-4 10:53:14

顶一顶？

zhangjinxuan · 发表于 2022-12-4 18:23:58

有人吗！

zhangjinxuan · 发表于 2022-12-4 18:32:29

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:15:24

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

好的，我研究研究

高山 · 发表于 2022-12-4 19:18:51

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

如果不过的话我再问问他

jhq999 · 发表于 2022-12-4 19:19:26

本帖最后由 jhq999 于 2022-12-4 19:24 编辑

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

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

高山 · 发表于 2022-12-4 19:20:27

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:21:58

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

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

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

zhangjinxuan · 发表于 2022-12-4 19:23:23

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

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

你觉得呢？

zhangjinxuan · 发表于 2022-12-4 19:24:19

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

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

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

zhangjinxuan · 发表于 2022-12-4 19:33:39

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

啊这，我还以为

jhq999 · 发表于 2022-12-4 19:37:00

本帖最后由 jhq999 于 2022-12-4 19:38 编辑

我对分数的思路
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 · 发表于 2022-12-4 19:38:49

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 · 发表于 2022-12-4 19:39:22

本帖最后由 jhq999 于 2022-12-4 19:42 编辑

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

能避免八哥尽量避免

zhangjinxuan · 发表于 2022-12-4 19:41:27

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

但重点不在分数

tommyyu · 发表于 2022-12-4 19:41:44

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

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

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

账号		自动登录	找回密码
密码			立即注册

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

评分

浏览过的版块