[racket] 27.5.4 Gaussian Elimination
On Nov 22, 2010, at 4:17 PM, Ken Hegeland wrote:
> The problem is 27.5.4 can be found at
> http://htdp.org/2003-09-26/Book/curriculum-Z-H-34.html#node_sec_27.5
>
> I am still on the beginning of this extended exercise and I am entirely lost. I know how it works but can't get anything even remotely close. I was able to create subtract from 27.5.2, but triangulate eludes me after a few days of thinking. My first thought is to make something that takes either a (listof(listof numbers)), or 3 (listof numbers), and have it output the first part of triangulation.
>
> So for the lolon of '((2 2 3 10)(2 5 12 31)(4 1 -2 1)) I want to produce an answer of
> '((2 2 3 10)(3 9 21)(-3 -8 -19))
>
> I feel like applying subtract to first and second in lolon produces (3 9 21), but I am not sure how to make it continue on the rest of the list. I tried (subtract2(subtract(first lolon)(second lolon))), which really doesn't work and it seems obvious to me just from glancing at it.
>
> I am thinking back to how I did merge sort, create a function that merges 2 lists, apply it to the first and second items in a lolon, then recursively apply it to the rest of the list.
>
> In subtract2 my final goal is to apply subtract to the first and second item, then recursively apply it to first and rest of the list, but I can't figure out how to get this.
>
> I know the real question has to do with applying this over and over to any lists of equal length, until you drop the first position to 0, and maybe I am heading in the wrong direction, but it seems easier to break it into smaller problems. I really want to complete this problem before moving on with the book but I can't find anything that works, everything I think of causes infinite loops and freezes my computer for 10 minutes.
>
> _________________________________________________
> For list-related administrative tasks:
> http://lists.racket-lang.org/listinfo/users
Say you're starting from here: (a rectangle)
> ((2 2 3 10)
> (2 5 12 31)
> (4 1 -2 1))
One step -- as described in the book gets you here:
> ((2 2 3 10)
> (0 3 9 21)
> (0 -3 -8 -19))
If you cut the 0s out from row 2 through N, you get closer to the triangle:
> ((2 2 3 10)
> (3 9 21)
> (-3 -8 -19))
This isn't quite a triangle yet. So how do you repeat this process?
Eureka: find a sub-rectangle to which you could apply this trick again. Do so until you're out of naturally chosen sub-rectangles.
Practically speaking, this means that you subtract the second row -1 times from the last:
>
> ((2 2 3 10)
> (3 9 21)
> (1 2))
Now you have got a triangle. Of course if the matrix has many more rows you need to repeat this step many more times.
The good news: Typing in the ideas presented above -- assuming you have internalized Parts I - IV of HtDP -- will take you about as much time as typing the email. Well, perhaps I am slow typist -- Matthias