Fork me on GitHub

算法谜题一

发表于 | 分类于
字数统计: 1.2k 字 | 阅读时长 ≈ 4 分钟

唔，总算还是开始了算法的学习与研究了。在这里写下每天做出来的算法题吧。

什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

我使用的书籍——《算法谜题》

《算法谜题》是一本经典算法谜题的合集。书中包括了一些古已有之的谜题，数学和计算机科学有一部分知识就发源于此。 《算法谜题》可以为对算法感兴趣的广大读者提供系统丰富而实用的资料，能够帮助读者提升高阶算法思维能力。《算法谜题》适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及在准备面试的应聘者和面试官阅读参考。

题目

简单谜题

狼羊菜过河

题目概述

一个人在河边，带着一匹狼、一只羊和一颗卷心菜，
他需要用船将这三样东西运至对岸，然而，这艘船的空间有限，只容得下他自己和另一样东西(或狼或羊或卷心菜)。
若他不在场看管的话，狼就会去吃羊，羊就会去吃卷心菜。此人如何才能把这三个“乘客”都送至对岸？

解答

我们首先考虑第一次移动，如果移动菜或者狼，那么剩下的对象就会“冲突”，因此我们将羊作为第一次移动的目标。人再回到这边，接下来有两个选项，载菜或者载狼，首先考虑载狼吧，把狼载过去，再把羊载回来，这边再把菜带过去，然后回来接羊，任务完成。那么载菜又如何呢，把菜载过去，再回来接羊，任务也完成了。不过，第一种方案似乎要更为简洁。

伪代码实现
1
2
3
4
5
6
7
8
9
10
public boolean crossTheRiver(void){
	while(!isOk(there)){					// 当对岸没有达到要求时
		tryMove(object);				// 尝试移动一个对象
		checkAvailable(here);				// 检查此边是否冲突
		checkAvailable(there);				// 检查对面是否冲突
		if(isAvailable(here)&&isAvailable(there))	// 如果两边都可以
		Move(object);					// 移动对象
	}
	return true;						// 完成后返回真值
}

手套问题

题目概述

抽屉中有20只手套。其中5双黑手套，3双棕色手套和2双灰手套。你只能在黑暗中挑手套，并且只有将手套挑出之后才能检查其颜色。最多要挑几次才能满足以下条件？
(a)至少挑出一双颜色匹配的手套。
(b)所有颜色的手套都至少挑出一双匹配的。

解答

(a)考虑最坏的情况：摸了10次，10双手套的一只都在手上了，那么再来一次就可以配上一双了。所以答案是11次。
(b)同样的，考虑极端坏的情况：把5双黑的摸齐了，3双棕色的也不放过，就差一只灰色的了，一共就是5×2+3×2+1+1+1=19次(灰色手套2只单的加上最后凑上双)

伪代码实现
1
//鄙人才疏学浅，不会

矩形切割

题目概述

找出所有将一个矩形分成n个直角三角形的方法(n>1)。并且将这种切割的方法归纳成一个算法。

解答

当n=2时，很容易考虑到对角线，一个对角线将一个矩形分为两个直角三角形。那么，当n>2时，又该怎么办呢？我们不妨在直角三角形中作高线，这条高线将这个直角三角形分成了两个新的直角三角形。那么，答案就显而易见了：沿对角线切割，然后找到一个直角三角形作出高线，直到数目达到要求。

伪代码实现
1
2
3
4
5
6
7
8
9
10
public void seperateRectangle(int triangleRequired, Rectangle rectangle){
	while(numOfTriangle < triangleRequired){				// 当数目不足时进行分割
		if (numOfTriangle == 0){						// 当第一次进行分割时
			linkDiagonal();						// 连接(矩形的)对角线
		}else{
			Triangle triangle = new findTriangle(rectangle)		// 找到一个所需要的直角三角形
			drawTriangleAltitude(triangle);				// 作出高线
		}
	}
}
0%