Functional Programming Principle

课程介绍

1. 名称： Functional Programming Principles in Scala

2. 平台： Coursera

3. 难易度：中级

4. 地址：https://www.coursera.org/learn/progfun1/home/info

5. 授课教师：Martin Odersky （Scala的作者）

评价

能听到Scala作者的视频课程，还是很惊喜的。课程相对来说，趣味性不强，但是很长知识。

比如，Scala程序中不推荐使用return语句，如果你在程序中遇到没有使用return，按经验推理程序应该正常返回，但是没有，那么就有可能是你的分支没有写完整，Scala编译器没有推理出来你的隐式return。

课堂笔记

week1 笔记

我们知道求浮点数是否相等要判断两个数的差值小于某一个阈值即可。那么比如求用牛顿法解平方的时候，遇到特别大的数或小数，就需要稍微改进下这种方法了，我们只需要判断两个数的差值，与被开方的数比值小于某一阈值即可。

week1 作业

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

编写一个递归程序计算出，不同面额的硬币加和等于某一整数的组合数。例如：整数是4，不同中的面额是【1，2】，那么它的组合数就是3种: 1+1+1+1, 1+1+2, 2+2。

思路：刚开始一直使用的是顺序思维解题的，比如先计算出单一的组合，然后是两两的组合，然后是三三的组合，以此类推，但按照这种思想写代码感觉很复杂。无奈，上网搜索一番，还真看到答案了，看了一下，原来很简单，只不过是缺乏经验或数学思维想不到。其实这就是算法中的分而治之算法，将一个复杂的问题分解成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，愿问题的解即子问题的解的合并。

那么此问题的解法就是分出两个分支，一个分支求减少硬币种类的组合数（比如：当前硬币种类是[1, 2, 3], 那么接下来求[2, 3]，依次类推，直到硬币种类不可以在减少为止。）；另一个分支求当前硬币种类的组合数。最后两分支加和即最终的组合数。终止条件是，子递归中当整数(amount)为0时，即为1种，返回1，当整数为负或者硬币种类为空的时候，此组合失败，返回0。

图：硬币种类：【1， 2， 3】，整数（amount）：6

硬币种类分治法.png

代码：https://gist.github.com/tongtie/9c72f261aa139fc09b58c6ca24db6a50

参考文献

1. 分治法