Algorithms There is a jail in the desert. A rebellion broke out and a single gua

Question

Algorithms

There is a jail in the desert. A rebellion broke out and a single guard is immobilized. He helplessly watched the prisoners left one by one with different speed in different directions. Later, he freed himself and took a motorbike with an extra seat. Now, he can follow the footprints and pick up one prisoner at a time and bring them back to jail. Each prisoner moves with constant individual speed v_i and left the jail at time t_i. In which order does the guard bring prisoners back in order to minimize the time?

Explanation / Answer

procedure MINTIME

//this is a function that runs a timer, identify the prisoner who has gone to the farthest distance, bring him first back //to the prison.

//Let n indicate the number of prisoners and the speed of the prisoners are available in the array v(1:n).

//c(1:n) indicate whether a particular prisoner is captured

//vehicle speed can be indicated as s.

//The prisoner who has to be captured back is identified by the next procedure and stored in the variable k

v(1:n) <- { speeds of n prisoners }

c(1:n) <- {false for all}

Start(timer);

while( not all c(1:n) are true) //when not all prisoners are captured, repeat the procedure

{

k <- FARTHESTPRISONER(v, c, timer); //identifying the farthest prisoner

//The kth prisoner is captured back - a procedure can be written assuming vehicle speed

timeCaptureK <- CAPTUREBACK(k, v, s, timer)

//timeCaptureK may be used to compute the total time of capturing

c[k] <- true;

}

end MINTIME;

-------------------------------------------------------------------------------------------------------------------------------------

procedure FARTHESTPRISONER(v, c, timer)

//The integer variable k indicates the ith prisoner who has gone to the farthest distance

distance = 0;

for i <- 1 to n do

if c[i] == false,

then

currentDistancei <- v[i] * timer;

if distance < currentDistancei,

then

k <- i

distance = currentDistancei

endif

endif

repeat

return(k);

end FARTHESTPRISONER

-----------------------------------------------------------------------------------------------------------------------------------

procedure CAPTUREBACK(k, v, s, timer)

//Let the guard capture the farthest prisoner at a distance x = s * (timeAtCaptureK - startTimeK)

//Same distance is travelled by the prisoner at timeAtCaptureK, x = v[k] * timeAtCaptureK

//(s-v[k])*timeAtCaptureK = s*startTime gives timeAtCaptureK = s*startTimeK/(s- v[k])

return timeAtCaptureK;

end CAPTUREBACK;

---------------------------------------------------------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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