Fork me on GitHub

算法谜题二

发表于 | 分类于
字数统计: 657 字 | 阅读时长 ≈ 2 分钟

这是《算法谜题》中的第4到第6题。

题目

简单谜题

士兵摆渡

题目概述

25个士兵组成的小分队需要渡河，可是河宽且水深，周围也看不到桥。他们发现河岸边有一个小船，两个12岁的男孩正在上面玩耍。船很小，仅能承载两个男孩或一个士兵的重量。士兵应怎样渡河？在你用的算法中，船从一个岸边到另一个岸边来回共计几次？

解答

考虑到船一次只能载一个士兵，那么每一次就有一个士兵驾船前去对岸，再由1个小孩驾船回来。一次可以将2个小孩运载至对岸。那么过程就很清晰了：2个男孩过河->1个男孩回来->一个士兵过河->另1个男孩驾船回来，重复至所有士兵都渡河完成。那么这样一来，船一共靠岸100次。

伪代码实现
1
2
3
4
5
6
7
8
public void soldiersCrossRiver(int numberOfSoldiers){
	while(!allSolidersAreCrossed()){
		boat.SendPeople(boy1, boy2, there);	// boat.SendPeople(object1, object2, toPlace);
		boat.SendPeople(boy1, here);		// boat.SendPeople(object, toPlace)
		boat.SendPeople(soldier, there);
		boat.SendPeople(boy2, here);
	}
}

行列变换

题目概述

变换前

图2.1 行列变换前的数字阵列
变换后
图2.1 行列变换后的数字阵列


怎样才能将图一中的数字阵列进行变换得到图二？要求只能进行行列变换。

解答

线性代数的知识告诉我们，对行列式进行行列变换不改变元素的相对位置。因此答案是不可以的。

伪代码实现
1
// 不存在的

数数的手指

题目概述

一个小女孩正在用左手手指数数，从1数到1000。她从拇指算作1开始数起，然后，食指为2，中指为3，无名指为4，小指为5。接下来调转方向，无名指算作6，中指为7，食指为8，大拇指为9，接下来，食指算作10，如此反复。问如果她继续按这种方式数下去，最后结束时是停在哪根手指上？

解答

我们不妨先看下前几个数字，找找规律：
数字特征

前几位数字与手指的匹配规律


具体的判断方法就不用我多说了8。当数数到1000时，对应的手指是食指。

伪代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
public Finger getTheFinger(int countNumber){
	int preCaculateNum = countNumber % 8;
	Finger result;
	switch (preCaculateNum){
		case 1: result.setFinger(thumb); break;
		case 2: case 0: result.setFinger(foreFinger); break; 
		case 3: case 7: result.setFinger(middleFinger); break;
		case 4: case 6: result.setFinger(ringFinger); break;
		case 5: result.setFinger(littleFinger); break;
		default: result.setFinger(null); break;
	}
	return result;
}
0%