General Programming Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingGeneral Programming Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old March 10th, 2005, 08:41 PM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 14
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!

Reply With Quote
  #2  
Old March 11th, 2005, 09:00 AM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
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

Reply With Quote
  #3  
Old March 11th, 2005, 09:12 AM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 14
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 }

Reply With Quote
  #4  
Old March 11th, 2005, 09:16 AM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
ah, I didn't catch those restrictions...
I figured it wasn't that easy =)

Reply With Quote
  #5  
Old March 11th, 2005, 03:28 PM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
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.

Reply With Quote
  #6  
Old March 11th, 2005, 04:02 PM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
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.

Reply With Quote
  #7  
Old March 11th, 2005, 04:24 PM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
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!!

Reply With Quote
  #8  
Old March 11th, 2005, 04:44 PM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
Here's a similar question.
The lucky seven

(thanks google)

Reply With Quote
  #9  
Old March 11th, 2005, 05:05 PM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
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!!

Reply With Quote
  #10  
Old March 12th, 2005, 04:36 AM
Cirus Cirus is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Mar 2005
Posts: 296 Cirus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 13 h 30 m 11 sec
Reputation Power: 13
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.

Reply With Quote
  #11  
Old March 12th, 2005, 11:07 AM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 14
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

Reply With Quote
  #12  
Old March 12th, 2005, 02:59 PM
Cirus Cirus is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Mar 2005
Posts: 296 Cirus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 13 h 30 m 11 sec
Reputation Power: 13
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?

Reply With Quote
  #13  
Old March 13th, 2005, 08:43 PM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
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.

Reply With Quote
  #14  
Old March 14th, 2005, 09:07 AM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
I just want to know the resulting fractions

Reply With Quote
  #15  
Old March 14th, 2005, 03:48 PM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
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!!

Reply With Quote
  #16  
Old March 14th, 2005, 10:56 PM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 14
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

Reply With Quote
  #17  
Old March 14th, 2005, 10:57 PM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 14
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

Reply With Quote
  #18  
Old March 15th, 2005, 08:42 AM
MadCowDzz's Avatar
MadCowDzz MadCowDzz is offline
I'm Internet Famous
Dev Articles Frequenter (2500 - 2999 posts)
 
Join Date: Jan 2003
Location: Toronto, Canada
Posts: 2,886 MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level)MadCowDzz User rank is Lance Corporal (50 - 100 Reputation Level) 
Time spent in forums: 1 Week 16 h 19 m 35 sec
Reputation Power: 18
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...

Reply With Quote
  #19  
Old March 15th, 2005, 10:57 AM
Anibal Anibal is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jan 2005
Posts: 176 Anibal User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 4 h 20 m 48 sec
Reputation Power: 14
Damn it!! Now I'll have to get me a girl!

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingGeneral Programming Help > One for you math gurus


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap