算法小白——智力题面试

算法小白——智力题面试

题A：

一个猎人带着一只羊，一只狼和一棵白菜回家，路上遇到一条河。河边只有一条船，但船太小，一次最多只可载猎人和另一样东西过河。但猎人不在时，狼要吃羊，羊要吃白菜。请问怎样才能把狼，羊，白菜都安全运过河？

注解：

这类题一般都有共性，例如，A,B,C都带有不同的属性（如本题物种不同），A,B,C有相互关联的属性（如本题的食物链关系：狼->羊->白菜），此时作为承运人只能携带某一A,B,C。

PS：2020.2.15注：其实这个可以类比为汉诺塔问题，如A的面积<B的面积<C的面积。

首先，运输是带有双向性质的！其次，且要破坏关联属性。

利用这点就很好做了
》：表示运出去
《：表示运回来
X :表示承运人

1. 》X，羊
2. 《X
3. 》X，狼 或》X，菜
4. 《X，羊
5. 》X，菜 或》X，狼
6. 《X
7. 》X，羊

题B：

有4条船,这4条船划到对岸所需的时间各不同,1号船要1分钟,2号船要2分钟,3号船要5分钟,4号船要10分钟.
怎样才能用最快时间把4条船划到对岸?
只有一个人划船,一次最多可划两条船走,但必须要划条回来.

注解：

没啥好说的，运输问题，同上。

1. 》1，2
2. 《2 或《1
3. 》3，4
4. 《1 或《2
5. 》1，2

题C：

小明和小华买了10斤蜂蜜,装在一个大瓶子里.要把蜂蜜平分,只有两个空瓶子,一个正好装7斤,另一个正好装3斤.怎样才能用最简单的方法把蜂蜜分出来

注解：

题目共性：某种物品，可以被连续分割（如本题的蜂蜜），分别有两个互为质数A,B的容量的容器（如3，7），那么必定存在某一数字x在区间[A,A+B]中（假设最小的质数为A）
具体步骤：
容器/容量

1. 10/10，7/0，3/0 ---------------------------初始
2. 10/3，7/7，3/0
3. 10/3，7/4，3/3
4. 10/6，7/4，3/0
5. 10/6，7/1，3/3
6. 10/9，7/1，3/0
7. 10/9，7/0，3/1
8. 10/2，7/7，3/1
9. 10/2，7/5，3/3
10. 10/5，7/5，3/0

题D：

有两根粗细不均匀的香，燃烧时快时慢，但每根香烧完的时间确定是一小时，你能用什么方法来确定45分钟的时间？

注解：

题目属性：给定物品，该物品数量X，给定该物品一种参数Z（如燃烧时间）求另一个参数N
（N=Z/2¹+Z/2²+…+Z/2^X，或N=Z/2^X）
如本题：45=60/2¹+60/2²=30+15

解法：
X个物品同时进行且第一个物品做参数Z/2¹操作，参数到Z/2¹时，下一个物品启动对（Z/2¹）/2的操作，依此类推。

说人话：同时点两个香，其中一个两头都点，当两头都点的燃烧完了再把另一个的两头也点上。

题E：

有10箱罐头,这10箱罐头每箱都是20盒,每盒有1斤.但其中有一箱,每盒只有9两.现在只有一个秤,而且只准秤一次,就要把有问题这箱找出来.
[前提:不能说用手抬,看哪个轻些]

注解：

题目属性：X件大物品，每个X中包含x个小物品，小物品属性为C，问题物品属性为C-h，其中X在序号n时X_n满足(C-h)*x，0<n<=X。
要点因为只能测量一次，所以对每个物品要设置参数，故参数设置为：
X₁=1，X₂=2，…，X_X=X

解法：
第一个拿出一个盒子，第二个拿出二个盒子，以此类推，最后一起称量，少了多少就可以判定为问题物品在哪
h*X？

说人话：第一个拿出一个盒子，第二个拿出二个盒子，以此类推，正确称量是：1+2+3+4+5+6+7+8+9+10=55，少了8两就代表第八个箱子有问题。