Let n be an even positive integer. Our goal is to determine the range of a list
ID: 3605669 • Letter: L
Question
Let n be an even positive integer. Our goal is to determine the range of a list of n real numbers, where the range is defined to be the difference between the largest number in the list and the smallest number in the list. The following algorithm solves this problem.
Let n be an even positive integer. Our goal is to determine the range of a list of n real numbers, where the range is defined to be the difference between the largest number in the list and the smallest number in the list. The following algorithm solves this problem Range(a1, a2,.. . , am: a list of n real numbers, where n is even and positive) 1.if a1 > a2 then 2. 5.else 4. 5, for i 1 to n/2-1 6. 7. 8. 9. if a2i+i > a2i+2 thein ifa2i+1 > M then M :=a2i if a22 M then M := a2i+2 if a2i+1Explanation / Answer
a. Above algorithm, initally among a1 and a2, assign the minimum to m and maximum to M. At any iteration value i, we finding minimum and maximum among a2i+1 and a2i+2 and if minimum of them is lower than the minimum value we found between a1 to a2i, we will replace the value of m to minimum of a2i+1 and a2i+2 . Similarly at iteration i, we are storing the maximum value value from a1 to a2i+2 into variable M. This can be shown by below equation
Since minimum((a1,a2,...,a2t-1,a2t),minimum(a2t+1,a2t+2) ) = minimum(a1,a2,...,a2t-1,a2t,a2t+1,a2t+2)
Similarly maximum((a1,a2,...,a2t-1,a2t),maximum(a2t+1,a2t+2) ) = maximum(a1,a2,...,a2t-1,a2t,a2t+1,a2t+2)
Thus after the tth iteration, we have the minimum value from a1,a2....,a2t+2 in variable m and maximum of them in variable M.
b. Since the loop iterates from i=1 to n/2 -1 and upto t iteration, we are covering from a1 upto a2t+2 and storing the minimum and maximum of them in m and M respectively. So upto n/2 -1 iteration we are covering from a1,a2,.. upto a2(n/2 -1)+1, a2(n/2-1)+2 . Thus we are covering all the elements from a1,a2,.. upto an-1, an with m containing mimimum among them and M covering maximum among them.
Calculating M-m will return the range of number in the entire list. Thus the above algorithm is correct.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.