Mystery(n: integer>0) 1 temp=1 2 for i = 1 to n do 3 temp=temp*i 4 return temp (

Question

Mystery(n: integer>0)

1      temp=1
2      for i = 1 to n do
3              temp=temp*i
4      return temp

(a) What does this algorithm compute?

(b) Write down the loop invariant for the loop in steps 2-3.

(c) Initialization: Prove that your loop invariant is true before the first iteration of the loop:

(d) Maintenance: Prove that if the loop invariant is true before any (say, the kth) iteration, show also that it remains true before the next(k+1 th) iteration:

(e) Termination: The two proofs above imply that the loop invariant must be true, show that the algorithm computes what you said it does in part(a):

Explanation / Answer

1. & 4. This algorithm computes the factorial of a number which is inputted by the user and returns it as a value to the main tester program.   Proof:

   If we put n as 4 then the program will enter the loop and it will go like: temp=1*1 = 1 and hence, it will return 1;   temp=1*2 = 2 and hence, it will return 2;   temp=2*3 = 6 and hence, it will return 6;   temp=6*4 = 24 and hence, it will return 24;

Hence , this is how the program will work and give out the factorial for the particular integer value entered in the program by the user.

2.& 4. The loop invariant for the following program is stated as follows. Hope you'll understand it well through this written loop invariant. The loop invariant goes as follows: LOOP INVARIANTS:

The loop invariants hold here in the given code:

(n: integer>0)

temp=1
for i = 1 to n do

// Loop Variants Hold Here.....
temp=temp*i
return temp

Please rate the answer if it helped....Thankyou

Hope it helps.....

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.