On Wed, Mar 24, 2010 at 8:21 PM, Glen Rubin <[email protected]> wrote:
> I wrote the following code to produce a lazy sequence of the triangle
> numbers. (triangle numbers are the series of numbers: 1, 1+2, 1+2+3,
> etc...)
>
> (defn tri-nums []
> "prduce a lazy sequence of triangle numbers"
> (let [triangles (map #(range 1 %) (iterate inc 2))]
> (map #(reduce + %) triangles)))
>
> However, I now have produced a large triangle number (76576500) and
> want to know which triangle number it is (e.g. the first, second,
> third, etc...)
Why not index the sequence with the 'indexed' function up front?
> So, I wrote the following code which should accept a triangle number
> as input and tell you which one it is in the series:
>
> (defn which-tri [z]
> (loop [x 1 y (first (tri-nums))]
> (cond
> (= y z)
> x
> (< y z)
> (recur (inc x) (first (rest (tri-nums))))
> true
> (println "no such tri-num"))))
>
>
> The problem is that this function works for the first two triangle
> numbers (1, 3), but then just sits there doing nothing on any higher
> (6, 10, etc...).
You're calling rest at the same rate as inc in your loop, which means
that x is increasing at a linear rate while y is increasing at a
roughly quadratic rate. Thus as soon as y overtakes x, x never has a
hope of catching up.
Like I said above, you probably don't need to do this to find the
index. But supposing you did, this is an instance of a more general
problem: determining the index (if any) of a number in a sorted
sequence. Something like this:
(defn index-in-sorted-seq [x s]
(loop [s s, i 0]
(when (seq s)
(cond
(= x (first s)) i
(> x (first s)) (recur (rest s) (inc i))
:else nil))))
-Per
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
To unsubscribe from this group, send email to
clojure+unsubscribegooglegroups.com or reply to this email with the words
"REMOVE ME" as the subject.
