学步园

以过桥算法来谈如何满足客户的需求和程序设计步骤

    如果答案只停留在解决题目的表面，而不能抽象出此类问题，是不及格的。
正如，开发应用型软件，应站在行业的高度和全局去思考，而不仅仅是解决局部的问题。
所以实际的项目中，应有架构师来统领全局，看得更多更远一些。

一、需求
四个女人过桥，夜间有一火把，每次最多过两个，必需带火把，
过桥速度不一样
no.1 1min
no.2 2min
no3 5min
no.4 10min
两个人过用最慢一个的速度，火把不能扔
如何在17min内四个女人都过桥

二、人工模拟(对应需求分析)
人工计算机答案：
1+2=2过
1=1回
5+10=10过
2=2回
1+2=2过
计：2+1+10+2+2=17分钟

    在实际的项目开发中，应将用户的需求进行界面建模、打印结果、报表等可视化的资料和用户确认；才能将问题看得透一些，找到更好的思路。
    如从上述的模拟就可以总结出思路：1、大数应在一起相抵 2、回程应可能小。
     这就是一种抽象化解决问题的能力，相当于“数学模型”。

三、问题的拓展(对应概要设计)

从此算法可以提出下述进一步的需求，即程序要能适应：
1、当不是四个，而是四亿个如何过。即所谓的需求变更，且这种变更是可能和合理的
2、通用性，不仅仅是用来过桥，类似的算法如何能活用或复用

 
四、解决方案(对应详细设计)
//设初始时，人都在桥左，目前是全部走到桥右。即将客户的需求，转换为“输入”和“输出”
//根据目标和结束条件，总结出数学模型：即“1、大数应在一起相抵 2、回程应可能小”的思路

do

  //过桥
  if(计算桥右没有走得快的人) then
      走得快的人先一起走
  else
      走得最慢的人一起走
  end if
  //回程
  总是返回最近的人

while 桥左没有人

打印出结果
 
五、编码实现
   由主程序和一个移动的对象两个文件组成。
   主程序：

using System;
using System.Collections.Generic;
using System.Text;

namespace Bridge
{
    /// <summary>
    /// 设初始时，人都在桥左，目前是全部走到桥右。即将客户的需求，转换为“输入”和“输出”
    ///根据目标和结束条件，总结出数学模型：即“1、大数应在一起相抵 2、回程应可能小”的思路
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            string CurrentStepMoveObject;
            MoveObject moveObject = new MoveObject();
            //数据输入
            moveObject.AddObjectMoveRate(1);
            moveObject.AddObjectMoveRate(2);
            moveObject.AddObjectMoveRate(5);
            moveObject.AddObjectMoveRate(10);
            moveObject.AddObjectMoveRate(20);
            moveObject.AddObjectMoveRate(30);

            do
            {
                //过桥
                if (moveObject.BridgeRightFasterObjectCount == 0) //计算桥右没有走得快的人
                {
                    CurrentStepMoveObject = moveObject.MoveToBridgeRight(1);// 走得快的人先一起走
                }
                else//计算桥右有走得快的人
                {
                    CurrentStepMoveObject = moveObject.MoveToBridgeRight(2);//走得最慢的人一起走
                }
                if (CurrentStepMoveObject != "")
                {
                    Console.WriteLine("过桥：" + CurrentStepMoveObject);
                }
                //回程
                CurrentStepMoveObject = moveObject.MoveToBridgeLeft(); //总是返回最近的人
                if (CurrentStepMoveObject != "")
                {
                    Console.WriteLine("返回：" + CurrentStepMoveObject);
                }
            }
            while  (!moveObject.IsMoveComplete);

            Console.ReadLine();
        }

    }
}

移动的对象:

using System;
using System.Collections.Generic;
using System.Text;

namespace Bridge
{
    /// <summary>
    /// 要移动的对象
    /// </summary>
    class MoveObject
    {
        const int OneMoveMax=2;//一次移动最多的数量
        List<int> BridgeLeftObjects;//桥左的待移动的对象
        List<int> BridgeRightObjects;//桥右的已移动的对象
        int MoveObjectsCount;//要移动对象的数量
        int MovedObjectsCount;//已移动对象的数量
        public MoveObject()
        {
            BridgeLeftObjects = new List<int>();
            BridgeRightObjects = new List<int>();
            MoveObjectsCount = 0;
            MovedObjectsCount = 0;
        }
        /// <summary>
        /// 增加要移动对象的速度
        /// </summary>
        public void AddObjectMoveRate(int ObjectMoveRate)
        {
            BridgeLeftObjects.Add(ObjectMoveRate);
            MoveObjectsCount++;
        }
        /// <summary>
        /// 桥右比桥左走得快的人数
        /// </summary>
        public int BridgeRightFasterObjectCount
        {
            get
            {
                int FasterObjectCount = 0;
                //桥右比桥左走得快的人数
                foreach (int BridgeRightObject in BridgeRightObjects)
                {                    
                    foreach (int BridgeLeftObject in BridgeLeftObjects)
                    {
                        if (BridgeRightObject < BridgeLeftObject)
                        {
                            FasterObjectCount++;
                            break;
                        }
                    }
                  
                }
                return FasterObjectCount;
            }
        }
       /// <summary>
        /// 从桥左走到桥右
       /// </summary>
       /// <param name="MoveType">移动的类型：走得快的(1)，还是走得慢的(2)</param>
        /// <returns>返回移动的具体对象</returns>
        public string  MoveToBridgeRight(int MoveType)
        {
            int LeftObject=0;
            int CurrentBridgeLeftObjects;
            string ToRightObject="";
            if (MoveObjectsCount > MovedObjectsCount)//是否未移完
            {
                BridgeLeftObjects.Sort();
                for (int MoveNumber = 1; MoveNumber <= OneMoveMax; MoveNumber++)
                {
                    CurrentBridgeLeftObjects = BridgeLeftObjects.Count-1;
                    if (CurrentBridgeLeftObjects >= 0)//是否还有可移的对象
                    {
                        switch (MoveType)//计算要移动的对象
                        {
                            case 1:
                                LeftObject = BridgeLeftObjects[0];
                                BridgeLeftObjects.RemoveAt(0);//过桥后删除
                                break;
                            case 2:
                                LeftObject = BridgeLeftObjects[CurrentBridgeLeftObjects ];
                                BridgeLeftObjects.RemoveAt(CurrentBridgeLeftObjects);//过桥后删除
                                break;
                        }
                        if (LeftObject > 0)
                        {
                            BridgeRightObjects.Add(LeftObject);
                            ToRightObject = (ToRightObject == "") ? LeftObject.ToString() : (ToRightObject + "," + LeftObject.ToString());

                            MovedObjectsCount++;
                            LeftObject = 0;
                        }
  
                    }
                }
            }
            return ToRightObject;
        }

        /// <summary>
        /// 总是最快一个的返回
        /// </summary>
        /// <returns>返回移动的具体对象</returns>
        public string MoveToBridgeLeft()
        {
            int RightObject;
            string ToLeftObject="";
            if (MoveObjectsCount != MovedObjectsCount)//未移完
            {
                BridgeRightObjects.Sort();
                RightObject = BridgeRightObjects[0];
                BridgeLeftObjects.Add(RightObject);
                MovedObjectsCount--;
                ToLeftObject = RightObject.ToString();
                BridgeRightObjects.RemoveAt(0);
            }
            return ToLeftObject;
        }
        public bool IsMoveComplete
        {
            get
            {
                return (MovedObjectsCount >= MoveObjectsCount);
            }
        }
    }
}

六、测试
   要将过桥的人数增加5个、10个、N个的情况下看是否也正确

源代码下载 :http://files.cnblogs.com/pinpkm/Bridge.rar

所属话题：[算法题]找重复数与四个女人过河