CODEWITHSUNDEEP
c++loopsassert
Chris Seltzer
Chris Seltzer

Reputation: 171

Understanding loop invariants

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?

Upvotes: 0

Views: 1209

Answers (1)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145239

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.

Upvotes: 1

Related Questions