|
 |
|
Dev Articles Community Forums
> Programming
> General Programming Help
|
One for you math gurus
Discuss One for you math gurus in the General Programming Help forum on Dev Articles. One for you math gurus General Programming Help forum discussing Perl, Python, Scripting and/or any languages that do not fit into any of the categories above.
|
|
 |
|
|
|

Dev Articles Community Forums Sponsor:
|
|

March 10th, 2005, 08:41 PM
|
Contributing User
|
|
Join Date: Feb 2005
Posts: 36
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 15
|
|
One for you math gurus
I'm having problems coming up with an algorythm to solve the following problem:
I need to find three fractions that add up to exactly 1.
They each must have a single digit numerator and a double digit denominator.
I can only use the digits 1-9 and each digit can only be used once.
Example:
1/23 + 4/56 + 7/89 = ???
or
9/12 + 8/34 + 7/56 = ???
HELP!
|

March 11th, 2005, 09:00 AM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
1/2 + 1/4 + 1/4 = 1
Now, you said double digit denominator w/ single digit numerator...
any permutation of the above should cut it.
5/20 + 6/24 + 5/10 = 1
|

March 11th, 2005, 09:12 AM
|
Contributing User
|
|
Join Date: Feb 2005
Posts: 36
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 15
|
|
Quote:
Originally Posted by MadCowDzz
1/2 + 1/4 + 1/4 = 1
Now, you said double digit denominator w/ single digit numerator...
any permutation of the above should cut it.
5/20 + 6/24 + 5/10 = 1
|
Yes, but 0 is not a valid digit in this case, and you reused both 2 and 5. All the digits from 1..9 must be used once and only once. I've found a way to do it using permutations, but it is not a very "smart" way to do it. You simply plug the digits 1..9 into an array, then loop while there are more permutations of the array. Inside the loop you simply plug the digits into the fractions, do the crunching and it either adds up or it doesn't. Then you get the next permutation.
BTW this is the first time I've used permuations. Prety cool stuff. If you take the array:
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } the next permutaion would be
{ 1, 2, 3, 4, 4, 6, 7, 9, 8 }
you can continue all the way until you get
{ 9, 8, 7, 6, 5, 4, 3, 2, 1 }
|

March 11th, 2005, 09:16 AM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
ah, I didn't catch those restrictions...
I figured it wasn't that easy =)
|

March 11th, 2005, 03:28 PM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
Carefull with permutations!! 362.880 is a very high number to test!!
I've come up with an idea...I just don't want to post it until finished...  .
Are you sure you're not leaving anything out? I mean...no other restrictions?
I always have one equation with 5 variables...it's imposible to solve. Damn it....I love challenges (I won't sleep till it's done!!)
Not an easy job...but good things in life (such as women) never are!!
Good Luck!
Anibal.
|

March 11th, 2005, 04:02 PM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
lol, me and my un-math skills...
i've written down every combination on of numbers paper...
perhaps the ultimate goal would be to write a program to figure it out...
alas, i'm lazy.
|

March 11th, 2005, 04:24 PM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
You're not crazy...I am! I have been using Algebra, and vectorial Analysis (I've also tried lineal Transformations...just for the fun of it) Something is left out....I'm sure of it. Otherwise is a matter of test and error (that's not an algorithm).
that bloody thing is not going to beat me!!
|

March 11th, 2005, 04:44 PM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
|

March 11th, 2005, 05:05 PM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
I saw it...although, there's a very important diference! We have here 3 terms and the sum equals 1. So, it very hard to estimate anything..since the first fraction is obvoulsy < 1. Then, to our surprise, the seccond and third are also < 1 (and between them, still < 1). It's imposible to limit the number to overcome by the second and third fractions, since we cant estimate how high the first fraction would be (in the example, the second fraction had to be > 6....here the second and third combined have to be > 0.?) see my point?
The answer though, has to be somewhere around there!!
Heil Google!!
|

March 12th, 2005, 04:36 AM
|
Contributing User
|
|
Join Date: Mar 2005
Posts: 296
Time spent in forums: 1 Day 13 h 30 m 11 sec
Reputation Power: 14
|
|
Try this:
1. Start
2. Take three var, iA,iB and iC.
a. Choose any digit and assign it to iA.
b. Choose digit from the remaining eight numbers and assign to iB
c. Repeat step 2b with remaining seven digits and assign to iC.
3. Form number of iB and iC as iC*10 + iB
4. Divide iA by product of step3 to get fraction.
5. Repeat steps 2 - 4 with remaining six numbers and add the resultant to step 4.
6. Repeat step five with remaining 4 numbers.
7. If sum is 1 then print "Success" and goto step 8 else go to step 2.
8. Stop.
Let me know if it solves your problem.
|

March 12th, 2005, 11:07 AM
|
Contributing User
|
|
Join Date: Feb 2005
Posts: 36
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 15
|
|
Quote:
Originally Posted by Cirus
Try this:
1. Start
2. Take three var, iA,iB and iC.
a. Choose any digit and assign it to iA.
b. Choose digit from the remaining eight numbers and assign to iB
c. Repeat step 2b with remaining seven digits and assign to iC.
3. Form number of iB and iC as iC*10 + iB
4. Divide iA by product of step3 to get fraction.
5. Repeat steps 2 - 4 with remaining six numbers and add the resultant to step 4.
6. Repeat step five with remaining 4 numbers.
7. If sum is 1 then print "Success" and goto step 8 else go to step 2.
8. Stop.
Let me know if it solves your problem.
|
Thanks for the suggestion. I was telling MadCowDzz that I've found a way to do it using permutations, but it is not a very "smart" way to do it. You simply plug the digits 1..9 into an array, then loop while there are more permutations of the array. Inside the loop you simply plug the digits into the fractions, do the crunching and it either adds up or it doesn't. Then you get the next permutation.
BTW this is the first time I've used permuations. Prety cool stuff. If you take the array:
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } the next permutaion would be
{ 1, 2, 3, 4, 4, 6, 7, 9, 8 }
you can continue all the way until you get
{ 9, 8, 7, 6, 5, 4, 3, 2, 1 }
The challenge is this is not a very intelligent way to go about it. It just seems like there should be a way using successive approximations or something but I'm just not that good with math.
BTW - After plugging this in it seems there is only one solution: 9/12 + 7/68 + 5/34
|

March 12th, 2005, 02:59 PM
|
Contributing User
|
|
Join Date: Mar 2005
Posts: 296
Time spent in forums: 1 Day 13 h 30 m 11 sec
Reputation Power: 14
|
|
This is what I suggested for. I am considering all digits,then choose 3 using 9C3 , then again 3 to give 6C3 for second number.This is followed by choosing remaining for third number and simply adding up to match 1.
Agree that algo is not good.Is there any better way of doing?
|

March 13th, 2005, 08:43 PM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
This is a problem that has to do with logic...not so much maths! The trick is to limit the posibilities for the second and third fractions. That way, the algo becomes much shorter and efective! I've tried to work it out with Mathmatical Analysis, but it's imposible to come up with restrictions for the value of numbers (and not repeating....is quite insane).
Good Luck
Anibal.
|

March 14th, 2005, 09:07 AM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
I just want to know the resulting fractions 
|

March 14th, 2005, 03:48 PM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
Don't we all?...I'll work it out.....no problem is going to beat me! I shall prevail, but first....I shall learn how to spell!! 
|

March 14th, 2005, 10:56 PM
|
Contributing User
|
|
Join Date: Feb 2005
Posts: 36
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 15
|
|
Quote:
Originally Posted by MadCowDzz
I just want to know the resulting fractions 
|
It was at the bottom of my response to Cirus above: 9/12 + 7/68 + 5/34
|

March 14th, 2005, 10:57 PM
|
Contributing User
|
|
Join Date: Feb 2005
Posts: 36
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 15
|
|
Quote:
Originally Posted by Anibal
Don't we all?...I'll work it out.....no problem is going to beat me! I shall prevail, but first....I shall learn how to spell!! 
|
It was at the bottom of my response to Cirus above: 9/12 + 7/68 + 5/34
|

March 15th, 2005, 08:42 AM
|
 |
I'm Internet Famous
|
|
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886
 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 19
|
|
lol, that's what you get for skimming of posts with too much text...
well, that satisfies my curiousity...
Is that the best way to approach the answer?
[Or was that your original question?]
PS - Sounds like you ruined Anibal's plans for the weekend... 
|

March 15th, 2005, 10:57 AM
|
Contributing User
|
|
Join Date: Jan 2005
Posts: 176
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 15
|
|
Damn it!! Now I'll have to get me a girl!
|
Developer Shed Advertisers and Affiliates
Thread Tools |
Search this Thread |
|
|
Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|