- Forum
- General C++ Programming
- Different ways of suming specific number
Different ways of suming specific numbers to gain 100
hi
i want to write a code to show how many ways i can sum up 5 different numbers so the answer would be 100.
here are the numbers :
2,5,10,20,50
i can repeat them as much as i want to for example :
1:50+50
2:20+20+20+20+20
3:50+20+20+10
but i have no idea where to begin,i don't want the actual code just a hint so i know where to begin?
i want to write a code to show how many ways i can sum up 5 different numbers so the answer would be 100.
here are the numbers :
2,5,10,20,50
i can repeat them as much as i want to for example :
1:50+50
2:20+20+20+20+20
3:50+20+20+10
but i have no idea where to begin,i don't want the actual code just a hint so i know where to begin?
This is a thinking problem, so alas, you must think about it yourself.
Your professor will probably show the most optimal solution after you turn in your assignment.
Your professor will probably show the most optimal solution after you turn in your assignment.
closed account (zb0S216C)
2 + 20 also gives you 100.
Is the goal just to find as may computations as possible?
Wazzak
Is the goal just to find as may computations as possible?
Wazzak
Last edited on
closed account (zb0S216C)
| L B wrote: |
|---|
| 2 + 20 is 22, unless they changed math without me? |
People created a concept that makes people laugh; it's called a joke.
Wazzak
Last edited on
This is an interesting problem.
I think you can use this:
create 6 nested "for"s to count answers.
I think you can use this:
| 2*a + 5*b + 10*c + 20*d + 50*e = 100 Find number of answer series for this equation. |
create 6 nested "for"s to count answers.
When ever I don't know how to program something right away, I think: "How would I do this in real life?" Then I figure out exactly what I did to get the right answer. Then "explain" that to the computer via C++.
Last edited on
I started a solution for this in the morning, as I too thought it was interesting. Then I had to break work, then I came back for 2 hours. I have a solution attempt that repeats several combinations and doesn't necessarily go through all summands. :-S This is harder than usual, or I'm becoming a moron. :-P
Last edited on
This problem is simple enough, so brute-forcing works fine. Using this approach, I got the result in just 0.000017 seconds.
Last edited on
you have the mathematical properties of addition and multiplication.
are they commutative? yes
a + b = b + a
a * b = b * a
are they associative? yes
(a + b) + c = a + (b + c)
(a * b) * c = a * (b * c)
are they distributive? partly
a * (b + c) = (a * b) + (a * c)
a + (b * c) != (a + b) * (a + c)
this question is rather about a simplified version of metamorphic coding where you have the simplest version:
50 + 50
and you want to iterate through all the versions until you reach the most complex one:
50 * 2 (in an addition form)
however here the situation is way simper because you dont have nop operators that dont do anything. as opposd to metamorphic code
are they commutative? yes
a + b = b + a
a * b = b * a
are they associative? yes
(a + b) + c = a + (b + c)
(a * b) * c = a * (b * c)
are they distributive? partly
a * (b + c) = (a * b) + (a * c)
a + (b * c) != (a + b) * (a + c)
this question is rather about a simplified version of metamorphic coding where you have the simplest version:
50 + 50
and you want to iterate through all the versions until you reach the most complex one:
50 * 2 (in an addition form)
however here the situation is way simper because you dont have nop operators that dont do anything. as opposd to metamorphic code
Last edited on
Modulus should be your friend in finding the answer you seek...
IN other words, if you base number has a remainder of 0 from the current sum, you can make that number divisible by that number, unlocking a possible combination of numbers to equate to 100. Start with you base case, prove and inductive case, and you have the foundation for your algorithm. Obviously the largest case is 50+50, correct?
100%50 = 0
50+50 = 100 // yay! first combination found!
(50%20) = 10 // not a possibility in this iteration
50%10 = 0 // a possible combination
50+10+10+10+10+10 // yay! another combination
50+40+10 // reduced but same result since we are popping a 10 for eval
(10%50) = 10 // nope
(10%20) = 10 // nope
(10%5) = 0 // yay!!!!
50+40+(5+5)
etc... etc.... Almost like Discreet Mathematics!!! I would evaluate it like a quasi tree like form.
IN other words, if you base number has a remainder of 0 from the current sum, you can make that number divisible by that number, unlocking a possible combination of numbers to equate to 100. Start with you base case, prove and inductive case, and you have the foundation for your algorithm. Obviously the largest case is 50+50, correct?
100%50 = 0
50+50 = 100 // yay! first combination found!
(50%20) = 10 // not a possibility in this iteration
50%10 = 0 // a possible combination
50+10+10+10+10+10 // yay! another combination
50+40+10 // reduced but same result since we are popping a 10 for eval
(10%50) = 10 // nope
(10%20) = 10 // nope
(10%5) = 0 // yay!!!!
50+40+(5+5)
etc... etc.... Almost like Discreet Mathematics!!! I would evaluate it like a quasi tree like form.
Last edited on
Another approach is to try to solve the general problem
How many ways to sum up to N, using the numbers in the set S.
@mcrist: ¿why did you group those 10 to form the 40? ¿Could you explain it for 7 as number and {2,3,5} as the set?
How many ways to sum up to N, using the numbers in the set S.
@mcrist: ¿why did you group those 10 to form the 40? ¿Could you explain it for 7 as number and {2,3,5} as the set?
because finding the possibility of the division of those additives from 40 needs to be a possibility to acquire one of the sums to 100. such as 50+20+20+10 since 40%20 = 0 so 20*2 = 40. This is because you have to treat that sum as a portion that you should evaluate. You would have to evaluate everything until you get the smallest possible result, which is 5 added 20 times.
Last edited on
My algorithm is similar and still doesn't yield the correct result. I am sorting the summands, meaning I have 5 before 2. But the smallest combination found is 20 * 5 as you say, but it is not the smallest possible one: The smalest is 2 + 2 + 2 ..... 50 times. So it has to be more complex than this.
Also, to avoid duplicates I am thinking I need to hash the combinations and check the collection before adding new ones.
Also, to avoid duplicates I am thinking I need to hash the combinations and check the collection before adding new ones.
Topic archived. No new replies allowed.