知乎使用者2018-03-19 13:57:27（-1） - 1 * （4 - 5 * 1 ^ 4） = 0
1 ^ （1 - 4 - 5 ^ 14） = 1
（-1） * （1 + （4 + 5） / （1 - 4）） = 2
（-1） * （1 + （4 - 5 * 1） * 4） = 3
（-1） - 1 * （4 - 5 - 1 * 4） = 4
（-1） - 1 * （4 - 5 - 1 - 4） = 5
（-1） + 14 / （5 + 1 - 4） = 6
（-1） * （1 + （4 - 5 - 1） * 4） = 7
（-1） - 1 ^ 4 * （5 - 14） = 8
（-1） + 1 * （4 + 5 + 1 ^ 4） = 9
（-1） - 1 * （4 + 5 * （1 - 4）） = 10
（-1） - 1 * （4 - （5 - 1） * 4） = 11
（-1） + 1 * （4 - 5 + 14） = 12
（-1） * （1 + （4 - 5） * 14） = 13
（-1） - 1 * （4 - 5 - 14） = 14
（-1） - 1 * （4 - 5 * 1 * 4） = 15
1 - 1 * （4 - 5 - 14） = 16
1 - 1 * （4 - 5 * 1 * 4） = 17
（-1） * （1 - 4 + 5 * （1 - 4）） = 18
（-1） - 1 * （4 - （5 + 1） * 4） = 19
（-1） - 1 * （4 - 5 * （1 + 4）） = 20
1 - 1 * （4 - （5 + 1） * 4） = 21
（-1） * （1 - 4 - 5 - 14） = 22
（-1） - （1 - 4） * （5 - 1 + 4） = 23
1 + 1 * （4 + 5 + 14） = 24
1 - （1 - 4） * （5 - 1 + 4） = 25
（-1） - （1 - 4） * （5 + 1 * 4） = 26
（-1） + 1 - （4 + 5） * （1 - 4） = 27
（-1） * （1 - 4 - 5 * （1 + 4）） = 28
（-1） - （1 - 4） * （5 + 1 + 4） = 29
（-1） + 1 * （45 - 14） = 30
（-1） - （1 - 4 - 5 * 1） * 4 = 31
1 + 1 * （45 - 14） = 32
（-1） * （1 - 4 * 5 - 14） = 33
（-11） + （4 + 5） * （1 + 4） = 34
（-1） - 1 * 4 * （5 - 14） = 35
（-1） + 1 - 4 * （5 - 14） = 36
1 - 1 * 4 * （5 - 14） = 37
1 * （14 + （5 + 1） * 4） = 38
（-1） * （1 - 4 * （5 + 1 + 4）） = 39
（-1） * （1 - 45 + 1 * 4） = 40
（-1） * （1 - 45 - 1 + 4） = 41
（-1） - 1 * （4 - 51 + 4） = 42
（-1） + 1 * （45 - 1 ^ 4） = 43
（-1） - （1 + 4） * （5 - 14） = 44
1 + 1 * （45 - 1 ^ 4） = 45
（-1） * （1 ^ 4 - 51 + 4） = 46
（-1） * （1 - 45 + 1 - 4） = 47
（-1） * （1 - 45 - 1 * 4） = 48
（-1） * （1 - 45 - 1 - 4） = 49
（-1） - 1 * （4 - 51 - 4） = 50
1 + 1 * （45 + 1 + 4） = 51
1 - 1 * （4 - 51 - 4） = 52
（-11） + 4 * （5 - 1） * 4 = 53
（-1） * （1 ^ 4 - 51 - 4） = 54
（-1） + 14 * （5 - 1 ^ 4） = 55
（-1） - （1 - 4） * （5 + 14） = 56
1 + 14 * （5 - 1 ^ 4） = 57
（-1） * （1 - 45 - 14） = 58
（-1） - 1 * 4 * 5 * （1 - 4） = 59
1 + 1 * （45 + 14） = 60
1 - 1 * 4 * 5 * （1 - 4） = 61
（-1） - 1 + 4 * （5 - 1） * 4 = 62
（-1） - （（1 - 4） * 5 - 1） * 4 = 63
（-1） + 1 + 4 * （5 - 1） * 4 = 64
（-1） - 1 * （4 - 5 * 14） = 65
1 * （14 * 5 - 1 * 4） = 66
（-1） + （1 + 4 * （5 - 1）） * 4 = 67
（1 + 1） * （4 * 5 + 14） = 68
（-1） * （1 ^ 4 - 5 * 14） = 69
（-1） + 1 ^ 4 + 5 * 14 = 70
（-1） - （1 - 4） * （5 + 1） * 4 = 71
（（-1） - 1） * 4 * （5 - 14） = 72
（-1） * （1 - 4 - 5 * 14） = 73
（-1） - 1 + 4 * （5 + 14） = 74
（-1） - （1 - 4 * 5 * 1） * 4 = 75
（-1） + 1 + 4 * （5 + 14） = 76
1 - （1 - 4 * 5 * 1） * 4 = 77
（-1） - 1 + 4 * 5 * 1 * 4 = 78
（-1） - （1 - 4 * 5 - 1） * 4 = 79
（-1） + 1 + 4 * 5 * 1 * 4 = 80
1 - （1 - 4 * 5 - 1） * 4 = 81
（-1） - 1 + （4 * 5 + 1） * 4 = 82
（-1） * （1 - （4 * 5 + 1） * 4） = 83
（-1） + 1 + （4 * 5 + 1） * 4 = 84
1 + 14 * （5 + 1 ^ 4） = 85
（（-1） - 1） * （4 - 51 + 4） = 86
（-1） + （1 + 4 * 5 + 1） * 4 = 87
（1 + 1） * （45 - 1 ^ 4） = 88
1 + （1 + 4 * 5 + 1） * 4 = 89
（-114） + 51 * 4 = 90
（-1） - （1 - 4 * （5 + 1）） * 4 = 91
（1 + 1） * （45 + 1 ^ 4） = 92
1 - （1 - 4 * （5 + 1）） * 4 = 93
（-1） + （1 + 4） * （5 + 14） = 94
（-1） * （1 - 4 * （5 + 1） * 4） = 95
1 + （1 + 4） * （5 + 14） = 96
1 + 1 * 4 * （5 + 1） * 4 = 97
（-1） - 1 + 4 * 5 * （1 + 4） = 98
（-1） * （1 - 4 * 5 * （1 + 4）） = 99
匿名使用者2018-03-19 20:27:58#include
#include
#include
#define n_cards 6
#define solve_goal 114
#define max_digit 5
typedef
struct
{
int
num
，
denom
；
}
frac_t
，
*
frac
；
typedef
enum
{
C_NUM
=
0
，
C_ADD
，
C_SUB
，
C_MUL
，
C_DIV
}
op_type
；
typedef
struct
expr_t
*
expr
；
typedef
struct
expr_t
{
op_type
op
；
expr
left
，
right
；
int
value
；
}
expr_t
；
void
show_expr
（
expr
e
，
op_type
prec
，
int
is_right
）
{
const
char
*
op
；
switch
（
e
->
op
）
{
case
C_NUM
：
printf
（
“%d”
，
e
->
value
）；
return
；
case
C_ADD
：
op
=
“ + ”
；
break
；
case
C_SUB
：
op
=
“ - ”
；
break
；
case
C_MUL
：
op
=
“ × ”
；
break
；
case
C_DIV
：
op
=
“ / ”
；
break
；
}
if
（（
e
->
op
==
prec
&&
is_right
）
||
e
->
op
<
prec
）
printf
（
“（”
）；
show_expr
（
e
->
left
，
e
->
op
，
0
）；
printf
（
“%s”
，
op
）；
show_expr
（
e
->
right
，
e
->
op
，
1
）；
if
（（
e
->
op
==
prec
&&
is_right
）
||
e
->
op
<
prec
）
printf
（
“）”
）；
}
void
eval_expr
（
expr
e
，
frac
f
）
{
frac_t
left
，
right
；
if
（
e
->
op
==
C_NUM
）
{
f
->
num
=
e
->
value
；
f
->
denom
=
1
；
return
；
}
eval_expr
（
e
->
left
，
&
left
）；
eval_expr
（
e
->
right
，
&
right
）；
switch
（
e
->
op
）
{
case
C_ADD
：
f
->
num
=
left
。
num
*
right
。
denom
+
left
。
denom
*
right
。
num
；
f
->
denom
=
left
。
denom
*
right
。
denom
；
return
；
case
C_SUB
：
f
->
num
=
left
。
num
*
right
。
denom
-
left
。
denom
*
right
。
num
；
f
->
denom
=
left
。
denom
*
right
。
denom
；
return
；
case
C_MUL
：
f
->
num
=
left
。
num
*
right
。
num
；
f
->
denom
=
left
。
denom
*
right
。
denom
；
return
；
case
C_DIV
：
f
->
num
=
left
。
num
*
right
。
denom
；
f
->
denom
=
left
。
denom
*
right
。
num
；
return
；
default
：
fprintf
（
stderr
，
“Unknown op： %d
\n
”
，
e
->
op
）；
return
；
}
}
int
solve
（
expr
ex_in
［］，
int
len
）
{
int
i
，
j
；
expr_t
node
；
expr
ex
［
n_cards
］；
frac_t
final
；
if
（
len
==
1
）
{
eval_expr
（
ex_in
［
0
］，
&
final
）；
if
（
final
。
num
==
final
。
denom
*
solve_goal
&&
final
。
denom
）
{
show_expr
（
ex_in
［
0
］，
0
，
0
）；
return
1
；
}
return
0
；
}
for
（
i
=
0
；
i
<
len
-
1
；
i
++
）
{
for
（
j
=
i
+
1
；
j
<
len
；
j
++
）
ex
［
j
-
1
］
=
ex_in
［
j
］；
ex
［
i
］
=
&
node
；
for
（
j
=
i
+
1
；
j
<
len
；
j
++
）
{
node
。
left
=
ex_in
［
i
］；
node
。
right
=
ex_in
［
j
］；
for
（
node
。
op
=
C_ADD
；
node
。
op
<=
C_DIV
；
node
。
op
++
）
if
（
solve
（
ex
，
len
-
1
））
return
1
；
node
。
left
=
ex_in
［
j
］；
node
。
right
=
ex_in
［
i
］；
node
。
op
=
C_SUB
；
if
（
solve
（
ex
，
len
-
1
））
return
1
；
node
。
op
=
C_DIV
；
if
（
solve
（
ex
，
len
-
1
））
return
1
；
ex
［
j
］
=
ex_in
［
j
］；
}
ex
［
i
］
=
ex_in
［
i
］；
}
return
0
；
}
int
solve114
（
int
n
［］）
{
int
i
；
expr_t
ex
［
n_cards
］；
expr
e
［
n_cards
］；
for
（
i
=
0
；
i
<
n_cards
；
i
++
）
{
e
［
i
］
=
ex
+
i
；
ex
［
i
］。
op
=
C_NUM
；
ex
［
i
］。
left
=
ex
［
i
］。
right
=
0
；
ex
［
i
］。
value
=
n
［
i
］；
}
return
solve
（
e
，
n_cards
）；
}
int
main
（）
{
int
i
，
j
，
n
［］
=
{
1
，
1
，
4
，
5
，
1
，
4
}；
//宇 宙 元 素
printf
（
solve114
（
n
）
？
“=114
\n
”
：
“No solution
\n
”
）；
//訴 訟 開 始
}
修改程式碼中的“114”為任意想要的數字。最後來一張
邏 輯 自 洽
Q 。 E 。 D 。
參考資料：
24 game/Solve - Rosetta Code
知乎使用者2018-03-20 03:09:16不錯，以後我們lab再招undergrad的時候我就給undergrad送上一杯紅茶，然後拿這個當演算法考題
羅宸2018-03-20 22:24:20哈哈， 這個問題看著傻傻的， 但是寫寫其實還蠻有意思的。 從比較General的角度看， 是個生成語法樹的問題。 但是這個語法樹有比較特殊的地方， 就是所有運算子都是二元的， 這是可以簡化演算法的一個關鍵的特徵。
先放結論， 用 （+）， （-）， （*） 三種運算子就可以。
下面是我首先寫出來的程式碼：
import
Data。List
numbers
ops
（
x
：
xs
）
=
e
（
x
：
xs
）
++
e
（
-
x
：
xs
）
where
e
［
x
］
=
［
x
］
e
xs
=
［
x
`
op
`
y
|
op
<-
ops
，
k
<-
［
1
。。
length
xs
-
1
］，
x
<-
e
（
take
k
xs
），
y
<-
e
（
drop
k
xs
）］
solve
xs
ops
=
map
head
。
group
。
sort
。
filter
（
>=
0
）
。
filter
（
<
100
）
$
numbers
ops
xs
solution
=
length
（
solve
［
1
，
1
，
4
，
5
，
1
，
4
］
［（
+
），
（
-
），
（
*
）］）
這個思路是這樣的：
由於有所有算符都是二元的這個特徵， 於是可以聯想到加括號問題， 咱們先考慮語法樹的可能個數：
f
1
=
1
—— 1個元素加括號的方式有1種
f
2
=
k
—— 2個元素加括號的方式有1種， 然後中間的符號選擇 （假設） 有 k 種
f
3
=
f
2
*
f
1
*
k
+
f
1
*
f
2
*
k
—— 3個元素， 要麼分別處理前2個和後1個， 然後中間加括號； 要麼分別處理前1個和後2個， 然後中間加括號
。。。
f
n
=
（
f
（
n
-
1
）
*
f
1
+
f
（
n
-
2
）
*
f
2
+
。。。
+
f
1
*
f
（
n
-
1
）
）
*
k
—— n個元素時， 列舉 （n-1） 種可能的切分位置
聰明的你一定早就看出來了， 這個遞迴關係非常像卡特蘭數， 事實上：
f
n
=
catalan
（
n
-
1
）
*
k
^
（
n
-
1
）
（
n
=
0
，
1
，
2
。。。
於是我們很快地知道， f 6 = catalan 5 * k^5 ， 假設我們用 加，減，乘 這 3 種運算子的話， 那麼語法樹就會有 42 * 3^5 = 10206 種， 不嚴謹地說， 這一萬多棵語法樹求值得到 ［0。。99］ 這一百種值的可能性還是比較高的。 然後把上面的遞迴公式中的計算語法樹個數改為計算語法樹可能求值結果的集合， 就得到了最初版本的程式碼了。 （當然包含了一個開頭可能加負號的trick）
當然寫完上面的程式碼之後， 在GHCi中執行發現， solution = 99， 說明漏了一種 ：）
GHCi
>
［
0
。。
99
］
\\
（
solve
［
1
，
1
，
4
，
5
，
1
，
4
］
［（
+
），
（
-
），
（
*
）］）
［
53
］
漏掉的是53。 然後咱就去找
@呂蒙正Incubator
貼的表。。。 （大霧
然後發現， 53 果然是透過一種比較trick的方式實現的， 就是把最前邊的兩個1並作了11。。。
好吧， 於是引入這個神奇的操作， 咱就得到了下面這坨正確 （卻並不漂亮） 的版本：
import
Data。List
numbers
ops
（
x
：
xs
）
=
e
（
x
：
xs
）
++
e
（
-
x
：
xs
）
where
e
［
x
］
=
［
x
］
e
xs
=
［
read
（
concat
（
map
show
xs
））］
++
［
x
`
op
`
y
|
op
<-
ops
，
k
<-
［
1
。。
length
xs
-
1
］，
x
<-
e
（
take
k
xs
），
y
<-
e
（
drop
k
xs
）］
solve
xs
ops
=
map
head
。
group
。
sort
。
filter
（
>=
0
）
。
filter
（
<
100
）
$
numbers
ops
xs
solution
=
length
（
solve
［
1
，
1
，
4
，
5
，
1
，
4
］
［（
+
），
（
-
），
（
*
）］）
這個時候 solution 終於等於100了。 呼。。。 於是咱們終於證實乘方操作是不必要的了， 加減乘已經足夠。。。 （當然還需要 “並” ， 以及開頭加負號這樣的兩個trick操作。。）
最後咱又想， 有沒有可能用少於三種符號， 比如用兩種符號， 就得到100種可能的結果呢？ 於是就有了下面的程式碼 （其實這裡把運算子拿出來單獨定義純粹是為了它能被打印出來 。。。）：
import
Data。List
type
Number
=
Int
data
Op
=
Add
|
Sub
|
Mul
|
Div
|
Pow
deriving
（
Show
，
Eq
，
Enum
）
eval
：：
Op
->
Number
->
Number
->
［
Number
］
eval
Add
x
y
=
［
x
+
y
］
eval
Sub
x
y
=
［
x
-
y
］
eval
Mul
x
y
=
［
x
*
y
］
eval
Div
x
y
=
［
x
`
div
`
y
|
y
/=
0
］
eval
Pow
x
y
=
［
x
^
y
|
y
>=
0
］
numbers
ops
（
x
：
xs
）
=
e
（
x
：
xs
）
++
e
（
-
x
：
xs
）
where
e
［
x
］
=
［
x
］
e
xs
=
［
read
（
concat
（
map
show
xs
））］
++
concat
［
eval
op
x
y
|
op
<-
ops
，
k
<-
［
1
。。
length
xs
-
1
］，
x
<-
e
（
take
k
xs
），
y
<-
e
（
drop
k
xs
）］
solve
xs
ops
=
map
head
。
group
。
sort
。
filter
（
>=
0
）
。
filter
（
<
100
）
$
numbers
ops
xs
powerset
：：
［
a
］
->
［［
a
］］
powerset
［］
=
［
［］
］
powerset
（
x
：
xs
）
=
let
pxs
=
powerset
xs
in
pxs
++
map
（
x
：
）
pxs
enumOps
=
［（
ops
，
length
（
solve
［
1
，
1
，
4
，
5
，
1
，
4
］
ops
））
|
ops
<-
powerset
［
Add
。。
Pow
］］
以下是每組運算子對應的所有語法樹可能求值結果的數量：
GHCi
>
enumOps
［（
［］
，
0
），（［
Pow
］，
2
），（［
Div
］，
7
），（［
Div
，
Pow
］，
15
），（［
Mul
］，
1
），（［
Mul
，
Pow
］，
9
），（［
Mul
，
Div
］，
28
），（［
Mul
，
Div
，
Pow
］，
37
），（［
Sub
］，
39
），（［
Sub
，
Pow
］，
56
），（［
Sub
，
Div
］，
55
），（［
Sub
，
Div
，
Pow
］，
68
），（［
Sub
，
Mul
］，
88
），（［
Sub
，
Mul
，
Pow
］，
92
），（［
Sub
，
Mul
，
Div
］，
91
），（［
Sub
，
Mul
，
Div
，
Pow
］，
93
），（［
Add
］，
16
），（［
Add
，
Pow
］，
57
），（［
Add
，
Div
］，
59
），（［
Add
，
Div
，
Pow
］，
71
），（［
Add
，
Mul
］，
94
），（［
Add
，
Mul
，
Pow
］，
97
），（［
Add
，
Mul
，
Div
］，
99
），（［
Add
，
Mul
，
Div
，
Pow
］，
99
），（［
Add
，
Sub
］，
56
），（［
Add
，
Sub
，
Pow
］，
79
），（［
Add
，
Sub
，
Div
］，
68
），（［
Add
，
Sub
，
Div
，
Pow
］，
85
），（［
Add
，
Sub
，
Mul
］，
100
），（［
Add
，
Sub
，
Mul
，
Pow
］，
100
），（［
Add
，
Sub
，
Mul
，
Div
］，
100
），（［
Add
，
Sub
，
Mul
，
Div
，
Pow
］，
100
）］
篩選出結果數量等於100的項：
GHCi
>
filter
（（
==
100
）
。
snd
）
enumOps
［（［
Add
，
Sub
，
Mul
］，
100
），（［
Add
，
Sub
，
Mul
，
Pow
］，
100
），（［
Add
，
Sub
，
Mul
，
Div
］，
100
），（［
Add
，
Sub
，
Mul
，
Div
，
Pow
］，
100
）］
於是最後發現， 使用加減乘這三種算符， 確實已經是最少的了。
當然我知道你們還想要看打印出的結果。。。 不過貼結果到這裡太有礙觀瞻了。 所以貼到gist吧：
Gist： 列印結果的版本
以上程式碼， 想玩的話， 也不妨下載個GHC （Haskell語言的編譯器） 執行一下哦 ：）
混分女孩輝夜姬2018-03-21 08:38:43
如圖，這個公式能表示大於等於1的所有整數
