首页 > 代码库 > 夜过吊桥算法
夜过吊桥算法
问题描述：五个人打算过一座吊桥，开始时他们都位于该桥的一侧。天很黑，五个人手里只有一个手电筒。该桥一次最多只能同时过两个人，无论是一个人还是两个人过桥，都需要携带手电筒看路。而且手电筒只能通过人携带过桥的方式传递。第一个人过桥需要1分钟时间，第二个人过桥需要2分钟，第三个人需要5分钟，第四个需要7分钟，第五个需要10分钟。由于速度不同，两个人一起过桥的话，速度以慢的人为准。求最快过桥时间。
Main
using System;using System.Collections.Generic;using System.Linq;namespace PassRiver{ class Program { private const int maxPassTogetherCount = 2; static void Main(string[] args) { List<Person> leftPersons = new List<Person>(); List<Person> rightPersons = new List<Person>(); Person p1 = new Person(1); Person p2 = new Person(2); Person p3 = new Person(5); Person p4 = new Person(7); Person p5 = new Person(10); leftPersons.Add(p4); leftPersons.Add(p5); leftPersons.Add(p1); leftPersons.Add(p2); leftPersons.Add(p3); int totalTime = 0; while (leftPersons.Count != 0) { List<Person> twoFastSpeedPersons = FindTwoFastSpeedPersons(leftPersons); foreach (Person person in twoFastSpeedPersons) { leftPersons.Remove(person); } rightPersons.AddRange(twoFastSpeedPersons); if (twoFastSpeedPersons.Count > 1) { totalTime += twoFastSpeedPersons[1].Speed; } else if (twoFastSpeedPersons.Count == 1) { totalTime += twoFastSpeedPersons[0].Speed; } else { } //------------- Console.WriteLine("---Go To Right---------->"); foreach (Person person in twoFastSpeedPersons) { Console.WriteLine(person.Speed); } Console.WriteLine("Total Time:" + totalTime); Console.WriteLine(); //------------- if (leftPersons.Count == 0 || rightPersons.Count==5) { break; } Person fastSpeedPerson = FindFastSpeedPerson(rightPersons); rightPersons.Remove(fastSpeedPerson); leftPersons.Add(fastSpeedPerson); totalTime += fastSpeedPerson.Speed; //------------- Console.WriteLine("<----------Go Back Left---"); Console.WriteLine(fastSpeedPerson.Speed); Console.WriteLine("Total Time:" + totalTime); Console.WriteLine(); //------------- if (leftPersons.Count == 0 || rightPersons.Count == 5) { break; } List<Person> twoLowestSpeedPersons = FindTwoLowestSpeedPersons(leftPersons); foreach (Person person in twoLowestSpeedPersons) { leftPersons.Remove(person); } rightPersons.AddRange(twoLowestSpeedPersons); totalTime += twoLowestSpeedPersons[0].Speed; //------------- Console.WriteLine("---Go To Right---------->"); foreach (Person person in twoLowestSpeedPersons) { Console.WriteLine(person.Speed); } Console.WriteLine("Total Time:" + totalTime); Console.WriteLine(); //------------- if (leftPersons.Count == 0 || rightPersons.Count == 5) { break; } fastSpeedPerson = FindFastSpeedPerson(rightPersons); rightPersons.Remove(fastSpeedPerson); leftPersons.Add(fastSpeedPerson); totalTime += fastSpeedPerson.Speed; //------------- Console.WriteLine("<----------Go Back Left---"); Console.WriteLine(fastSpeedPerson.Speed); Console.WriteLine("totalTime:" + totalTime); Console.WriteLine(); //------------- if (leftPersons.Count == 0 || rightPersons.Count == 5) { break; } } Console.WriteLine("------------Total Time-------------"); Console.WriteLine(totalTime); Console.ReadKey(); } public static List<Person> FindTwoLowestSpeedPersons(List<Person> persons) { List<Person> sortedPersons = persons.OrderByDescending(s => s.Speed).ToList(); List<Person> passedPersons = new List<Person>(); if (persons.Count > 1) { passedPersons = new List<Person>(); passedPersons.Add(sortedPersons[0]); passedPersons.Add(sortedPersons[1]); } else if (persons.Count == 1) { passedPersons.Add(sortedPersons[0]); } else { } return passedPersons; } public static List<Person> FindTwoFastSpeedPersons(List<Person> persons) { List<Person> sortedPersons = persons.OrderBy(s => s.Speed).ToList(); List<Person> passedPersons = new List<Person>(); if (persons.Count > 1) { passedPersons = new List<Person>(); passedPersons.Add(sortedPersons[0]); passedPersons.Add(sortedPersons[1]); } else if (persons.Count == 1) { passedPersons.Add(sortedPersons[0]); } else { return null; } return passedPersons; } public static Person FindFastSpeedPerson(List<Person> persons) { if (persons.Count > 0) { List<Person> sortedPersons = persons.OrderBy(s => s.Speed).ToList(); return sortedPersons[0]; } else { return null; } } }}
Person
namespace PassRiver{ public class Person { private int _speed; private Side _side; public Person(int speed) { _speed = speed; _side = Side.Left; } public int Speed { get { return _speed; } set { _speed = value; } } public Side Side { get { return _side; } set { _side = value; } } }}
Side
namespace PassRiver{ public enum Side { Left = 0, Right = 1 }}
SortUtil
using System.Collections.Generic;namespace PassRiver{ public static class SortUtil { public static List<Person> BubbleSort(List<Person> persons) { for (int i = 0; i < persons.Count - 1; i++) { for (int j = i + 1; j < persons.Count; j++) { if (persons[i].Speed < persons[j].Speed) { Person temp = persons[j]; persons[j] = persons[i]; persons[i] = temp; } } } return persons; } }}
夜过吊桥算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。