精华区文章阅读

发信人: sino (茶水博士), 信区: Theory
标  题: Re: 24点有穷举之外的算法吗?
发信站: 哈工大紫丁香 (Sun Aug 27 13:28:59 2000), 转信

发信人: daniel (飞翔鸟), 信区: algorithm
发信站: NJU Lily BBS (Sun Apr 11 11:58:40 1999), 转信

【在 zhch (Zhch from NJU) 的大作中提到: 】
: 没有.
: 仅有算法好坏之分,
: 但都属于穷举.

Yeah,这个问题太简单了。问题空间规模太小。

每个数都有10种取法，所以共10^4种，进行运算就相当于对四个数排序

之后插入运算符，四个数共有24种取法，四则运算符只能取三个，共有

4^3种取法，则10^4*24*4^3=15360000 < 2^24=16777216。也就是说该问题

空间复杂度小于2^24，如果考虑到同构之类的情况，实际空间还要更小。

对这样的问题，随便什么搜索算法都能解。和国际象棋10^210、围棋10^761

的复杂度相比，这个问题实在是算不了什么。

另外，原问题提法好象不妥，不应是“有限次”四则运算，而应是每个数和

运算的中间结果都只能使用一次。否则，哪怕是四个1也能算出24来（似乎

所有的数都能算出来吧？我没证明，不知道是不是）。
: 【在 Younger (迷惘的人 ) 的大作中提到: 】
: :     任给4个 1 ~10上问�,判断能否经过有限步四则运算得到24.
: :    各位高人,请不吝赐教.
: :     as title.

--
迷失在都市的旷野
享受孤独的梦想
体会寂寞的光荣
※ 修改:．fib 於 Aug 27 13:26:38 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．南京大学小百合 bbs.nju.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: fib.bbs@bbs.nju.edu.]

Algorithm 版 (精华区)