l less than equal to h less than equal to n, and n is an integer denoting the ma

Question

l less than equal to h less than equal to n, and n is an integer denoting the maximum height. Provide pseudo-code or clearly defined steps for each of the following algorithms. (a) Design and write an algorithm to perform the minimum number of trials (MNT) to determine the highest safe height (FISH). Determine MNT in terms of n. (b) Design and write an algorithm to break the minimum number of jars needed to find HSH. Determine MNT in terms of n. (c) Suppose that you are given a budget of k = 2 jars (that is you cannot break more than two jars). Give an algorithm so the total number of trials to find the HSH is minimum. You must prove that your algorithm achieves this minimum. What is the value of MNT?

Explanation / Answer

t(t+1)/2 = n

t2 + t - 2n = 0

t = [ -1 +sqrt(1+8n) ] / 2

a.)

Code :

int n ; // input

int t = [ -1 +sqrt(1+8n) ] / 2 ;

int h = n ; // initializing the maximum value of h = n

int i = 0 ; // initializing the number of trials to 0

while( jar breaks for height h) {

      h = h-t;

      t = t-1;

      i = i+1;

}

// This while loop decreases the value of h with arithmetic progression of t with diference -1 to some value to which the jar will break

while( jar dosen't breaks for height h) {

      h = h+1;

      i = i+1;

    }

// This while loop increases the new value of h obtained from the previous while loop till we get h = Minimum safe height + 1

system .out.print(i) ;

Final value of i = minimum number of trials

For worst case in the algorithm the MNT is maximum when MSH = 1

and MNT in that case = [ -1 +sqrt(1+8n) ] / 2

b.)

Code :

int n ; // input

int t = [ -1 +sqrt(1+8n) ] / 2 ;

int j = 0 // initializing the jar broken to 0

int h = n ; // initializing the maximum value of h = n

while( jar breaks for height h) {

      h = h-t;

      t = t-1;

      j = j+1

} // This while loop decreases the value of h with arithmetic progression of t with diference -1 to some value to which the jar will break and the corresponding value of jar

system.out.print(j+1) ;

Final value of (j+1) = minimum number of jars required to be broken

As the algorithm for this is more or less same as in part (a) Thus for worst case in the algorithm the MNT is maximum when MSH = 1

and MNT in that case = [ -1 +sqrt(1+8n) ] / 2

c.)

Code :

int n ; // input

int h = n ; // initializing the maximum value of h = n

int i = 0 ; // initializing the number of trials to 0

if( jar breaks for height h/2) {

          h = 1 ; }

else{

          h = h/2 ; }

i = 1 ; // after this 1 trial has gone i.e. the first trial adds up to i. Hence i = 1 form i = 0

// This above conditional fuction are used to first initialize the value of h after from which we start checking the for incremented h to get MSH

while(jar dosen't breaks for height h) {

      h = h+1;

      i = i+1;

    } // This while loop increases the new value of h obtained from the previous while loop till we get h = Minimum safe height + 1

system .out.print(i) ;

Final value of i = minimum number of trials

MNT for the worst case = n/2

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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