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

Question #41785

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]

Expert's answer

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]

· First, the two boys take the boat to the other side,after which

· Then a villager takes the boat to the other side andstays there while the

· 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

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

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.

Need a fast expert's response?

Submit orderand get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

## Comments

## Leave a comment