PDA

View Full Version : Programming/algorithm help


LoD
21-05-2004, 15:21:06
OK, so basically I have as input 2-4 sets of lengths, each defininig a right-angled triangle. My task is to see whether one can build a square or a rhombus out of those triangles.
Now my problem is that I have defined several cases of when that condition is true. However, I'm torn between just doing a check of those cases, or doing a shitload of work for a sensibly-conditioned enumeration.
The cases I've found out are coming in a moment...

LoD
21-05-2004, 15:38:04
Rhombus (so can be applied for square as well, since every square is a rhombus) :
http://civ.org.pl/gwiazda/r3.png
http://civ.org.pl/gwiazda/r1.png
http://civ.org.pl/gwiazda/romb2.gif

Square:
http://civ.org.pl/gwiazda/q1.png
http://civ.org.pl/gwiazda/q2.png
http://civ.org.pl/gwiazda/q3.png

So, have I blatantly omitted a lot of cases (not counting the ones that would require identical checking instructions) and should do an enumeration, or should I just verify for the above cases and let it go?


Help, anyone? Please?

Gary
21-05-2004, 16:21:51
Wish I could offer some useful help, but ... from my life experience I tend to plump for the, "just to the simple check" type of option, and then wonder why I flunked while others got through on the "shitload of work" option.

Unsure what you're doing it for. College ? You'll proabably start doing the simple check, get cold feet and then do the lot, and be glad you did afterwards.

LoD
21-05-2004, 17:18:57
Uni. It's an "Introduction to Programming" course, so it shouldn't require a large amount of work to do it well. I'm still torn, since the enumaration would take a shitload of time (and by that I mean mostly execution time) and would be quite complex to make - and it's generally used when you don't know which answer set is the right one, or don't have enough conditions to discriminate against the wrong ones.
The emphasis on this task is actually to incorporate someone else's program into your own anyway...

Sir Penguin
21-05-2004, 19:50:09
One thing you could do would be to put pairs of equal-length lines from different triangles into an equivalence class. If the set of lines doesn't divide up evenly into equivalence classes, then the set of lines is unsolvable.

Then, pick two equivalence classes to represent the sides of the rhombus (opposite sides are equal, and thus in an equivalence class), and try to arrange the other equivalence classes as single lines of the same length as the class elements. If you can't find a solution, move on to a different pair of equivalence classes for the outside, and continue doing that until you've used all equivalent outside pairs.

I'm not sure how you'd check the inside. I guess you'd have to make sure that all the inside equivalence classes fit together, and that the shell (outermost) classes are the same as the two outside classes that you picked before.

That's really inefficient and hard, but you'll get bonus points for being obscure.

SP

LoD
21-05-2004, 20:19:03
Not here you won't - any bonus you get come from students :)...

Likewise, you could calculate the side length of a "potential" rhombus or square and work on that - then again, the biggest problem is AGAIN checking the inside...