工作之余参加了coursera的公开课functional programming principles in scala，这个课是第三次开讲了，讲师仍然是scala的祖师爷martin odersky先生。个人认为学习公开课最大的阻碍在于有些老师的口音实在是……不忍直视，比如最早在coursera开授公开课的andrew ng（当然他现在是小老板了）。幸好martin大爷的英文口音不是很重，而且课程也不是很难，大家有兴趣可以去学习一下，地址在这里：
好了，烟鬼正转，转到文章的主题上来。每周的课程是通过在线的video lectures来进行的，你可以自行在线观看或者下载到本地，当然在线观看是有字幕的。本地观看你只能自求有字幕组去制作外挂字幕咯。video lectures之后会有assignments，也就是所谓的作业，只有完成了这些作业并提交，才有可能完成这门课的学习哦。
值得一提的是，每周作业的提交会有一个soft deadline和hard deadline，其中前者也叫做due date，就是应该上交作业的最后期限。在due date之前上交作业，作业的分数会根据你作业的质量来决定，在due date之后没延迟一天，作业的分数为实际分数*（1-20%*延迟的天数）。如果你聪明的话，应该算到due date五天之后提交的作业无论多完美，分数都会为0了……恩，hard deadline就是due date后的第五天。
为了防止误操作，也为了给童鞋们一个改过自新，哦不是止于至善的机会，每周作业最多有5次提交机会。作业的分数按照5次中得分最高的那次计算（业界良心啊！）。
废话不多说，现在讲解自己关于week 1作业的思路。
week 1主要讲function & evaluation，内容是函数式编程的一些基本概念、scala的基本语法以及讲了一个递归和尾递归（尾递归会在后续博文中涉及……玛德我又给自己挖坑%>_<%）。总体来说比较简单，关于课程内容这里就不多做介绍，正式进入习题讲解。
本周一共有三道题目，都是在下载后eclipse工程中的main.scala文件中完成代码编写。
exercise 1是关于杨辉三角的（原文成为pascal‘s triangle）：
这个相信大家都不陌生，应该小学的时候就见过。为了照顾低年级同学我还是简单介绍一下，杨辉三角左右两条边上的元素都为1，内部的元素值为其上面两个元素的和。第一个作业就是要写一个函数，任意给定元素的位置（以行和列的形式），求出其值。
怎么样，简单吧？人家还给出了函数原型：
ok，现在就来分析一下。碰到这种问题，我们首先想到就是使用递归来做，那么递归一般来讲有两个要素，递归调用关系和终止条件。
1.递归调用关系：杨辉三角的性质已经决定了，元素的值等于其上一行的两个元素值之和，即value(c, r) = value(c, r - 1) + value(c - 1, r - 1)。这样就可以看到value的两个参数会越来越小，直到达到终止条件；
2.终止条件：杨辉三角的左右两条边上的元素均为1，即value(0, r) = 1, value(x, x) = 1，其中前者表示左边上的元素、后者表示右边上的元素
有了以上两个条件，我们的代码就水稻渠成了！
第二个作业是parentheses balancing，就是括号匹配。函数原型如下：
以list[char]的形式给出一个字符串，字符串内包含若干左括号和右括号，要求判定其中的括号是否能够匹配。若能返回true，否则返回false。
题目中各给出了两个正反例：
其中前两个是正例，我们可以看到其中的左右括号完全匹配，应该返回true；后两个是反例，其中第三个只有右括号没有左括号，第四个的左右括号不匹配。
我们仍然用递归来解这道题目，初步观察输入数据中会包含非括号字符，这些字符对我们的处理过程会造成一定的麻烦，并且去掉他们之后不会对结果有影响。所以我们在预处理部分首先去掉输入中的非括号字符。
剩下的就都是括号了，按照递归的思路，我们仍然要确定递归调用关系和终止条件：
1.递归调用关系：相信大家都玩过俄罗斯方块，当一行的所有像素都被填满实体时，则消除此行。我们在此处也借用这种方法，那么我们就要思考，在什么情况下可以去掉一对括号呢？有三种情况：字符串的前两个分别是（和）时；字符串的最后两个分别是（和）时；字符串的首尾分别是（和）时。那么，消除的次序对结果是否有影响呢？我们来看一个简单的例子：()()，这个输入符合以上的三种可以消除的情况，那么应该先按照哪种情况来消除呢？明显地，如果按照第三种情况消除首尾，那么剩下的)(就不能匹配了，这就造成了错误的判断。如果首先按照前两种情况消除括号对就不会出现这种问题。所以消除的次序应该是将第三种情况放到最后。
2.终止条件：从递归调用关系可以观察到，在一直有括号匹配的情况下，字符串的长度会越来越短，当长度为0时，我们到达了一个边界，在这个边界上我们可以返回true。另外，因为括号都是成对匹配的，所以当字符串的长度为奇数时，我们可以直接返回false。最后，如果满足消除条件的三种情况都不存在，也需要返回false。
所以代码如下（我们定义了一个辅助函数）：
第三道题目是counting change，也就是算法界著名的换零钱系列问题之一。
题目给定一个数额以及零钱的种类，要求计算出使用零钱种类分解数额的可能方案个数。函数原型如下：
同样考虑递归调用关系和终止条件：
1.递归调用关系：从零钱种类中拿出一个零钱面值coin，那么金额money的换零钱方式有两种：要么使用零钱面值coin，要么不使用。 如果不使用零钱面试coin，那么money的换零钱方式就等于使用去掉面值coin后的零钱种类分解money；如果使用零钱面试coin，那么money的换零钱方式为money - coin使用原始零钱种类换取的方式。
这个地方说的可能比较绕。概括的说，将总数为money的现金换成n种零钱的不同方式的数目等于：
a.将现金数money换成除第一种零钱外的所有其他零钱的不同方式数目，加上
b.将现金数money - coin换成所有种类的零钱的不同方式数目
其中coin为第一种零钱的面值，a、b中第一种零钱可以替换成任意一个零钱面值。
2.终止条件：因为在递归调用关系中，money和零钱集合都是缩小的，所以考虑边界情况：
a.如果money为0，则换取零钱的方式有1种，即所有面值零钱的个数为0
b.如果money小于0，则换取零钱的方式有0种
c.如果零钱集合为空，则换取零钱的方式有0种
这三种边界条件的判断先后关系是否影响结果呢？太晚了不想分析了，留给大家去思考吧
好，贴代码：
到此为止，week 1的三个作业全都分析完成。总体来看还是比较简单的。本人代码写的很粗糙，如果有一起上这门课的，还望不吝赐教。
你也可以在github上获取所有我关于这门课的作业代码：
参考：
《计算机程序的构造和解释》 harold abelson, gerald jay sussman, julia sussman著，裘宗燕 译
声明：
本文为原创，禁止用于任何商业目的，转载请注明出处：
![git关联问题解决[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)