课外娱乐__《编程之美》之小飞的电梯调度算法

时间:2021-12-06 12:51:26

/*
 * floorProblem.java
 *
 * Created on 2009年4月29日, 上午3:01
 *
 * 问题描述:《编程之美》之小飞的电梯调度算法。
 * 假设电梯只在某一楼层停,然后乘客下电梯步行至各自目的楼层,求电梯应停在哪一层能使乘客步行的楼层数和最少。
 * 假设楼层为N,最大载人数为M,应停层数为X,每位乘客目的楼层为Mi,Mr表示实际乘客数。
 * (1)数学想法:楼层应该停在sum(Mi)/Mr,如果此数为整数,则即为所求,若此数非整数,则可以上下相邻整数分别
 * 求和,然后比较优劣
 * (2)计算机最笨算法:遍历每个楼层,求出停在每个楼层乘客步行楼层数和,然后求最少值
 * (3)书中提供想法:由于(2)的算法复杂度高,所以考虑将其中一套循环提出改为加减比较以减少复杂度。
 * 假设电梯停在i层,乘客步行层数和为Y,去i-1及其以下层M(i-1),去i层Mi,去i+1及其以上层M(i+1)
 * 如果电梯停在i-1层,则和为Y-M(i-1)+M(i+1)+Mi=Y-(Mi-1 - Mi+1 - Mi),如果电梯停在i+1层,则和为
 * Y-M(i+1)+M(i-1)+Mi = Y - (Mi+1 - Mi-1 - Mi)。如果M(i-1)>Mi+1 + Mi,则停在i-1层更好,如Mi+1>Mi-1 + Mi,
 * 则停在i+1层更好,否则停在i层更好。
 * 此题中楼层和最大载客数目都是可量化的,最大载客数目一般不超过20,楼层数目视具体情况2-几百不等。算法一二
 * 以载客为中心,floors[]存的是每个乘客要去的目的楼层,而方法三则是以楼层数目为中心。如果楼层数目超过载客数目,
 * 很明显以载客为中心会稍微减少些资源,反之,以楼层为中心会更优。而第三种方法若以载客为中心,
 * 则需要手动统计到每层的乘客数,当然也可以全部提供这两种数据。
 * passengers[]存的是到每层的乘客数量。
 *
 * 如果电梯会在k个楼层停,如何解决?我的想法是,先将楼层分成k组,然后每组应用停1层算法。如果刚好能分成等k
 * 层,则此问题解决。如果分成等k组,还剩余m项,m<k,则将m项最少人数的层分给相邻的非最少人数的层所在的组。
 *
 * 忽略一般的错误处理,假设用户很细心。
 *
 */

package elevator;

import java.util.logging.ConsoleHandler;
import java.math.RoundingMode;
/**
 *
 * @author ziteng@nkbbs.org

 */
public class floorProblem
{
   
    private int pNum;
    private int fNum;
    /**
     * Creates a new instance of floorProblem
     */
    public floorProblem()
    {
        pNum = 0;
        fNum = 0;
    }
    /**
     * @param passengerNum 乘客数目
     * @param floorNum 楼层数目
     */
    public floorProblem(int passengerNum, int floorNum)
    {
        pNum = passengerNum;
        fNum = floorNum;
    }
    /**
     * @param floors[] 每个乘客对应的目的楼层
     */
    public int mathFun(int floors[])
    {
        int sum = 0;
        int i = 0;
        for(i = 0; i < pNum; i++)
        {
            sum += floors[i];
        }
        int evg = (int)Math.floor((double)sum/(double)pNum);
        if(sum%pNum == 0)
        {
            return evg;
        }
        else
        {
            sum = 0;
            for(i = 0; i < pNum; i++)
            {
                if(floors[i] - evg > 0)
                {
                    sum += floors[i] - evg;
                }
                else
                {
                    sum += evg - floors[i];
                }
            }
            int sum1 = 0;
            for(i = 0; i < pNum; i++)
            {
                if(floors[i] - evg - 1 > 0)
                {
                    sum1 += floors[i] - evg - 1;
                }
                else
                {
                    sum1 += evg + 1 - floors[i];
                }
            }
            if (sum > sum1)
                return (evg + 1);
            else
                return evg;
        }
    }
   
    public int simpleFun(int floors[])
    {
        int sum[] = new int[fNum];
        int i = 0;
        int j = 0;
        int minSum = 0;
        int minFloor = 1;
        for(i = 0; i < fNum; i++)
        {
            sum[i] = 0;
        }
        for(i = 0; i < fNum; i++)
        {
            for(j = 0; j < pNum; j++)
            {
                if(floors[j] - i - 1 > 0)
                {
                    sum[i] += floors[j] - i - 1;
                }
                else
                {
                    sum[i] += i + 1 - floors[j];
                }
            }
            if(i != 0)
            {
                if(sum[i] < minSum)
                {
                    minSum = sum[i];
                    minFloor = i;
                }
            }
            else
            {
                minSum = sum[i];
            }
        }
        return minFloor;
    }
    /**
     * @param passengers[] 每个楼层对应乘客数目
     */
    public int complexFun(int passengers[])
    {
        int minFloor = 1;
        int i = 0;
        int N1 = 0;
        int N2 = passengers[0];
        int N3 = 0;
        //int minSum = 0;
        for(i = 1; i < fNum; i++)
        {
            N3 += passengers[i];
            //minSum += i * passengers[i];
        }
        for(i = 1; i < fNum; i++)
        {
            if(N1 + N2 < N3)
            {              
                N1 += N2;
                N2 = passengers[i];
                N3 -= passengers[i];
                minFloor = i;
            }
            else
                break;
        }
        return minFloor;
    }
   
    /**
     * @param passengers[] 每个楼层对应乘客数目
     * @param floornum 楼层的数目,确定passengers数组的大小
     * @param firstnum 需要分析楼段的最低楼层数。
     */
    public int complexFun(int passengers[], int floornum, int firstnum)
    {
        int minFloor = firstnum;
        int i = 0;
        int N1 = 0;
        int N2 = passengers[firstnum];
        int N3 = 0;
        //int minSum = 0;
        if(floornum == 1)
            return firstnum;
        for(i = firstnum; i < floornum + firstnum; i++)
        {
            N3 += passengers[i];
            //minSum += i * passengers[i];
        }
        for(i = firstnum; i < floornum + firstnum; i++)
        {
            if(N1 + N2 < N3)
            {              
                N1 += N2;
                N2 = passengers[i];
                N3 -= passengers[i];
                minFloor = i;
            }
            else
                break;
        }
        return minFloor;
    }
   
    /**
     * @param passengers[] 每个楼层对应乘客数目
     * @param k 电梯停留的此数
     */
    public int complexFunK(int passengers[], int k)
    {
        int MAX = 30;
        int i = 0;
        int N1 = 0;
        int N2 = passengers[0];
        int N3 = 0;
       
        int rNum = 0;
        for(i = 0; i < fNum; i++)
        {
            if(passengers[i] > 0)
            {
                rNum++;
            }
        }
        //如果允许停的次数大于用户需要去的楼层层数,则直接停就好
        if(k >= rNum)
        {
            for(i = 0; i < fNum; i++)
            {
                if(passengers[i] > 0)
                {
                    System.out.println(i);
                }
            }
            return 0;
        }
        int blocknum = rNum/k;
        //如果可以恰好等分为k组,则等分
        if(rNum%k == 0)
        {
            rNum = 0;
            int firstnum = 0;
            for(i = 0; i < fNum; i++)
            {
                if(passengers[i] > 0)
                {
                    rNum++;
                }
                if(rNum == blocknum)
                {
                    System.out.println(complexFun(passengers, i - firstnum, firstnum));
                    rNum = 0;
                    firstnum = i;
                }
            }
        }
        else
        {
            //找出乘客人数最少的leftnum个楼层,记录到floorrecord中,并进行排序,从小到大
            int leftnum = rNum % k;
            int floorrecord[] = new int[leftnum];
            int numrecord[] = new int[leftnum];
            int tmp[] = new int[pNum];
            int min = 0;
            int minindex = 0;
            for(i = 0; i < fNum; i++)
            {
                if(passengers[i] == 0)
                {
                    tmp[i] = MAX;
                }
                else
                {
                    tmp[i] = passengers[i];
                }
            }
           
            for(i = 0; i < leftnum; i++)
            {
                min = MAX;
                for(int j = 0; j < fNum; j++)
                {
                    if(tmp[j] > 0)
                    {
                        if(tmp[j] < min)
                        {
                            min = tmp[j];
                            minindex = j;
                        }
                    }
                }
                tmp[minindex] = MAX;
                floorrecord[i] = minindex;
            }
            sort(floorrecord, leftnum);
           
            rNum = 0;
            int firstnum = 0;
            int minfloorindex = 0;
            int kcount = 0;
            //每个分组有blocknum个楼层,人数最少的楼层不参与统计而是就近并入相邻组
            for(i = 0; i < fNum; i++)
            {
                    if(passengers[i] > 0 && i != floorrecord[minfloorindex])
                    {
                        rNum++;
                    }
                    else if(i == floorrecord[minfloorindex])
                    {
                        minfloorindex++;
                    }
                    if(rNum == blocknum)
                    {
                        kcount++;
                        if(kcount == k)
                        {
                            System.out.println(complexFun(passengers, fNum - firstnum, firstnum)+1);
                        }
                        else
                        {
                            System.out.println(complexFun(passengers, i - firstnum + 1, firstnum)+1);
                        }
                        rNum = 0;
                        firstnum = i + 1;
                    }              
            }
        }
        return 0;
    }
   
    private void sort(int arr[], int num)
    {
        int temp = 0;
        for(int i = 0; i < num; i++)
            for(int j = i+1; j < num; j++)
            {
                if(arr[j] < arr[i])
                {
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        floorProblem fp = new floorProblem(15, 8);
        //值以日常生活称呼为主。
        int floors[] = {2,2,3,3,3, 4,4,5,5,5, 5,6,7,7,8};
        //passengers[0]表示去第一层的用户数,在从一楼开始楼梯上升过程中一般为0.其它类推
        int passengers[] = {0,2,3,2,4,1,2,1};
        System.out.println(fp.mathFun(floors));
        //因为数组从0开始,所以转换成日常称呼需要+1
        System.out.println(fp.simpleFun(floors)+1);
        System.out.println(fp.complexFun(passengers)+1);
        fp.complexFunK (passengers, 4);
    }
   
}