课程介绍
任课教师：李皞(hào)，华中科技大学博士，香港城市大学博士后，主要从事智能算法及其在红外光谱、农业信息与环境遥感领域的应用研究，办公室：东 7-505，答疑辅导时间：周四下午。建议提前通过电话、、邮件、QQ联系（电话：暂匿，QQ：暂匿，mail：暂匿）群号：739265561.
2019年9月2日笔记
题目1：
农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会偷吃羊。
请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。
......
题目2：
你请一个工人为你工作七天，用一根金条作为报酬。金条被分为7小块，可以每天支付一块儿。但是，如果你只能将金条切割两次。
请问你如何切割金条，能满足每天支付一块给工人呢？
（面试过的原题）
可以将金条切两刀，分成3份，1/7份、2/7份和4/7份。
第一天，支付工人1/7的报酬。
第二天，支付2/7并让工人找回1/7。
第三天，支付1/7的金条。
第四天，支付4/7的金条，并收回1/7和2/7份的。
第五天，支付1/7份的金条。
第六天，支付2/7份金条，并收回1/7份的金条。
第七天，支付1/7的金条。
题目3：
有5个外观没有区别的物品，重量各不相同。你只有一个天平。请问：
至少需要用天平称多少次，才能将它们按重量的升序排序？
......
算法实例：最大公约数
问：最大公约数算法，可以怎样实现？
顺序实现（辗转相除法）：
int Gcd (int a, int b) {
int r = 0;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
递归形式：
int Gcd(int a, int b) {
if(b == 0) return a;
return Gcd(b, a % b);
}
2019年9月9日笔记
如何证明一个算法可行？
数学归纳法
1、如何证明 "n^3-n" 能被3整除？
2、证明：前n个奇数之和是一个完全平方数
3、反驳：所有的马颜色一样？
......
反证法
1、 如何证明"根号二"是无理数？
......
2、如何证明质数的个数有无穷多个？
......
练习
夜过吊桥
问题：晚上有四个人ABCD要过河，过河必须有手电筒，但只有一个手电筒，有一艘船每次能乘两个人，如果结对过河，快的人要迁就慢的人，求最快过河方法。手电筒只能送不能扔。 过桥速度：A:1min B:2min C:5min D:10min
-
方法一：贪心算法。每次都让最快的人过。先让最快的AB过，然后由快一点的A将手电筒带回来，再让快一点的AC过，再由A带回来，最后AD过。 花费了2+1+5+1+10=19分钟
-
方法二：可以这样考虑：每次两个不同时间的人过河，慢一点的人所需时间减去快一点的人的时间，就是快一点的人浪费的时间。 所以，首先考虑过河（忽略回来的过程），过河要两两搭配（节省时间），一共有四个人，通过遍历找到浪费时间最少的组合，即AB和CD。 然后考虑回来送手电筒的人，因为尽量节省时间，所以首先让AB过河，以便让快的A回来送手电筒，这时，让CD过河，再由B将手电筒送回，AB同时过河。 时间总计：2+1+10+2+2=17分钟
-
如果要最快，最少需要5次运输。
-
在五次运输中，过河成对，回来单人。人数分别是2 1 2 1 2。
-
过河时尽量两两过。
-
有三次两个人过，浪费最少时间的搭配是两次AB和一次CD。
-
回来时让快的一个人送。
-
先让AB过，既是考虑到最少过河时间，也是为了送回时间少（因为有A）。
