CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Dec 2012
    Posts
    3

    nested for loops

    hi,

    i am currently trying to teach my self c++. Workign fin so far, but now i have hit a break with this problem:
    (translated by me, sorry)

    1) you are given a large number x and a subset of smaller numbers a<b<c<d. Find the smallest amount of a,b,c,d possible to reach x.
    So you are supposed to find a combination like "5*a + 3*b + 1*d" == x, where 5+3+1 is the smallest possible.

    I thought a lot about this, no success. :/
    I would have otped for bruteforce testing all possible combinations, but the book says no bruteforcing.

    The example is taken from the "advanced" part of my book, chapter "loops and algorithms". A solution is supposed to be on an accompanying cd, but i lost that ages ago.

    any hints for me?


    p.s. coudlnt think of a proper title, sorry...

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: nested for loops

    Sounds like a pretty typical exercise. Forgetting programming for a minute, how would you do it with a pencil and paper.

    Let's say the number is 55, and the smaller numbers are 1, 2, 3, 4. What steps would you take to solve it? Once you can answer that, then you can figure out how to code it. To give you a clue, the solution uses division and remainders.

  3. #3
    Join Date
    Dec 2012
    Posts
    3

    Re: nested for loops

    i do not know.
    The straight forward approach would be:

    1) a = x/a;
    2) b = (x%a)/b
    3) c = ((x%a)%c)/d
    ...


    But that doesnt work, as you have to be able to "undo" the algorithm, when you find that there`s leftover at the end (assuming there is no a,b,c,d == 1).
    Also, wired numbers may have "exceptions", no? Where above algorithm will miss the optimal solution. (although i couldnt think of an example right now, i ll keep trying )

    if it`s a typical exercise, do you know of a tutorial or exemplary solution? I am still sort of clueless and wasnt able to find anything. :S

  4. #4
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: nested for loops

    a recursive or backtracking algorithm seems like the obvious first approach i'd go for.

    From a pure mathematical p.o.v. I don't think there is method for solving this (it's a fitting problem), and that means brute forcing.

    Of course there are gradients in what you consider "brute force". A recursive or backtracking solution would just be "smart" approaches to brute forcing (you attempt to try the most likely solutions first), but in a worst case scenario, you could be ending up trying every possible combination anyway.
    The fact it is about "loops and algorithms", would lead me to believe the idea is in fact to try a backtracking approach.


    You didn't mention the title of the book.
    Most book publishers, or the authors host accompanying cd's/disks on their website.
    Even if they don't, someone else that bought the book may have the disk on his website.

  5. #5
    Join Date
    Apr 1999
    Posts
    27,449

    Re: nested for loops

    Quote Originally Posted by skidrive View Post
    1) you are given a large number x and a subset of smaller numbers a<b<c<d. Find the smallest amount of a,b,c,d possible to reach x.
    So you are supposed to find a combination like "5*a + 3*b + 1*d" == x, where 5+3+1 is the smallest possible.
    Let me try to rephrase this with a real life problem:

    A country (USA) has coins in the denonimation of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents. It takes 100 cents to make 1 dollar. What is the least number of coins needed to equal a certain dollar and cents amount?

    In other words, you have 5 coin types, so what is the least amount of coins you would need jingling in your pocket to equal, say 5 dollars and 30 cents? Or 3 dollars and 10 cents? or no dollars and 75 cents? etc.

    If this is not the same problem, then clarify. If it is the same problem, then does this help you visualize more clearly the goal?

    Regards,

    Paul McKenzie

  6. #6
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: nested for loops

    An important difference with money is that the currency makers will (usually ) be nice enough to provide us with the 1 coin value.
    This means you can solve the problem mathematically without loops, but it may not be optimal. In that approach you would be 'greedy' and assume that you take as much of a bigger coin values as possible and the pass the remainder onto the smaller coins.

    Using your coins in your above post: Suppose. You need 13cents
    No 50 cents fit
    No 25 cents fit
    1x 10 cents coin fits, leaving 3
    No 5 cents fit
    3x 1cent fits.
    you needed 4 coins.

    a simple set of divisions, modulo's and subtractions will solve this.

    But it's not guaranteed optimal.
    Suppose there existed a 4 cents coin and you needed to get 8 cents total.
    Using the 'greedy' approach above, you would end up with 1x 5cents and 3x 1cents. (4 coins)
    where the optimal is 2x 4cents (2 coins).


    This calculated 'greedy' approach also only has a guaranteed answer if the 1 coin value is present.

    In the more generalized problem (as stated in the OP which does not guarantee the presense of 1) there might be no answer from the greedy calculation, even when there is a possible answer.

    note that in the absense of 1, some values will not be possible to achieve even with trying all the possibilities.
    Last edited by OReubens; December 14th, 2012 at 05:33 AM.

  7. #7
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: nested for loops

    rereading the OP. This was actually about finding the optimal solution (lowest a+b+c+d), and not about finding a solution.

    This actually makes it impossible to solve without going for a brute force approach when you try to break down the large number into it's constituent smaller parts. You will need to try alternative solutions to the first one you find to make sure there are no more optimal ones.

    That doesn't mean there's no efficient way to solve this with a computer, if you can afford to spend some memory on it.
    The idea is to turn the problem upside down.
    Rather than asking "how do I break a large number into the smallest amount of smaller bits".
    You turn it upside down into "what large values do I progressively get when I combine smaller bits".

    In an algorithm rough outline).
    Make an array at least the size of the large number you want to get.
    this array needs to have an indicator for "empty", a reference/list of values of what small bits make this value. a count of the number of bits to make this value.
    empty the array
    start filling the array with all the possible values you can make with 1 'small bit'.
    you then combine each of the already filled in answers of count 1, with each of the single values to make all the possible answers of count 2. fill your answer in the array if there's not already an answer there.
    repeat to combine all the count 2 answers with each of the single values to make all the possible count 3 answers.
    repeat until you have an answer for the larger value you were seeking.


    example.
    suppose you have numbers 1 4 and 5. And you're looking to find an answer for making 13.
    you make an array of size 9.
    at index 1 you fill in the answer "1" of count 1
    at index 4 you fill in the answer "4" of count 1
    at index 5 you fill in the answer "5" of count 1

    you then combine all the count 1 answers with all the single values.
    for-loop over the array finding each count 1 answer, and add each of the possible answers
    index 1 has a count 1, we will combine with all the values
    at index 2 we fill in "1+1" of count 2
    we ignore "1+4" because we already have a better solution there
    at index 6 we fill in "1+5"
    index 4 has a count of 1, combine with each of the values
    we ignore 4+1 already have a 5
    at index 8 we fill in "4+4"
    at index 9 we fill in "4+5"
    index 5 has a count of 1, combine with each of the values
    we ignore 5+1 already have a 6
    we ignore 5+4 already have a 9
    at index 10 we fill in "5+5"

    next we for-loop over the array finding all the count 2 answers and combining with each of the 3 values.
    etc...

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured