Answer to Question #41785 in Programming & Computer Science for san

Question

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]

Answer 1

Answer on Question#41785, Programming, Other
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]

Solution:
· 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.

Algorithm
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.