Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to solve the problem of overnight suspension bridge with object-oriented". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn "how to solve the problem of overnight suspension bridge with object-oriented".

Problem description

1. Five people are going to cross a suspension bridge, and at first they are all on one side of the bridge.

two。 It was so dark that five people had only one flashlight in their hands.

3. The bridge can only cross two people at the same time, whether one person or two people cross the bridge, need to carry a flashlight to watch the road. And flashlights can only be transmitted by people carrying them across the bridge.

4. It takes 1 minute for the first person to cross the bridge, 2 minutes for the second person, 5 minutes for the third person, 7 minutes for the fourth person, and 10 minutes for the fifth person. Because of the different speed, if two people cross the bridge together, the slow one will prevail.

Problem: try to cross the bridge as soon as possible. The algorithm for solving the problem is required to be written.

Analyze the topic

1. From the left to the right, you need a person with a flashlight, and when you get to the right, you need someone to turn back to the left, so how can you minimize the return time?

A: then the man who sent the flashlight back must be the fastest on the right.

two。 Two people cross the bridge at the same time, take the maximum time, then how to ensure the maximum use of the longest time?

A: choose the two people who spend the longest time on the left to cross the bridge together.

3. How to make sure that the person who turns on the right and goes back and forth to the left takes the shortest time?

A: on the left, choose the fastest two people to go to the right, then the fastest fold back to the left, and the next fastest to wait for the slowest two people to come, and then fold back to the left. Repeat this step to ensure that it takes the shortest time for the person to return to the left.

Let's try to figure out how long it will take.

(1) choose the two fastest people on the left to go first, 1 minute and 2 minutes first, taking a total of 2 minutes. Now on the left, 5, 7, 10. One on the right, two.

(2) choose the fastest person on the right to come back, 1 minute back, a total of 2 minutes + 1 minute = 3 minutes. Now on the left, 5, 7, 10. Two on the right.

(3) choose the slowest two people on the left, 7 minutes and 10 minutes, a total of 3 minutes + 10 minutes = 13 minutes. Now the left side is 5pm 1. On the right, 2, 7, 10.

(4) choose the fastest person on the right to turn back and come back in 2 minutes. It takes a total of 13 minutes + 2 minutes = 15 minutes. Now on the left, 5 minutes, 1 minutes, 2. On the right, 7. 10.

(5) choose the two fastest people on the left to go first, 1 minute and 2 minutes first, taking a total of 15 minutes + 2 minutes. Now five on the left. Right 7, 10, 10, 1, 2.

(6) choose the fastest person on the right to turn back, 1 minute back, a total of 17 minutes + 1 minute = 18 minutes. Now the left side is 5pm 1. Right 7, 10, 10, 2.

(5) choose the slowest two people on the left to go over. A total of 18 minutes + 5 minutes = 23 minutes will be spent on the passage of 1 minute of 5 minutes. It's not on the left right now. On the right, 7, 10, 10, 2, 5, 5, 1.

It took 23 minutes in total.

Sum up the above rules:

The fastest two people go, the fastest one comes back, the slowest two people go, and the fastest one comes back. Loop this step.

How to implement the above algorithm?

Here we can use an object-oriented approach.

Define a Person class.

Included attributes:

(1) the bridge crossing speed Speed. (1 minute / 2 minutes / 5 minutes / 7 minutes / 10 minutes)

(2) which side of the bridge Side is currently on (left / right)

Included method: the method that walks from left to right, or the method that folds from the right to return to the left, named Pass (Side side)

Define an interface IPassAction that contains a method void Pass (Side side)

Define an enumerated type Side, including Left, Right

Define a way to find the two slowest people on one side of the bridge

List FindTwoFastSpeedPersons (List persons, Side side)

Define a way to find the two fastest people who cross the bridge on one side

List FindTwoLowestSpeedPersons (List persons, Side side)

Define a way to find the two slowest people on one side of the bridge

Person FindFastSpeedPerson (List persons, Side side)

Define a method to detect whether the specified person has reached the specified side

CheckPersonsPassedToTargetSide (List persons, Side targetSide) code

Person class

Namespace PassRiver2._0 {public class Person: IPassAction {private int _ speed; private Side _ side; public Person (int speed, Side side) {_ speed = speed; _ side = side;} public int Speed {get {return _ speed;} set {_ speed = value }} public Side Side {get {return _ side;} set {_ side = value;}} public void Pass (Side side) {_ side = side;}

Side enumerated class

Namespace PassRiver2._0 {public enum Side {Left = 0, Right = 1}}

IPassAction interface

Namespace PassRiver2._0 {public interface IPassAction {void Pass (Side side);}}

Public method

List FindTwoFastSpeedPersons (List persons, Side side)

List FindTwoLowestSpeedPersons (List persons, Side side)

Person FindFastSpeedPerson (List persons, Side side)

CheckPersonsPassedToTargetSide (List persons, Side targetSide)

Private static List FindTwoLowestSpeedPersons (List persons, Side side) {List sortedPersons = persons.Where (s = > s.Side = = side). Orderby Descending (s = > s.Speed). ToList (); List passedPersons = new List (); if (persons.Count > 1) {passedPersons = new List (); passedPersons.Add (sortedPersons [0]) PassedPersons.Add (sortedPersons [1]);} else if (persons.Count = = 1) {passedPersons.Add (sortedPersons [0]);} else {} return passedPersons } private static List FindTwoFastSpeedPersons (List persons, Side side) {List sortedPersons = persons.Where (s = > s.Side = = side) .OrderBy (s = > s.Speed). ToList (); List passedPersons = new List (); if (persons.Count > 1) {passedPersons = new List (); passedPersons.Add (sortedPersons [0]) PassedPersons.Add (sortedPersons [1]);} else if (persons.Count = = 1) {passedPersons.Add (sortedPersons [0]);} else {return null;} return passedPersons } private static Person FindFastSpeedPerson (List persons, Side side) {if (persons.Count > 0) {List sortedPersons = persons.Where (s = > s.Side = = side) .OrderBy (s = > s.Speed). ToList (); return sortedPersons [0];} else {return null }} private static bool CheckPersonsPassedToTargetSide (List persons, Side targetSide) {bool isPassed = false; foreach (Person person in persons) {if (person.Side! = targetSide) {isPassed = false; return isPassed }} isPassed = true; return isPassed;}

Main method

Static void Main (string [] args) {Type type = MethodBase.GetCurrentMethod () .DeclaringType; / / create logging component instance ILog log = log4net.LogManager.GetLogger (type); / / record error log.Info ("Start"); List persons = new List (); persons.Add (new Person (1, Side.Left)) Persons.Add (new Person (2, Side.Left)); persons.Add (new Person (5, Side.Left)); persons.Add (new Person (7, Side.Left)); persons.Add (new Person (10, Side.Left)); int totalTime = 0 While (! CheckPersonsPassedToTargetSide (persons, Side.Right)) {List twoFastSpeedPersons = FindTwoFastSpeedPersons (persons, Side.Left); foreach (Person person in twoFastSpeedPersons) {person.Pass (Side.Right) } if (twoFastSpeedPersons.Count > 1) {totalTime + = twoFastSpeedPersons [1] .Speed;} else if (twoFastSpeedPersons.Count = = 1) {totalTime + = twoFastSpeedPersons [0] .Speed } else {} / /-log.Info ("- Go To Right- >") Foreach (Person person in twoFastSpeedPersons) {log.Info (person.Speed);} log.Info ("Total Time:" + totalTime) / /-if (CheckPersonsPassedToTargetSide (persons, Side.Right)) {break;} Person fastSpeedPerson = FindFastSpeedPerson (persons, Side.Right); fastSpeedPerson.Pass (Side.Left); totalTime + = fastSpeedPerson.Speed / /-log.Info ("); foreach (Person person in twoLowestSpeedPersons) {log.Info (person.Speed);} log.Info (" Total Time: "+ totalTime) / /-if (CheckPersonsPassedToTargetSide (persons, Side.Right)) {break;} fastSpeedPerson = FindFastSpeedPerson (persons, Side.Right); fastSpeedPerson.Pass (Side.Left); totalTime + = fastSpeedPerson.Speed / /-log.Info ("

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.