please do problem 5 On the gameshow The Price is Right conte

please do problem 5

On the gameshow The Price is Right, contestants guess the price of an item, and the winner is the person who guesses closest to the actual price without going over the actual price. For example, if the price of a refrigerator is $1529 and the contestants guess $1000, $1530, $1200, and $1600, then the person who guessed $1200 will win the refrigerator. If all guesses are too high, nobody wins. The following algorithm takes as input a list of guesses and an actual price, and determines the guess that is closest to the actual price without going over. All inputs are positive values. The algorithm returns 0 if all guesses are too high and there is no winner. procedure ClosestWithoutGoingOver(a_1, a_2, .. ., a_n: list of guesses, p: price, all positive) best:= 0 for i:= 1 to n if (a_i best) best:= a_i return best Use a loop invariant to prove that the ClosestWithoutGoingOver algorithm given above is correct, i.e., that it returns the guess in the list that is closest to the price p without going over, and returns 0 if all guesses in the list are too high. Be sure to include all the parts of the proof: State the loop invariant precisely. Prove the loop invariant by induction on the number of loop iterations. Use the loop invariant to prove that the algorithm is correct as defined above. Design an algorithm that finds the index of the last even integer in a given list of integers or returns 0 if the list does not have any even integer: (Start your pseudocode like this:) procedure LastEven(a_1, a_2, .. ., a_n: list of integers) State the loop invariant precisely. Prove the loop invariant by induction on the number of loop iterations. Use the loop invariant to prove that the algorithm is correct as defined above.

Solution

5)

a)

I hope this solves your problem but if you have any other doubt related to this algorithm just comment in the comment section below I\'ll help.

b)

Loop invariant: A loop invariant is a condition that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part way through an iteration.)

when i =0 the condition will be checked whether the integer which is selected in the array is even or not if it is an even number the algorithm will start chickening for the rest of the integers in the array and keep on updating the location as even number arrives.

when i =0 the condition will be checked whether the integer which is selected in the array is even or not if it is an even number the algorithm will start chickening for the rest of the integers in the array and keep on updating the location as even number arrives.

d)

for(int i=0; i<length; i++)

{

if(LastEven(i) % 2==0)

{

loc=i;

flag=1;

}

}