Min-Max
Write an algorithm that finds both the smallest and
largest numbers in a list of n numbers and with complexity
T(n) is at most about (1.5)n comparisons.
Answer Posted / kush singh
1. Algorithm MaxMin (i,j, max, min)
2. // a[1:n] is a global array Parameter i and j are integers,
3. // 1 „T i „T j < n. The effect is to set max and min to the
4. // largest and smallest values in a [i, j], respectively.
5. {
6. if (i=j) then max:=min:=a[i]; //small(P)
7. else if (i = j ¡V 1) then //Another case of Small (P)
8. {
9. if a [i] < a[j] then
10. {
11. max:=a[j]; min:=a[i];
12. }
13. else
14. {
15. max:=a[i]; min:=a[j]
16. }
17. }
18. else
19. {
20. // If P is not small, divide P into subproblems
21. // Find where to split the set
22. mid:= „¾(i+j)/2„Î;
23. //Solve the subproblems
24. Maxmin (i, mid, max, min);
25. MaxMin (mid+i, j, max1, min1);
26. // Combine the solutions
27. if (max<max 1) then max:=max1;
28. if(min>min1) then min:=min1;
29. }
30. }
| Is This Answer Correct ? | 4 Yes | 0 No |
Post New Answer View All Answers
Code for Two Classes for Doing Gzip in Memory?
write a program that prompt the user to enter his height and weight,then calculate the body mass index and show the algorithm used
How to Split Strings with Regex in Managed C++ Applications?
U hv to enter a range from a and b and search hw many no. of times a pattern n. occurs between the range a and b. Eg :i/p:enter range :0 100 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 0 to 100:1 Eg :i/p:enter range :100 1000 Enter pattern: 13 o/p: the no. times 13 occurred betwwn 100 to 1000: (in this 13,113,131,132,133…139,213,313,…913 all these will be counted)
Performance Algorithm A performs 10n2 basic operations and algorithm B performs 300 lg n basic operations. For what value of n does algorithm B start to show its better performance?
solve the problem in the programming language C++"if a five digit number is input through the keyboard.Write a program to calculate the sum of its digits(hint: use the modulus operator)
What output does the following code generate? Why? What output does it generate if you make A::Foo() a pure virtual function? class A { A() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; class B : public A { B() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; int main(int, char**) { A objectA; B objectB; return 0; }
write a program that reads a series of strings and prints only those strings begging with letter "b"
How to swap two ASCII numbers?
write a program to convert temperature from fa height into celcius and vise versa,use modular programming
how to write a program that opens a file and display in reverse order?
Given a table of the form: Product Sold on A 1/1/1980 B 1/1/1980 C 1/1/1980 A 1/1/1980 B 1/1/1980 C 2/1/1980 A 2/1/1980 There are 30 products and 10,000 records of such type. Also the month period during which sales happened is given to u. Write the program to display the result as: Product Month No. of copies A January 12 A February 15 A March 27 B January 54 B February 15 B March 10 C January 37
Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
write a function that reverse the elements of an array in place.The function must accept only one pointer value and return void.
how to diplay a external image of output on winxp by using c & c++,