# While loops round two

• Oct 9th 2007, 05:12 PM
speakeasy
While loops round two
Sorry for reposting, but these are some new questions that spin off my old post.

Okay can anyone explain while loops to me in a non-computer like way or as non-computer like as it can get. I understand the logic of while loops, but whenever I put it to practice I get all sorts of confused.

I really just need someone to clarify this whole concept for me. My teacher taught us using charts and I get confused which column of the chart holds my answer. Basically I do not know which number I want. I think I am just confusing my self more writing this entry.

Here is an example where I just can't grasp the whole idea:

Problem:

For which values of the integer b do each of the following algorithms terminate?

a) begin
k:=b
while k<5 do
k:=2k-1
end

I keep getting the answer b>(or equal to)3, but the book's answer is b>(or equal to)2.

and then

c) begin
k:=b
while k<5 do
k:=2k+1
end

Now I get the answer b>(or equal to) 2, and the book's answer is something like b E(as in the element/set E) natural numbers.

So you see I am not getting this.
• Oct 9th 2007, 11:56 PM
Opalg
Quote:

Originally Posted by speakeasy
Here is an example where I just can't grasp the whole idea:

Problem:

For which values of the integer b do each of the following algorithms terminate?

a) begin
k:=b
while k<5 do
k:=2k-1
end

I keep getting the answer b>(or equal to)3, but the book's answer is b>(or equal to)2.

and then

c) begin
k:=b
while k<5 do
k:=2k+1
end

Now I get the answer b>(or equal to) 2, and the book's answer is something like b E(as in the element/set E) natural numbers.

So you see I am not getting this.

The difference between your answers and the book's is that you seem to be looking at whether the algorithm terminates after just one pass through the loop. In fact, you are asked whether the algorithm eventually terminates.

In Example a), if b=2 then k starts with the value 2. This is less than 5, so we pass through the loop and k emerges with the value 3. This is less than 5, so we have to pass through the loop again, and this time k emerges with the value 5. This fails the k<5 test, so at this stage the algorithm terminates.

On the other hand, if b=0 then as k goes through the loop it emerges with the value -1 (after the first pass), then -3 (after the second pass), then successively -7, -15, -31, ... . It's clear that after each pass k gets more and more negative, so it will never be greater than 5 and the algorithm will never terminate.

In Example c), suppose for example that b=0. Then the successive values of k as it passes through the loop are 0, 1, 3, 7, and at that point the algorithm terminates.

On the other hand, if k<0 then 2k+1<0, so if b is negative then k has a negative initial value, and will remain negative no matter how many times it passes through the loop. Therefore if b<0 then the program will not terminate.