Re: Algorithms Homework Help?!?!

[Adam Beneschan <adam@irvine.com>]

On Tuesday, January 15, 2013 1:52:44 PM UTC-8, willmann817 wrote:
> I am given an Array that contains the number of M&Ms of each color I have.  Each index in the array represents a different color.  I am also given an Integer of the number of children I am having at a birthday party. 
> 
> --THE CHILDREN MUST ALL HAVE THE SAME NUMBER OF M&MS
> --EACH CHILD MUST ONLY HAVE 1 COLOR OF M&MS
> 
> Given an array containing the number of M&Ms I have in each available color, and the number of kids, determine the maximum number of M&Ms you can put in each goody bag. 
> 
> For example, with 11 red M&Ms, 9 blue M&Ms, and 5 M&Ms, you could give 5 children a maximum of 4 M&Ms each. You could not give each child 5 M&Ms without at least one child receiving M&Ms of different colors. 


I think the first approach should be to put the M&M's away.  If you give them to small children, they will get the chocolate all over their hands and then get it all over your furniture, curtains, pets, etc.  Don't buy the "melts in your mouth, not in your hand" garbage.  Maybe you're not old enough to remember that slogan.  But it doesn't work with little kids.  Trust me.


>   I was given a hint that said to write a helper function Groups(M : Integer; A : Int_Array) that takes a number of M&Ms and the array and returns how many groups I can make of M pieces of M&Ms. 
> 
> (For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, Groups(3) would return 7.)


Ah, so you ate all the M&Ms yourself and decided to give them Legos instead.  Good, that's what I would have done.

  
> Then do my binary search based on this helper function(Posted below). 
> 
> --This problem MUST include Binary Search in some way.
> 
> 
> 
> I completed that but now I am stuck on the main function(also posted below) it is totally wrong cause I can't even pass the first test case:
> 
> 
> 
> 	function Groups(Bricks : Integer; A: Int_Array) return Integer is
> 	counter : Integer := 0;
> 	begin
> 		for I in A'Range loop
> 			counter := counter + (A(I)/Bricks);
> 		end loop;
> 	return counter;
        end Groups;  -- (obviously this line belonged up here)
> 
>    function Candy(Kids : Integer; MsPerColor : Int_Array) return Integer is	
> 	lo : Integer := 1;
> 	hi : Integer := 50000;
> 	mid : Integer;
> 	begin
> 		for I in MsPerColor'Range loop
> 			if  MsPerColor(I) > hi then
> 				hi :=  MsPerColor(I);
> 			end if;
> 
> 			if  MsPerColor(I) < lo then
> 				lo :=  MsPerColor(I);
> 			end if;
> 		end loop;
> 
> 		mid := (lo+hi)/2;
> 		while Groups(mid, MsPerColor) /= Kids loop
> 			mid := (lo+hi)/2;
> 			if Groups(mid, MsPerColor) > Kids then
> 				hi := mid;
> 			else
> 				lo := mid;
> 			end if;
> 		end loop;
> 	return mid;
>    end Candy;

I won't give the whole answer, since this is a homework assignment.  But it will probably help to put some lines in the code to output some values.  I did that myself, since I was in too big a hurry to study your code carefully.  I added these after the "while" line:

text_io.put("lo=" & integer'image(lo));
text_io.put(" hi=" & integer'image(hi));
text_io.put(" mid=" & integer'image(mid));
text_io.put_line(" groups returns " & integer'image(Groups(mid, MsPerColor)));

If you do this, I think you'll quickly figure out what the first mistake is.

As for the second mistake: the Put statements should help you see that too.  You need to think about: what kinds of quantities do your variables lo, hi, and mid represent, and what kind of quantity does the first parameter to Groups represent.  They don't match, which is a problem.

Good luck, and hope this helps,

                             -- Adam