hey, all~
I've got a pumpkin head, I can't figure this out. see..
"(tree n) (n>=0)"
>(tree 0)
0
>(tree 1)
(0(1)(2))
>(tree 2)
(0(1(3)(4))(2(5)(6)))
>(tree 3)
(0(1(3(7)(8))(4(9)(10)))(2(5(11)(12))(6(13)(14)))))
......
that is "tree"
I've tried everything I can do, but I couldn't make it.
anybody can help me out?? I'm about to give up :(
I guess it is concerned about recursive function...
On Thu, Oct 03, 2002 at 11:58:25PM +0900, K. Miller wrote:
> hey, all~
>
> I've got a pumpkin head, I can't figure this out. see..
>
>
> "(tree n) (n>=0)"
>
> >(tree 0)
> 0
> >(tree 1)
> (0(1)(2))
> >(tree 2)
> (0(1(3)(4))(2(5)(6)))
> >(tree 3)
> (0(1(3(7)(8))(4(9)(10)))(2(5(11)(12))(6(13)(14)))))
> ......
>
> that is "tree"
Interesting pattern. Seems that the two children of every node are
equal to (1+ (* 2 node)) and (+ 2 (* 2 node)) respectively.
Properly formatting the results makes its structure much clearer:
* (tree 0)
0
* (tree 1)
(0 (1)
(2))
* (tree 2)
(0 (1 (3)
(4))
(2 (5)
(6)))
* (tree 3)
(0 (1 (3 (7)
(8))
(4 (9)
(10)))
(2 (5 (11)
(12))
(6 (13)
(14))))
[It seems to me that the stated result for (tree 0) is wrong, however.
It should be (0) according to the rest of the pattern.]
Each node in the tree consists of a 3 element list:
(value child-1 child-2)
and the children may be omitted.
The problem seems to want you to construct a tree by building up each
level recursively. The argument provided is the maximum depth of the
tree, and thus determines your stopping point.
The recursive case of this algorithm (when not at the maximum depth)
should construct a node with 2 children, calculating the appropriate
values for them (and of course applying the function recursively to
obtain the child nodes).
The base case of the algorithm should construct a node with no children.
Remember, in all cases, you are returning a ``node'' as I have defined
it above.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
I thought it was just enumerating the nodes breadth-first, starting from
zero.
k,c
Matthew Danish wrote:
> On Thu, Oct 03, 2002 at 11:58:25PM +0900, K. Miller wrote:
>
>>hey, all~
>>
>>I've got a pumpkin head, I can't figure this out. see..
>>
>>
>>"(tree n) (n>=0)"
>>
>>
>>>(tree 0)
>>
>>0
>>
>>>(tree 1)
>>
>>(0(1)(2))
>>
>>>(tree 2)
>>
>>(0(1(3)(4))(2(5)(6)))
>>
>>>(tree 3)
>>
>>(0(1(3(7)(8))(4(9)(10)))(2(5(11)(12))(6(13)(14)))))
>>......
>>
>>that is "tree"
>
>
> Interesting pattern. Seems that the two children of every node are
> equal to (1+ (* 2 node)) and (+ 2 (* 2 node)) respectively.
>
> Properly formatting the results makes its structure much clearer:
>
> * (tree 0)
> 0
>
> * (tree 1)
> (0 (1)
> (2))
>
> * (tree 2)
> (0 (1 (3)
> (4))
> (2 (5)
> (6)))
>
> * (tree 3)
> (0 (1 (3 (7)
> (8))
> (4 (9)
> (10)))
> (2 (5 (11)
> (12))
> (6 (13)
> (14))))
>
> [It seems to me that the stated result for (tree 0) is wrong, however.
> It should be (0) according to the rest of the pattern.]
>
> Each node in the tree consists of a 3 element list:
>
> (value child-1 child-2)
>
> and the children may be omitted.
>
> The problem seems to want you to construct a tree by building up each
> level recursively. The argument provided is the maximum depth of the
> tree, and thus determines your stopping point.
>
> The recursive case of this algorithm (when not at the maximum depth)
> should construct a node with 2 children, calculating the appropriate
> values for them (and of course applying the function recursively to
> obtain the child nodes).
>
> The base case of the algorithm should construct a node with no children.
>
> Remember, in all cases, you are returning a ``node'' as I have defined
> it above.
>
K. Miller wrote:
> hey, all~
>
> I've got a pumpkin head, I can't figure this out. see..
>
>
> "(tree n) (n>=0)"
>
>
>>(tree 0)
>
> 0
>
>>(tree 1)
>
> (0(1)(2))
>
>>(tree 2)
>
> (0(1(3)(4))(2(5)(6)))
>
>>(tree 3)
>
> (0(1(3(7)(8))(4(9)(10)))(2(5(11)(12))(6(13)(14)))))
> ......
>
> that is "tree"
Do you mean "that is what the function i am supposed to write is
supposed to do"?
>
>
> I've tried everything I can do, but I couldn't make it.
could you show us one or two best efforts so far?
kenny
clinisys
"K. Miller" <········@hanmail.net> writes:
> I've tried everything I can do, but I couldn't make it.
As the poet said, 'Only God can make a tree' -- probably because it's
so hard to figure out how to get the bark on.
(Woody Allen)
Hope this helps
-dan
--
http://ww.telent.net/cliki/ - Link farm for free CL-on-Unix resources
"K. Miller" <········@hanmail.net> wrote in message ·················@news1.kornet.net...
> hey, all~
>
> I've got a pumpkin head, I can't figure this out. see..
>
>
> "(tree n) (n>=0)"
>
> >(tree 0)
> 0
> >(tree 1)
> (0(1)(2))
> >(tree 2)
> (0(1(3)(4))(2(5)(6)))
> >(tree 3)
> (0(1(3(7)(8))(4(9)(10)))(2(5(11)(12))(6(13)(14)))))
> ......
>
> that is "tree"
>
>
> I've tried everything I can do, but I couldn't make it.
>
> anybody can help me out?? I'm about to give up :(
>
> I guess it is concerned about recursive function...
It appears that the function should return a complete binary tree of n levels,
where the root node is at level 0, and where the nodes are numbered in
a top-down left-to-right breadth-first manner by consecutive integers
beginning with 0.
My Lisp is rusty and I'm sure this can be done more elegantly, certainly
more efficiently, but here's a solution. If it looks like Scheme code translated
to CL, you would be right!
(defun make-tree (n-levels)
(if (= n-levels 0)
`(0)
(make-tree-aux (- n-levels 1)
(make-leaves (make-level-n-nodes n-levels)))))
(defun make-tree-aux (level-n bottom-up-tree)
(if (= level-n 0)
(cons 0 bottom-up-tree)
(let ((level-n-nodes (make-level-n-nodes level-n)))
(make-tree-aux (- level-n 1)
(mapcar #'(lambda (parent siblings)
(cons parent siblings))
level-n-nodes
(make-siblings bottom-up-tree))))))
(defun make-level-n-nodes (level-n)
(let ((num-nodes (expt 2 level-n)))
(make-level-n-nodes-aux (- num-nodes 1) num-nodes)))
(defun make-level-n-nodes-aux (start num)
(if (= num 0)
'()
(cons start (make-level-n-nodes-aux (+ start 1) (- num 1)))))
(defun make-leaves (level-n-nodes)
(mapcar #'(lambda (node) `(,node)) level-n-nodes))
(defun make-siblings (level-n-nodes)
(if (null level-n-nodes)
'()
(cons `(,(car level-n-nodes) ,(cadr level-n-nodes))
(make-siblings (cddr level-n-nodes)))))
> (make-tree 3)
(0 (1 (3 (7) (8)) (4 (9) (10))) (2 (5 (11) (12)) (6 (13) (14))))
Hope this helps.
Regards,
jag
On Thu, Oct 03, 2002 at 08:24:12PM +0000, John Gilson wrote:
> [a lot of code! ouch]
My version of this (based on the description in my previous post in this
thread) is:
;; invariant: n >= 0
(defun tree (n &optional (level 0) (value 0))
(if (< level n)
(list value
(tree n (1+ level) (1+ (* 2 value)))
(tree n (1+ level) (+ 2 (* 2 value))))
(list value)))
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
Matthew Danish wrote:
> On Thu, Oct 03, 2002 at 08:24:12PM +0000, John Gilson wrote:
>
>>[a lot of code! ouch]
>
>
> My version of this (based on the description in my previous post in this
> thread) is:
>
> ;; invariant: n >= 0
> (defun tree (n &optional (level 0) (value 0))
> (if (< level n)
> (list value
> (tree n (1+ level) (1+ (* 2 value)))
> (tree n (1+ level) (+ 2 (* 2 value))))
> (list value)))
>
>
I prefer this slight variation:
(defun tree (n &optional (value 0))
(if (= n 0)
(list value)
(list value
(tree (- n 1) (+ 1 (* 2 value)))
(tree (- n 1) (+ 2 (* 2 value))))))
Seems simpler to dispense with the level variable. Now, rather than
checking if we are at the last level, we just ignore the concept of
levels and build a tree of size n. It's just semantics, but it feels
cleaner to me. This makes a tree of size n just two trees of size n-1
joined with a root node.
Justin Dubs
John Gilson wrote:
> My Lisp is rusty and I'm sure this can be done more elegantly, certainly
> more efficiently, but here's a solution. If it looks like Scheme code translated
> to CL, you would be right!
>
> (defun make-tree (n-levels)
> (if (= n-levels 0)
> `(0)
> (make-tree-aux (- n-levels 1)
> (make-leaves (make-level-n-nodes n-levels)))))
<snip>
As an aside, this program has a little usability problem (quite common
in example code): it dies with stack overflow, if the parameter isn't a
positive integer.
--