0

A college freshman I know taking an intro to computer science class asked me for help on one of his homework assignments. I read through a few times and I'm embarrassed to admit I don't know what they're asking for. Here's the question:

Given below is the outline of a loop. Finish the program so that it will read in x and y values, validate them (by continuing to prompt the user until they enter the correct values), and run such that the given assertions will always be true. Include the loop invariant assertion at the four points in your program where it must be true. You may not use the multiplication operator, except in the given assert(...) statements.

assert(x>0 && y>0);
while(...)
{
    assert(sum == i*(x+1));
    ...
    ...
}
assert(sum == y*(x+1));

I didn't know what a loop invariant was so I googled and read the Wikipedia article. From that I gather the first assert statement is telling me that I should not allow x and y to ever be negative for the duration of the loop. Truthfully I'm stuck at this point. Can someone help me understand what they're asking for here?

Chris Seltzer
  • 171
  • 2
  • 13
  • I guess i is the loop variable? One readin of x and y has to be before the loop. Or is there a starting value for x and y? Is there an initial value for the sum? – ChaosCakeCoder Sep 28 '12 at 04:33
  • If any of the `assert`s evaluate to false your program won't run. Take `i` as some variable that changes every time the loop is executed. – Hindol Sep 28 '12 at 04:40
  • 1
    You might wanna refer to this thread... http://stackoverflow.com/q/3221577/1410711 – Recker Sep 28 '12 at 04:43
  • @ChaosCakeCoder You know literally everything I know about the question. – Chris Seltzer Sep 28 '12 at 04:57

1 Answers1

1

The description of the homework is incomplete to the point of being almost meaningless.

However, one can infer that it is about letting the user enter two positive integers, and computing the product without using the multiplication operator, as a sum.

Generally, a product of positive integers can be defined as sum in this way:

2 times b = b + b
(a + 1) times b = b + (a times b)

with the cases for operands 1 and 0 inferred by requiring the general rules to hold.

The similarity of the last equation, to the asserts you show, is probably not a coincidence.

Anyway, it works nicely as a loop invariant. As you increase the loop variable the loop invariant still holds and ensures that you have a nice product around. So that when the loop is finished, the loop invariant's constraint on that product, plus the value of the loop variable at this point, ensures that you have a product that is (easily reduced to) x*y.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331
  • Thanks for the help. The observation about computing the product of positive integers makes sense. I suppose I'm confused about what the loop is trying to accomplish. Is it just looking for any two arbitrary positive numbers? Is the "loop invariant assertion" assert(sum == i*(x+1));? – Chris Seltzer Sep 28 '12 at 05:05
  • assuming my theory about the homework is correct, the loop should be "computing the product of positive integers" entered by the user. so it is not "looking for any two arbitrary positive numbers". and yes the loop invariant would be that assert. :-) – Cheers and hth. - Alf Sep 28 '12 at 05:20