cstriker1407的笔记本

好记性不如铅笔头

java, 编程, 编程之美

《编程之美》读书笔记:电梯调度算法

最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊。书中的算法实现使用C编写的,这里作者自己写了一部分java的实现,如果有错误,还请各位读者批评指正。截图版权属于原作者。
github:

https://github.com/cstriker1407/think_in_java

1.8小飞的电梯调度算法

生成测试数据:

	Random random = new Random();
		
	int floorNums = random.nextInt(10) + 1;
	System.out.println("电梯总层数:" + (floorNums));
	int[] peopleNums = new int[floorNums];
	for (int i = 0; i < peopleNums.length; i++)
	{
		peopleNums[i] = random.nextInt(20);
		System.out.println("第[" + (i+1) +"]层的乘客数目为:" + peopleNums[i]);
	}

解法1:

	public static void liftDispatchA(int [] peopleNums)
	{
		int floorNum = peopleNums.length;
		
		int minUse = -1;
		int bestFloor = -1;
		
		for (int i = 0; i < floorNum; i++)
		{
			int thisUse = 0;
			/* i 代表当前停留楼层(从0计数) */
			for (int j = 0; j < floorNum; j++)
			{
				thisUse += Math.abs(i - j) * peopleNums[j];
			}
			if (minUse == -1 || minUse > thisUse)
			{
				minUse = thisUse;
				bestFloor = i;
			}
		}
		
		System.out.println("最优停留楼层:" + (bestFloor + 1));
		System.out.println("耗费人力:" + minUse);
	}

 解法2:

	public static void liftDispatchB(int [] peopleNums)
	{	
		int floorNum = peopleNums.length;
		
		/* 以电梯停留在第0层开始(从0计数) */
		int N1 = 0;
		int N2 = peopleNums[0];
		int N3 = 0;
		int minUse = 0;
		int bestFloor = 0;
		for (int i = 1; i < floorNum; i++)
		{
			N3 += peopleNums[i];
			minUse += peopleNums[i] * i;
		}
		
		/*
		 * F(i+1) = F(i) + N1 + N2 - N3
		 * 如果N1 + N2 > N3,则可以推出 F(i+1) > F(i);
		 * 同时由于从电梯0层开始向上计数,因此N1增加,N3减小,一旦在某一层上N1 + N2 > N3,那么剩余的电梯层必然也会N1 + N2 > N3,
		 * 就可以不用计算了
		 */
		for (int i = 1; i < floorNum; i++)
		{
			if (N1 + N2 > N3)
			{
				break;
			}else 
			{
				bestFloor = i;
				minUse = minUse + N1 + N2 - N3;
				N1 += N2;
				N2 = peopleNums[i];
				N3 -= peopleNums[i];
			}
		}
		
		System.out.println("最优停留楼层:" + (bestFloor + 1));
		System.out.println("耗费人力:" + minUse);
	}

 

Leave a Reply

13 − 3 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

Theme by Anders Norén

苏ICP备16032087号