I suck at algorithms, even though I have a Machine Learning and Algorithms master degree. It makes me frown everytime in coding interviews. So I decided to practice more often, hope that I can get better at it. At least not afraid of it. Now this is the first one. Problem Rotate a square matrix clockwise concentrically by 1. For example: 1 2 3 4 5 6 7 8 9 will become
断断续续的看这个 Percy Jackson 系列已经有很长时间了，第一本和第二本都是在电子书上看完的，最近看到书店在打折，正好有全套在卖，就买了，现在正在看第四本。虽然封面是丑了一点，但是半价的话也就忍了先。 典型的少年读物，情节紧凑，到处都是怪物和神啊什么的，小孩看了应该很激动。不过练习英语还不错，生词量不多。这个是9岁+读物啊。。。
Time and Space of Recursion
Learn more about recursion
今天通过一个例子，来谈一谈第归的时间和空间效应。 例子很简单，计算 a 的 n 次方。 我们来对比一下两种第归算法的时间和空间的消耗。 第一个方法很直接。思想就是要计算 a 的 n 次方， 只要计算 a 的 (n - 1) 次方， 然后结果在乘以 a 。如下： (define (expt a n) (if (= n 0) 1 (* a (expt a (- n 1))))) 为了更直观的理解这个算法，我们来计算一个例子， 2 的 3 次方。 (expt 2 3) (* 2 (expt 2 2)) (* 2 (* 2 (expt 2 1))) (* 2 (* 2 (* 2 (expt 2 0)))) (* 2 (* 2 (* 2 1))) (* 2 (* 2 2)) (* 2 4) 8 我们能能明显看到这个算法的“形状”是一个三角形。每一行代表一次计算，也可以理解成时间的消耗。而每一列则代表计算机需要记住的内容，比如说一共要乘以几个2，也可以理解成空间的消耗。我们可以看到，随着 n 的增大， 这个算法的时间和空间消耗也随之增大。而且增大的速度都是线性的。时间的消耗随着 n 的增大而增大很好理解， n 大了， 计算花的时间也相应长了。但是空间消耗可不可以不增大呢？下面我们就来看另一种算法。
Simple example of recursion
Learn more about recursion
今天读到SICP里的一个介绍recursion的例子，用牛顿猜想来计算平方根。 首先，介绍了计算机程序和数学方程的区别。数学方程大多用的是描述法（declarative）。比如说这个平方根，数学上只需要说： 如果x的平方等于y，而且x大于0，那么x就是y的平方根。 这是一种很高层次的描述，通过描述，来限制答案的域。如果能直接用到计算机里，问题就简单了。大概写出来的程序就是这个样子： func sqrt(x): @ * @ = x; @ > 0; return @; 让计算机去处理计算细节。这当然是一种理想的情况，如果都能这样写程序，那就完事大吉了。这就叫描述性编程(Declarative Programming)。 当然现在还做不到这么绝对，所以我们只能自己写如何进行细节的计算来得到我们的结果。这就叫做命令式变成(Imperative Programming)。 总体来说，描述性编程比命令式编程要容易理解的多，因为不用自己下达命令给计算机，只需要对问题进行描述，计算机自己会找到答案。典型的例子就是xml配置文件，人们把对系统的需求和配置写在一个单独的xml文件里面，然后让计算机自己去执行相应的命令。 好了，现在进入正题。牛顿猜想的原理如下： 要计算x的平方根，先猜想一个答案y，然后用 (y + x / y) / 2 来得到新的优化过猜想。反复进行，知道得到满意的猜想。 首先，我们先来定义一些辅助方程。 (define (abs x) (if (< x 0) (- x) x)) (define (square x) (* x x)) (define (average x y) (/ (+ x y) 2)) 接下来我们来写主程序。 (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) 这个程序用第归的方法实现了牛顿猜想。
最近因为工作的原因在学clojure，其实我一直都想学一个LISP语言，现在终于有人付钱让我学啦，呵呵。 最早接触到LISP是因为Emacs。当年在研究生时给大学的自然语言研究组帮忙的时候，教授就是Emacs的资深（20年+）用户，我也就开始一点一点的接触了，后来经过一段时间的压迫性的苦练，终于入门了。有一天无意中发现了Emacs Lisp Intro，就开始学习emacs lisp，可惜半途而废了。 因为clojure还比较新，所以没有什么太多资料。我就买了一些关于LISP的经典书籍，比如这个 《Structure and Interpretation of Computer Programs》。但由于本人的拖延症的病情，所以打算从今天开始读第一章了（第二遍尝试）。。。 在开篇有一段引言如下： ``I think that it’s extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines.
