【2014-01-08】《编程之美》读书笔记：电梯调度算法

[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2014-01-08 标题《编程之美》读书笔记电梯调度算法分类编程 / java / 编程之美 标签java·编程之美·电梯调度《编程之美》读书笔记电梯调度算法1.8小飞的电梯调度算法解法1解法2最近在学习《 编程之美 》这本书书中提到了很多很经典的算法问题和实现学起来真是耗费脑细胞啊。书中的算法实现使用C编写的这里作者自己写了一部分java的实现如果有错误还请各位读者批评指正。截图版权属于原作者。githubhttps://github.com/cstriker1407/think_in_java1.8小飞的电梯调度算法生成测试数据RandomrandomnewRandom();intfloorNumsrandom.nextInt(10)1;System.out.println(电梯总层数(floorNums));int[]peopleNumsnewint;for(inti0;ipeopleNums.length;i){peopleNumsrandom.nextInt(20);System.out.println(第[(i1)]层的乘客数目为peopleNums);}解法1publicstaticvoidliftDispatchA(int[]peopleNums){intfloorNumpeopleNums.length;intminUse-1;intbestFloor-1;for(inti0;ifloorNum;i){intthisUse0;/* i 代表当前停留楼层从0计数 */for(intj0;jfloorNum;j){thisUseMath.abs(i-j)*peopleNums;}if(minUse-1||minUsethisUse){minUsethisUse;bestFloori;}}System.out.println(最优停留楼层(bestFloor1));System.out.println(耗费人力minUse);}解法2publicstaticvoidliftDispatchB(int[]peopleNums){intfloorNumpeopleNums.length;/* 以电梯停留在第0层开始从0计数 */intN10;intN2peopleNums[0];intN30;intminUse0;intbestFloor0;for(inti1;ifloorNum;i){N3peopleNums;minUsepeopleNums*i;}/* * F(i1) F(i) N1 N2 - N3 * 如果N1 N2 N3则可以推出 F(i1) F(i) * 同时由于从电梯0层开始向上计数因此N1增加N3减小一旦在某一层上N1 N2 N3那么剩余的电梯层必然也会N1 N2 N3 * 就可以不用计算了 */for(inti1;ifloorNum;i){if(N1N2N3){break;}else{bestFloori;minUseminUseN1N2-N3;N1N2;N2peopleNums;N3-peopleNums;}}System.out.println(最优停留楼层(bestFloor1));System.out.println(耗费人力minUse);}