Question

Use a loop invariant to prove that the following program segment for computing the nth power,...

Use a loop invariant to prove that the following program segment for computing the nth power, where n is a positive integer, of a real number x is correct.

power := 1
i := 1
while i <= n
  power := power*x
  i := i+1

Homework Answers

Answer #1

Let p be the loop invariant and we need to prove that before, inside and termination of loop “power = x i−1 and i ≤ n + 1.”.

For iniatial case: i=1 and power = xi-1 = x0 =1;

In the loop: i<=n; Since I is incerement by 1; and we know that powerinitial =xi-1;

So, the new power will be powernew= powerinitial*x= xi-1*x = xi-1+1 = x(i+1)-1 ;

Now, We know that i=i+1; for new case

Then, on putting i in the place of (i+1), for new case

We get powernew= xi-1 ;

This process goes throughout the loop.

Now, after the termination of loop, ie. i<=n is false;

We get i=n+1;

by putting the value of i in power

powern = xi-1 = xn+1-1 = xn.

I hope it helps.
Thank you

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
For each pseudo-code function below (after the next ==== line), write a useful loop invariant capturing...
For each pseudo-code function below (after the next ==== line), write a useful loop invariant capturing correctness for the main loop in each of the following programs and briefly argue initialization, preservation, and termination. EXAMPLE PROBLEM: //Function to return the max of an array A Maximum(array of integers A) Local integer integer m m=0 for i = 1 to n if A[i] > m then m = A[i] end function Maximum EXAMPLE SOLUTION: The loop invariant is m = max(0,...
Recursively computing sums of cubes, cont. (a) Use induction to prove that your algorithm to compute...
Recursively computing sums of cubes, cont. (a) Use induction to prove that your algorithm to compute the sum of the cubes of the first n positive integers returns the correct value for every positive integer input.
Find the exact number of times (in terms of n) the innermost statement (X = X...
Find the exact number of times (in terms of n) the innermost statement (X = X + 1) is executed in the following code. That is, find the final value of X. Then express the total running time in terms of O( ), Ω( ), or Θ( ) as appropriate. X = 0; for k = 1 to n     for j = 1 to n – k         X = X + 1; The following program computes and returns...
Prove binary search (Seen below) is correct using a loop invariant. def search_binary(arr, val): low, up...
Prove binary search (Seen below) is correct using a loop invariant. def search_binary(arr, val): low, up = 0, len(arr) - 1 while low != up: # binary search mid = (low + up) / 2 if arr[mid] == val: return mid elif val < arr[mid]: up = mid - 1 else: low = mid + 1 return low
*********I need question 6 answered which is from question 5 which is ********* Question 5 :...
*********I need question 6 answered which is from question 5 which is ********* Question 5 : Program Correctness I (1 point) Use the loop invariant (I) to show that the code below correctly computes n P−1 k=0 2k (this sum represents the sum of the first n even integers where n ≥ 1). Algorithm 1 evenSum(int n) 1: p = 2(n − 1) 2: i = n − 1 3: while i > 0 do 4: //(I) p = nP−1...
Using a loop (not the output format character %o), create a program that takes a positive...
Using a loop (not the output format character %o), create a program that takes a positive integer n, and then displays the polynomial for the octal representation of that integer. Use successive division, as demonstrated in the binary conversion example from the lesson, to do this. For example, for n = 157, the program should output the following: 157 = + (5 * 8^0) + (3 * 8^1) + (2 * 8^2) When this part is working properly, “surround” this...
IN JAVA In this problem, we will implement an nth root finder. Recall that the nth...
IN JAVA In this problem, we will implement an nth root finder. Recall that the nth root of x is the number when raised to the power n gives x. In particular, please fill in the method findNthRoot(int number, int n, int precision) within the Main class. The method should return a string representing the nth root of number, rounded to the nearest precision decimal places. If your answer is exact, you should still fill in the answer with decimal...
A program devise a recursive algorithm to find a2n, where a is a real number and...
A program devise a recursive algorithm to find a2n, where a is a real number and n is a positive integer (hint: use the equality a2n+1 = (a^2n)^2
Given the following program segment….             for (num = 10; num >= 1; num--)            cout...
Given the following program segment….             for (num = 10; num >= 1; num--)            cout << setw(3) << num; Write a while loop that will have the same output. C++
Write a program that asks the user of a positive integer value. The program should use...
Write a program that asks the user of a positive integer value. The program should use a loop to get the sum of all the integers from 1 up to the number entered. For example, if the user enters 50, the loop will find the sum of 1,2,3,4,…,50. using namespace std;
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT