Question

In: Computer Science

Find a loop invariant (I) for the following while loop with the post-condition {Q: S=1}, where...

Find a loop invariant (I) for the following while loop with the post-condition

{Q: S=1}, where S is an integer and the operator / represents an integer division.

Show your work step by step to receive full credit.

         while (S > 1) do
              S = S / 2;
         }

Solutions

Expert Solution

Loop invariant can be defined as a condition which will always be true. This property must be satisfied throughout every iteration of the loop.

We have the post-condition:

Q: S = 1

The given loop checks if the value of 'S' is greater than 1 or not. If it is true, then it divides 'S' by 2 and this process is repeated in every iteration. The while loop condition will fail when the value of 'S" is one or less. At that case, the value of 'S' will never be less than one as it is integer in nature. Loop invariant does not depend on the state of the iterative condition. It always remains true irrespective of the iterative condition which can be true or false.

The post-condition must be true after the execution of the while loop condition.

So, one loop invariant we can determine from the given relation is:

S > 1 [the while loop will be executed only when 'S' is greater than one, not equal to one]

Please comment in case of any doubt.
Please upvote if this helps.


Related Solutions

According to the loop invariant theorem, a valid loop invariant ?(?)I(n) must have the property that...
According to the loop invariant theorem, a valid loop invariant ?(?)I(n) must have the property that Select one: a. ?(?)=0I(n)=0 after a finite number of steps. b. After the loop, ?→?(?)P→I(N) where ?P is the postcondition. c. ?(0)→?I(0)→Q, where ?Q is the precondition. d. None of the other answers are correct
(C++)Change the following loop to a while loop: int i; for (i=0; i<10; i++) {    ...
(C++)Change the following loop to a while loop: int i; for (i=0; i<10; i++) {     cout<<i<<endl; }
Why is an exit condition so important for a while loop?
Why is an exit condition so important for a while loop?a.An exit condition is not vital.  A while loop works fine without one.b.So the programmer knows when it is okay to leave the room.c.If no exit condition is provided, while loops cannot continue beyond one iterationd.It allows the loop to end instead of running indefinitely.e.While loops are unstable, and must know how to exi
I have to use a sentinel while loop to complete the following task in a java...
I have to use a sentinel while loop to complete the following task in a java program, I want to see how this is executed so I can better understand how the sentinel while loop works. Thank you! Convert Lab 10 from a counter controlled WHILE loop to a sentinel WHILE loop. Do the following: Prompts the user to enter a grade or a -1 to quit. IF the user entered a -1 THEN Display a message that the User...
Study the following code with a while-loop and convert it to a for-loop (fill in the...
Study the following code with a while-loop and convert it to a for-loop (fill in the blanks). int i=4, result=1; while(i>1) { result *= i; i--; } The following for-loop performs the same functionality: int result=1; for (__________ i=4; i _________1;____________) { result *= i; }
Here is a traditional loop in C:   while (A{i} == 0)                A{i} = A{5} + A{i+3};...
Here is a traditional loop in C:   while (A{i} == 0)                A{i} = A{5} + A{i+3}; (NOTE: please consider braces {} here as usual square brackets for array index). Assume that i is stored in register $s1, and the base address of the array A is in $s2. Fill in the multiple blank spaces in the following MIPS program that is supposed to be compiled from the above C loop: loop: sll $t0, $s1,                add $t0, $t0,                lw $t1, 20($s2)...
Consider the linear time invariant system described by the transfer function G(s) given below. Find the...
Consider the linear time invariant system described by the transfer function G(s) given below. Find the steady-state response of this system for two cases: G(s) = X(s)/F(s) = (s+2)/(3(s^2)+6s+24) when the input is f(t) = 5sin(2t) and f(t) = 5sin(2t) + 3sin(2sqrt(3)t)
For each of the following answers, determine whether the answer better describes a for loop or a while loop.
For each of the following answers, determine whether the answer better describes a for loop or a while loop.It performs one iteration for every value in a sequence.It uses a loop variable.It continues the loop until the condition becomes false.It continues the loop until reaching the end of the sequence.It can easily cause infinite loops.The exact number of iterations are usally known when starting the loop.
1. The correct mean for Condition One is _______ while the correct mean for Condition Two is ______:
Condition 1 Scores Condition 2 Scores 1 8 2 3 3 4 3 10 4 2 4 8 4 7 5 7 2 8 6 9 2 10 5 10 Column Mean Column Median Column Mode Standard Deviation Column Range 1. The correct mean for Condition One is _______ while the correct mean for Condition Two is ______: A. 3.50 and 8.00 B. 3.42 and 7.17 C. 4.00 and 8.00 D. 1.51 and 2.76 E. 7.17 and 3.42 2. The...
Given the following pre-condition and program segment, what is the post-condition for y? // Pre-condition: -2...
Given the following pre-condition and program segment, what is the post-condition for y? // Pre-condition: -2 <= x < 4 y = 2*x*x - x +3
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT