Otto's C++ Corner
OttoDestruct
Join Date: 2002-11-08 Member: 7790Members
Join Date: 2002-11-08 Member: 7790Members
in Off-Topic
Er... I don't get this assignment (not really assignment more of a quiz, not a full program):
Eucidean Algorithm
1: Find the remainder of a divided by b
2: Assign a the value of b
3: Assign b the value of the remainder
4: if b = 0 then quit, a is the greatest common divisor
5: Otherwise, go to step a and repeat
Define function gcd() that returns an int and has two int arguments. gcd() returns the greatest common divisor of its arguments. Be sure to state the assumptios on the values of actual arguments.
Er... ok.. so am I only supposed to use two variables?
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Define function gcd() that returns an int and has two int arguments. <!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
And WTH state the assumptions?
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Be sure to state the assumptios on the values of actual arguments.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
I see no way to even get past the first part without using three variables (remainder, a, b). If the assignment means in the function header that I'm supposed to have two ints that makes more sense. Other than that I know I can just use a loop to accomplish everything.
Eucidean Algorithm
1: Find the remainder of a divided by b
2: Assign a the value of b
3: Assign b the value of the remainder
4: if b = 0 then quit, a is the greatest common divisor
5: Otherwise, go to step a and repeat
Define function gcd() that returns an int and has two int arguments. gcd() returns the greatest common divisor of its arguments. Be sure to state the assumptios on the values of actual arguments.
Er... ok.. so am I only supposed to use two variables?
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Define function gcd() that returns an int and has two int arguments. <!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
And WTH state the assumptions?
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->Be sure to state the assumptios on the values of actual arguments.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
I see no way to even get past the first part without using three variables (remainder, a, b). If the assignment means in the function header that I'm supposed to have two ints that makes more sense. Other than that I know I can just use a loop to accomplish everything.
Comments
<!--c1--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->
int gcd (int a, int b)
{
int remainder;
remainder = a / b;
a = b;
b = remainder;
while (b == 1)
{
cout << "Enter A: ";
cin >> a;
cout << "Enter B: ";
cin >> b;
remainder = a/b;
a = b;
b = remainder;
}
return a;
}
<!--c2--></td></tr></table><span class='postcolor'><!--ec2-->
We'll give you two hints:
1) recursion
2) you're assuming that (a >= b), right?
And the following line is not correct, can you figure out why?
remainder = a / b;
You'd be surprised how the most boring computer science things can end up being useful in a game.
We'll give you two hints:
1) recursion
2) you're assuming that (a >= b), right?
And the following line is not correct, can you figure out why?
remainder = a / b; <!--QuoteEnd--> </td></tr></table><span class='postcolor'> <!--QuoteEEnd-->
No clue why the line isn't correct because I included a main function to setup the variables to be sent in, and it works fine.
We'll give you two hints:
1) recursion
2) you're assuming that (a >= b), right?
And the following line is not correct, can you figure out why?
remainder = a / b; <!--QuoteEnd--> </td></tr></table><span class='postcolor'> <!--QuoteEEnd-->
You COULD use recursion, but recursion is most of the times less efficient (yet smaller in code) and harder to understand... Just stick with loops unless you wanna proclaim how "elite" you are <!--emo&:)--><img src='http://www.unknownworlds.com/forums/html/emoticons/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif'><!--endemo-->
We'll give you two hints:
1) recursion
2) you're assuming that (a >= b), right?
And the following line is not correct, can you figure out why?
remainder = a / b; <!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
You COULD use recursion, but recursion is most of the times less efficient (yet smaller in code) and harder to understand... Just stick with loops unless you wanna proclaim how "elite" you are <!--emo&:)--><img src='http://www.unknownworlds.com/forums/html/emoticons/smile.gif' border='0' style='vertical-align:middle' alt='smile.gif'><!--endemo--> <!--QuoteEnd--> </td></tr></table><span class='postcolor'> <!--QuoteEEnd-->
The assignment was to use loops anyway.
remainder = a / b; <!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
No clue why the line isn't correct because I included a main function to setup the variables to be sent in, and it works fine.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
The remainder of a divided by b is:
a % b
Also, why does gcd() ask for input?
I thought gcd()'s only purpose was to return the greatest common divisor of a and b.
Thats why.
*Edit*
Uh.. yea.. *slaps self for forgetting mod*
Thats why.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
Let me guess...
You teacher forces you to put a and b in gcd()'s parameter list, even though a and b are only used locally?
Sorry if my questions sound stupid, but the programming style they teach you is very weird.
Thats why.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
Let me guess...
You teacher forces you to put a and b in gcd()'s parameter list, even though a and b are only used locally?
Sorry if my questions sound stupid, but the programming style they teach you is very weird. <!--QuoteEnd--> </td></tr></table><span class='postcolor'> <!--QuoteEEnd-->
It was part of the assignment to assume a and b were being passed into the function.
But yes, use modulous. I can't think of any other way to get a remainder in C++ off the top of my head.
Actually, as a tangent, CrystalSnake, -is- there any way to perform a modulous operation without using modulous?
Of course, I have to know Java, not C++, but its still evil.
Also, where in that description does it say to take in new values at every iteration in a loop?
AND the way you set up that loop it'll only return the correct answer if it gets the right answer immediately, and in that case (with your code) it won't ask for new values.
The way it seems to me, from your initial description:
1. You can use additional variables if you need them.
2. focus on the loop, always the loop
3. don't ask for new values in the function.
4. just use the variables passed to the function and output the answer.
5. check the logic of that boolean statement in your while loop, it isn't helping.
Of course, I have to know Java, not C++, but its still evil. <!--QuoteEnd--> </td></tr></table><span class='postcolor'> <!--QuoteEEnd-->
Um... right.....
The problem I am having is seeing what your code is doing. I mean, gcd implies that it should return the Gratest Common Factor of A and B, but your code doesn't do that. Why are you taking input in the loop? Why aren't you using recursion? It makes sense for this problem....
You can write (a % b) like this:
a - ((a / b) * b)
Also, where in that description does it say to take in new values at every iteration in a loop?
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
I assumed it had to be as I programmed it so you don't get an infinite loop.
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->AND the way you set up that loop it'll only return the correct answer if it gets the right answer immediately, and in that case (with your code) it won't ask for new values.<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
Whats the point of asking for new values if its already correct? That would be like passing 1 + 1 = 2 in then asking you to do it again.
<!--QuoteBegin--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->
5. check the logic of that boolean statement in your while loop, it isn't helping.
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
Logic? What logic doesnt work about while ( b == 1)?
Variable: Declared locally by the procedure
Parameter: Passed from outside the procedure
<!--c1--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->
int make_four(int x) {
int y = x / (x / 2);
return y + 2;
}
<!--c2--></td></tr></table><span class='postcolor'><!--ec2-->
The above is a really pointless little function that takes one parameter (x), returns an int (y + 2), and declares one local variable (y).
In my main function (elsewhere in the code), I might have something like this:
<!--c1--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->
int input;
cin >> input;
cout << make_four(input);
<!--c2--></td></tr></table><span class='postcolor'><!--ec2-->
The value of 'input' in the main function will determine what the value of 'x' is within make_four. When make_four returns the cout << will receive the value that was given to return.
For assumptions, think about what would make the code not work correctly. For example, the division in make_four can result in a divide by zero, which is a Bad Thing , and we assume the user would never be so nasty as to give us that input.
Hopefully this clears something up, if not, then meh...
edit: note that the loop may be infinite if the assumptions for the values aren't correct, in which case the algorithm fails, and so would your code. You may want to check for that at the start of the function. Of course, there is also the problem that you would need to pre-specify an error value for return.... meh, just leave the check out and indicate the assumption.
Thats exactly the point I was making. The loop only runs when b == 1. Otherwise it just skips it and returns a, as its already done those calculations and found a to be the greatest common divisor. Why would you want to prove twice that a is the greatest common divison? Other note - yes every assignment we have assumes correct data is entered unless we're told otherwise to dummy proof it.
For powers of 2 there is. For instance if you want to do i%8 you could write i & 7 , just remember that the number after & is 1 smaller than the modulous you want and that it only works for modulous that are powers of 2.
Monkey wrench time. And here is the reason why you always look for non-trivial test cases:
Let's try a=6 b=9. The greatest common divisor of 6 and 9 is 3. Calling your provided gcd(6,9) returns 9 (assuming the remainder = a / b bug is fixed). 9 most definitely does not divide 6. Thus (b==1) is not the correct loop condition. Hint for the correct loop conditions:
<!--QuoteBegin--OttoDestruct+Nov 6 2003,08:29 PM--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (OttoDestruct @ Nov 6 2003,08:29 PM)</td></tr><tr><td id='QUOTE'><!--QuoteEBegin-->4: if b = 0 then quit, a is the greatest common divisor
5: Otherwise, go to step a and repeat
<!--QuoteEnd--></td></tr></table><span class='postcolor'><!--QuoteEEnd-->
Let "step a" = "step 1" for clarity.
The algorithm was handed to you on a silver platter for this one. The entire assignment appears to be "given 5 steps can you convert each step one by one to code?" So given
<!--c1--></span><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'><!--ec1-->int gcd(int a, int b);
<!--c2--></td></tr></table><span class='postcolor'><!--ec2-->
as the declaration of the function (which is what you have), you know that a and b are passed in a arguments to the function. From there just take it one line at a time - there's nothing fancy to do. No input, no output. Just crank. You're making it way too hard on yourself...