Answer to Question #41785 in Other Programming & Computer Science for san
A group of k villagers must cross,the Sarawak river, which is a wide and deep river. There is no bridge in sight.
They notice two 10-year-old boys playing in a rowboat at the shore. The boat is
so tiny and it can hold only two boys or one villager. How can the villagers
can get across the river and leave the boys in joint possession of the boat?
How many times the boat pass from shore to shore? [Hint: Solve the problem by
starting with k = 1]
· First, the two boys take the boat to the other side,after which one of them returns withthe boat.
· Then a villager takes the boat to the other side andstays there while the other boyreturns the boat.
· These four trips reduce the problem size, measured bythe number of villagers to be ferried by 1.
· Thus, if this fourtrip procedure is repeated the totalof k times, the problem will be solved after the total of 4k trips.
Apply decrease-by-1 process:
Ferry one villager to the far side,leaving boat and boys back at their initial positions
· If no villagers remain, we have finished,
· otherwise, ferry remaining k−1 villagers
Answer. For the groupof k villagers, 4k trips will need to be made.
Need a fast expert's response?Submit order
and get a quick answer at the best price
for any assignment or question with DETAILED EXPLANATIONS!