Concrete Mathematics
Posted: Sat Jun 28, 2008 4:28 am
While this isn't a book about Lisp at all, I am thoroughly enjoying it and the fact that mathematics are so easily portable to lisp. Take this problem for example:
How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? or...
What is the maximum number Ln of regions defined by n lines in the plane?
I then tried some small cases on paper, and eventually came to the conclusion that
L0 = 1
Ln = Ln-1 + n for n>0
Because:
With 0 cuts, you have one big slice.
With every next cut you make, you increase the amount of slices by the number of the cut you're making.
0 cuts: 1 big slice
1 cut: 2 slices
2 cuts: 4 slices
3 cuts: 7 slices
The formula
L0 = 1
Ln = Ln-1 + n for n>0
is most easily portable to lisp code as follows:
I've only just started reading this book, and I'm loving it already. I'll post some more examples later, like the closed form solution to this problem (that is: non-recurrent).
How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? or...
What is the maximum number Ln of regions defined by n lines in the plane?
I then tried some small cases on paper, and eventually came to the conclusion that
L0 = 1
Ln = Ln-1 + n for n>0
Because:
With 0 cuts, you have one big slice.
With every next cut you make, you increase the amount of slices by the number of the cut you're making.
0 cuts: 1 big slice
1 cut: 2 slices
2 cuts: 4 slices
3 cuts: 7 slices
The formula
L0 = 1
Ln = Ln-1 + n for n>0
is most easily portable to lisp code as follows:
Code: Select all
(defun L (n)
(cond ((= n 0) 1)
((> n 0) (+ (L (1- n)) n))))