4Clojure hard题目-106

池塘仙人 发布于 2012/11/20 23:55
阅读 325
收藏 1

4Clojure是一个面向clojure初学者的在线答题网站,问题从易到难,一步步辅助初学者深入了解clojure

Number Maze

Difficulty: Hard
Topics: numbers


Given a pair of numbers, the start and end point, find a path between the two using only three possible operations:
  • double
  • halve (odd numbers cannot be halved)
  • add 2
Find the shortest path through the "maze". Because there are multiple shortest paths, you must return the length of the shortest path, not the path itself.
test not run
(=1(__1 1)) ; 1
test not run
(=3(__3 12)); 3 6 12
test not run
(=3(__12 3)); 12 6 3
test not run
(=3(__5 9)) ; 5 7 9
test not run
(=9(__9 2)) ; 9 18 20 10 12 6 8 4 2
test not run
(=5(__9 12)); 9 11 22 24 12

题目要求从一个数装换到另一个数需要的最小步骤数,装换的方法有3种:*2 /2 +2

这里只需要简单的应用广度优先的思想,用一个值记录需要的步骤数,每一次对条件中的点应用三种方法,并把计数+1,当第一次发现终点时,就是其解。

如果用深度优先,先找一条通路,保存起来,再找另一条,不断重复,则面临两个问题:存在的通路是有限条吗?能保证最短的通路没有被遗漏吗?

(fn [f t]
  (loop [from #{f} length 1]
    (if (contains? from t)
        length
      (recur 
       (set
        (concat;这里是最简的解答,如果要削减重复计算,可保存旧值并每次把旧值过滤掉
         (map (partial + 2) from)
         (map (partial * 2) from)
         (map #(/ % 2) (filter even? from))))
          (inc length)))))


加载中
返回顶部
顶部