手动安装mysql

在战舰少女贴吧里,偶尔能看到的一个说法叫做“这活动我用脚打都能过”,意思是活动关卡很容易(实际上有时候并非真的那么简单,仅仅是调侃)。在安装mysql这件事情上,也有用脚安装和用手安装两种。

典型的用脚安装就是使用系统的包管理器。例如在我的LinuxMint系统中,在shell中键入下列命令就可以装上mysql

1
sudo apt-get install mysql-server

遗憾的是,包管理器并不是任何时候都可用的。举个例子:以前在UC,研发团队是可以申请到一些机器用于分配给开发人员使用的,但如果要在上面使用数据库,那么多半需要开发人员自己动手部署。此外,只要掌握了手动部署单个mysql实例的方法,就可以轻松地在一台机器上部署多个mysql实例了,而这正是我最近需要完成的一个任务。为了方便自己很久之后查阅,也为了帮到其他有此类需求的程序员,我写了这篇手动安装的指南。

初始化数据库

安装mysql的第一步,是创建数据库运行所需要的一系列文件。在5.7.6版本之前的mysql中,这个过程是由mysql_install_db这个脚本完成的。在5.7.6的发行版中,这个功能被集成到了mysqld中,下面的操作也是基于mysqld实现的。mysqld提供了执行用于初始化的命令行选项:

  • –initialize
  • –initialize-insecure

–initialize-insecure会为数据库的root账户设置空的密码,方便稍后登录,因此将选用这一个初始化的方法。

为了初始化数据库,还需要指定mysql的安装目录和存放数据文件的目录。安装目录即mysql的二进制安装包解压缩后生成的目录,而存放数据文件的目录则可以自由选择。这两个路径分别传递给mysqld的–basedir和–datadir参数。为了方便起见,也为了避免mysqld启动后读取了已存在的mysql配置文件造成干扰,我将这两个参数写到了配置文件中。在我的机器上配置文件路径是~/local/mysql/my.cnf,内容如下

1
2
3
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data

需要注意的是,根据官方文档的说明,datadir所设置的目录,必须为一个尚不存在的目录或者是一个空目录。在我的系统中,/home/liutos/data/mysql/data是一个尚未创建的目录。

现在可以进行初始化了。因为在我的系统上解压缩后的目录为~/local/mysql,因此在shell中执行的命令为

1
2
cd ~/local/mysql/
./bin/mysqld --defaults-file=/home/liutos/local/mysql/my.cnf --initialize-insecure --user=`whoami`

启动数据库服务

完成初始化后就可以启动mysqld了。启动的命令为

1
./bin/mysqld_safe --defaults-file=/home/liutos/local/mysql/my.cnf --user=`whoami` > /dev/null 2>&1 &

由于在我的系统中,已经使用包管理器安装了mysql服务并且正在监听着3306端口,为此必须修改即将启动的mysqld进程所监听的端口。监听的端口号可以通过配置文件来指定,修改后的配置文件如下

1
2
3
4
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307 # 新增该行

现在可以执行刚才的启动命令了。成功启动后,使用netstat -apn | grep '3307'应当可以看到类似下文的输出

1
tcp6       0      0 :::3307                 :::*                    LISTEN      30898/mysqld

登录数据库

一番波折,终于可以登录了。因为当初是使用–initialize-insecure执行初始化的,root账户没有登录密码,因此在shell中键入下列命令登录

1
mysql -u root --skip-password -h 127.0.0.1 -P 3307

登录后建议为root账户设置登录密码。例如,我要给root账户设置密码为1234567,就执行下列SQL语句

1
ALTER USER 'root'@'localhost' IDENTIFIED BY '1234567';

UNIX socket配置

按照上述步骤启动后,mysqld会在系统的/tmp目录下创建一个mysql.sock文件。此时如果再按照上述步骤是无法启动另一个mysql实例的,因此每一个mysqld必须使用单独的.sock文件。这可以通过配置文件来实现,在我的系统上的配置如下

1
2
3
4
5
[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307
socket = /home/liutos/local/mysql/mysql.sock # 新增该行

报告层数的广度有限搜索

题外话

大一的时候为了装13就自己去图书馆借了很多讲解和CS有关却又还没有教或者不会教的内容的书来看,其中就有数据结构那一类的。不过我已经忘记了当时去图书馆借到的是什么样子的书了,只知道书的封面是蓝色的(要是有空的话去图书馆找找就可以知道了=。=)。不过说到数据结构方面的书,在国内大部分和计算机或者信息技术沾边的专业的学生中,比较广为人知的应该既不是《算法导论》,也不是《算法概论》,而是编者为严蔚敏的那本《数据结构C语言描述》吧。我也有幸看过,并且印象中那时候觉得那本教材还是不错的。只不过现在道行稍微有点高了,就开始有点鄙视当初习得技能的恩师了——哦,有种过河拆桥的感觉。

百度面试题

第一次去百度面试时,面试官看起来和蔼可亲,同样给出的问题也很和蔼可亲。当时的问题有三道,第一道是让我随意写一个二叉树的遍历的代码,我挑了个深度优先搜索来写,因为我觉得这货算得上是最容易写的代码之一了。然后面试官就让我用广度优先搜索再写一遍,我就再写了一次。说真的,队列那一部分的处理还真是让人头大,尤其是我居然稀里糊涂地把队列的处理和栈的处理混淆在一起了,结果代码看起来也是稀里糊涂的。要不是面试官大慈大悲耐心地和我商量着来修改,我可能就没有遇到第三题的机会了。不过终究第二题还是安全过关了,之后就是第三题了:给广度优先搜索增加一个返回所找到的关键字在二叉树的哪一层的功能。

老实说,听到题目的当即我就想到了一种最最最简单的办法,就是修改二叉树的定义,给它增加一个数据字段来存储每一个节点究竟位于第几层就可以了嘛,唉真是简单得无趣啊=。=不过面试官说不允许这样做,那好,我再换一种办法,就是增加一个新的队列来存储每一个进入队列的节点究竟是位于哪一层的。因为一开始肯定是从第一层开始的,所以只要中间的每一个节点都不要漏掉,那么根据父节点的层数就可以推知直接的子节点的层数,那么在将每一个节点入队列的时候都有办法知道它们是在哪一层的。嗯,这个办法也很好,不过面试官也不允许增加新的队列,呃。。你这不是存心刁难我么!还好,把队列的版本稍微修改一下就可以去掉队列了,不过要增加广度优先搜索的实现函数的参数。

第三个版本

首先要明确这个函数的参数与返回值究竟是怎样的。因为当时这个功能是用C语言来实现的,所以只允许函数调用有一个返回值。在一开始写的两个版本中函数的返回值是所找到的二叉树中的节点,所以在第三个版本中也依然返回所查找到的节点或者是在找不到的时候返回C语言中的空——NULL。那么这样一来节点所对应的深度的信息只能通过下面的两种方法来返回了:

  • 全局变量
  • 传出参数

我选择了第二种,因此查找功能需要增加一个传出参数depth,它的类型声明是int *。因此查找功能的入口函数的整体类型声明为:

TreeNode dfs_search_tree(Tree tree, char target, int *depth)

(我觉得标识符取得还不错,不用解释了吧→_→)那么dfs_search_tree这个函数要如何实现具体的功能呢?现在我们是为了要在队列的版本上进行修改来实现查找功能的,那么原本需要使用队列来存储的深度信息现在应该交给函数的参数来存储,但是这个参数不能添加到入口函数中,因此我们需要一个辅助函数,就叫做dfs_search_tree_aux函数好了,它至少需要上面的函数所拥有的三个参数,并且还需要一个用来传递而不是用来返回的深度的信息,不妨声明为int *nd。

试想一下,如果我们在处理第i层的一个节点,那么显然可以知道它的左右子树的根结点如果存在,必定会位于第i+1层,因此在广度优先搜索的函数递归调用的时候,nd参数的传递是以加一的形式进行的,即遍历子树的时候nd必定要比测试当前节点的时候加一。不过实际上这样子是不可行的,因为我们不是在测试了父节点之后就立即递归调用函数来测试两个子节点,在测试父节点的时候,只是把两个子节点给放进了队列罢了,因此没有办法通过简单地直接加一的方法来传递深度参数。我们需要的信息是,现在这个节点和上一个节点到底是不是在同一层。

确定是否在同一层的一个办法,是知道每一层的节点的数目。例如第一层显然只能有一个节点,因此当测试了第一个节点后就可以知道第一层已经测试完了,那么接下来的函数调用的nd参数的值就至少应该增加一,并且应该把表示一层的节点个数的参数设置为第二层的对应值。第二层的节点个数可以利用遍历第一层的时候来得到。例如对于第i层的节点,如果每一个节点都有两个子节点,那么第i+1层的节点数目就是第i层的两倍,对于其它情况也可以很简单地推算出来。因此,我们需要额外的两个参数current_count和next_count,来分别存储当前层剩下的节点数目以及下一层目前所探测到的节点数目。现在,我们可以写出辅助函数的原型了:

TreeNode dfs_search_tree_aux(char target, int depth, int *nd, Queue queue, int current_count, int next_count)

其中没有和dfs_search_tree一样的tree参数,因为在广度优先搜索中,树的节点是存储在队列queue中的。dfs_search_tree_aux这个函数的逻辑是这样子的:

  1. 先看看队列是否为空。如果是就说明节点都已经测试完了,仍然没有找到目标节点,所以返回NULL;
  2. 从队列中取出最早进入的节点。
  3. 既然已经开始测试新的节点,那么当前层的剩余节点数就少了一个,因此current_count要自减一;
  4. 测试节点的关键字。如果是一致的就先设置传出参数nd为depth,然后返回对应节点的指针;
  5. 如果测试失败,那么就说明函数需要继续递归调用下去了。这时候需要先决定current_count和next_count的值。
  6. 如果current_count为0,也就是说这一层没有节点剩下了,那么就让depth加一,把当前的节点数目(current_count)设置为下一层的节点数目(next_count),然后下一层的节点数目重新归零。
  7. 接下来,测试左子树是否为空。如果非空,就把当前节点的左子树根结点入队,并给next_count加一。同样的,右子树也是类似的处理办法。
  8. 最后,递归调用辅助函数本身。

最后给出代码链接好了:https://github.com/Liutos/CLab/blob/master/binary_tree/prototype.c

递归、闭包、面向对象

话题由来

参加了不少IT公司的笔试,有些题目遇到的次数还是比较多的,例如给一系列字符和一个空栈,询问你选项中的哪一个是不可能出现的出栈顺序这样的问题。另外一道题目,就是我这里要拿来讲的,不过我讲的和题目本身不直接相关,只是恰好和题目所要完成的任务有重合罢了。这道题目就是“给出一颗二叉树的先序遍历和中序遍历的输出结果,请给出这个二叉树的后序遍历的输出结果”。

这道题目其实非常简单,尽管我一开始遇到的时候仍然是手足无措的(谁没有年少无知过呢对不),不过一两次之后就轻车熟路了,知道了这样的题目的行之有效的解法。举个例子,先序的序列和中序的序列分别是”abfce”和”bface”,那么这棵二叉树就是这样子的

可以知道,后序遍历的输出结果为”fbeca”。怎么得到这棵二叉树呢?其实很简单,首先根据先序遍历的定义,所以在先序遍历结果中的第一个元素一定是整棵二叉树的根结点,也就是a,那么根据中序遍历的定义,在a左边出现的序列就是左子树的中序遍历结果,在a的右边的就是右子树的中序遍历结果,它们分别是”bf”和”ce”。并且可以知道,在先序遍历中与它们对应的片段应该也是”bf”和”ce”。在对”bf”做同样的处理,就可以知道b是根结点,而左子树为空且右子树为单节点f,另一棵子树的根结点为c且左子树为空,右子树为单节点e。

那么,怎么用程序来自动化呢?

C语言的递归版本

以文字来描述根据先序和中序来构造二叉树的算法还是很好理解的。为了描述方便,取几个名字。把先序遍历的结果叫做preseq,中序遍历的输出结果叫做inseq,并且把它们当作C语言中的数组那样来取出元素(例如preseq[0]表示第一个元素),再给它们一个方便取出片段的语法糖,例如preseq[0..2]表示取出下标从0到2的三个元素组成一个新的输出序列。

首先,取出preseq的第一个元素preseq[0],可以知道它肯定是目前正在处理的整棵二叉树的根结点,接着在inseq中寻找这个根结点,于是就可以把inseq分成三段,第一段是左子树的中序输出结果inseq1,第二段是根结点本身inseq2,第三段则是右子树的中序输出结果inseq3。同样的,preseq也可以分成三部分:第一个元素就是根结点,记为preseq1,然后是和inseq1等长的一个子串,也就是左子树的先序遍历的输出结果,剩下的,就是和inseq3等长的子串,即右子树的先序遍历输出结果了。既然有得到了先序和中序遍历的输出结果各一对,那么接下来只要对对应的一对输出结果递归调用原来的功能就可以了。递归的base case,就是输出结果只有一个元素的情况。这时候只需要生成一个没有左右子树的节点即可。

我写了两个版本,第一个是很简单很直接的实现,就是完全按照上面所说的思路来做的,因此其中充满了字符串的复制操作,详见代码(其中的make_tree_by_prein函数就是实现了上面的算法的代码)

第二个版本避免了字符串的复制操作,不过没有第一个版本的make_tree_by_prein函数那么好理解了。这里只有修改后的make_tree_by_prein函数的代码

CommonLisp和Java的版本

C语言中的第二个版本在CommonLisp和Java里面可以改得更好一点,这多亏了CommonLisp的闭包特性和Java的OO方式。在C实现的第二个版本中,make_tree_by_prein函数有两个参数,而辅助函数make_tree_aux则需要两个参数。其中参数preseq和inseq是两个在传递过程中完成不会被修改的参数,它们之所以被作为参数,仅仅是因为C语言中只有两种方式在函数间共享一些信息:

  • 函数参数
  • 全局变量

因为不想使用全局变量,所以只好在参数列表中动手脚了,不过在CommonLisp和Java的实现,就有办法可以在函数之间以受控的方式共享信息。例如下面用CommonLisp实现的make-tree-by-prein函数

函数make-tree-by-prein利用labels在函数体内部定义了一个闭包aux,preseq和inseq则是在词法范围内可见的变量,因为在aux内部依然可以访问到它们,这样就不需要将它们作为aux的两个参数来进行传递了。而Java的实现也是类似的,在Java中方法从属于类,并且它们可以共享同一个类的实例中的所有变量,因此直接使用这些变量即可,代码如下(因为Java同样没有办法定义内部函数的关系,所以只好定义一个用private修饰的方法makeTreeAux了。)

不是有人说吗?OO是穷人的闭包;闭包是穷人的OO;-)

后记

总算把讲思路贴代码的东西弄完了,可以好好扯淡一番了=。=话说上课的时候有个考研的同学找我讲话(班里的一名胖子,在算法方面有很厉害的嗅觉),就是问我对于用算法来实现“根据先序和中序输出结果如何构造二叉树”有没有思路。递归的方法其实很容易就可以想出来了,加之我之前已经想过这类题目要怎么系统地解决,所以很快就说出来了。然后我就觉得用C语言可以像上面那样写出一个高效(即没什么字符串复制操作)的版本,接着又想到这个可以用Lisp(或者其它带闭包的语言)来实现得更好,又想到了用Java也可以实现闭包的那类效果,再接着又觉得可以发篇文章来讨论讨论,于是就有这样的一篇东西了。

对于具体实现某个功能的技术,我貌似没有特别地挑剔,甚至可以说,对于加入到编程语言中的任何特性,我都没有太挑剔的,只要好用,那么我就很可能会接纳——当然了,我也无法保证自己在找到一个反例之后不会把这句话给改掉当作自己没有这么说过,不过暂时没有想到这种情况,所以就先当作我是这样的人吧。举个例子,对于Haskell我很喜欢,也很喜欢纯函数语言的说法,即“纯函数是非常有利于程序编写的”。不过对于副作用我也没有持完全拒绝的态度,即使我在编程的过程中也会尽量遵循函数式编程的规矩(尽量避免副作用)。可是副作用实际上避无可避,倒不如拥抱它们。或许正是因为这个原因,我才会喜欢OCaml更甚于Haskell吧——至少目前是这样的。

我也喜欢惰性计算,尤其是其带来的效果——无限长的列表推到看起来实在是帅得不行,并且还可以使得编写的程序拥有了函数式的外观和命令式的效率(例如《SICP》中举的例子,用惰性计算结合map、filter和reduce)。拥有惰性计算有利无害,何乐而不为呢~或许也正是因为自己对特性的需求是多多益善,所以才喜欢Common Lisp吧。

涂色笔试题的动态规划解法

链子涂色问题的动态规划解法

话说大四已经开始了一个半月了,自己自从开学以来也一直在找工作,相继投了很多家IT公司。可悲的是,笔试过后就完全没有回音了——参加了多益网络的笔试两天后倒是有回音,只是收到的是拒绝的邮件QAQ。说实话,现在对于自己能不能够顺利地找到工作还是很担忧的,所以最近开始了紧张的复习。不过自己实在是懒,所以也没有像别人考研那么地拼命,只是在刷完微博读完邮件逛完豆瓣后开始看一些讲数据结构和算法的书罢了。至于是否真的有效,我也不清楚,毕竟笔试题目也不一定就完全考察这些内容的。不过按照目前的几次经验来讲,考察数据结构和算法的擦边球也有不少,可以说也是为了日后的面试准备一下吧,如果有面试的话……QAQ。

问题来源与描述

前面跑题还真严重,算是个人风格吧……话说室友去了一家名为CVT的公司参加笔试和面试,尽管最后第二轮被刷了,不过可以说还是挺厉害的。他在参加了笔试之后回来和我说了一道题目,大意是“给一串红绿珠子并存的链子,要求通过涂色把红色的珠子全部放到绿色的珠子的左边去,要求涂色的次数尽可能地少”。刚开始的时候没有认真听,于是就觉得这是编辑距离的变体罢了,那天晚上就把这个思路脱口而出,结果他第二天去面试面试官又拿这道题问他有没有新思路,结果估计被我害得够呛吧,惭愧。

题目其实有蹊跷,因为编辑距离是有前提的,那就是做变换的过程中要可以使用插入和删除操作,而那道题只允许涂色,那么也就是编辑距离中的替换操作罢了。还有另外一个和编辑距离不同的地方,那就是最终的变换目标不是唯一的,因为完全可以把链子里的珠子全部涂成一个颜色,那样就不会有红色在绿色的右边的情形了。所以,这道题目不是编辑距离的变体。唉,都怪自己太骄傲了,没有读懂题目。

动态规划的解法

前天上计算智能的课的时候,因为室友(去笔试的那位)想到了正确的线性时间的解法,所以我也不甘落后,开始在课堂上捣鼓起这道题目来。我的预感是,一般笔试题应该都可以用动态规划来做的,于是就从动态规划的角度来思考,结果也确实想到了一个办法。尽管不知道网上是不是已经有这道题的解法了,不过还是拿出来分享一下吧。

既然要使用动态规划,那么当然要按部就班地来思考。首先,就是要描述最优解的结构,也就是要找出问题解的最优子结构。为了便于描述,先约定一些记法。对于珠子和链子这种东西,可以把它们适当地抽象为元素和数组,用R代表红色而用G代表绿色,同时用S表示整个数组。数组的长度记为S.len,数组的第n个元素记为S[n],而把最后一个元素拿掉之后的数组记为S[1..(S.len-1)](类似于Python中的数组slice的写法)。对具体的数组实施变换,即涂色操作的功能就命名为F,它是一个二元函数,第一个参数是数组,第二个参数是位于数组之后的元素。为什么要这样子定义,而不是定义为一元函数呢?

不一样的最优子结构

对于数组的最后一个元素S[S.len],它只有两种可能:

  • S[S.len]为R;
  • S[S.len]为G。

并且如果本来是红色R的,那么可以涂成绿色G的;本来是绿色G的,可以涂成红色R。可是对于一个珠子,是不是真的可以随意地对它涂色的呢?显然不是的。例如,如果已经确定了整个数组S的下一个元素是红色R的,那么S[S.len]就无论如何也不能涂成绿色,因为这样一来就绝对无法得到红色全在绿色右边的链子了。所以,如果操作F是最优的,即F对于一个数组S以及给定的下一个元素a,它的涂色次数最少,那么:

  • 如果a为R,那么F肯定是把前缀S[1..(S.len-1)]也给全部涂成了红色;
  • 如果a为G,那么F对于数组S的前缀S[1..(S.len-1)]的涂色次数肯定也是最少的。

上述的第二条,正是解的最优子结构。

递归定义最优解的值

显然,最优解的值也就是最优解的衡量标准,即需要对原来的数组进行的涂色的次数。既然要递归定义,那么就要考虑递归的一般情形(也就是需要递归的情形)以及基准的情形。对于下一个元素a为红色的情况,只能继续选择把目前处理的数组的最后一个元素也涂成红色,因此如果原来的数组最后一个元素S[S.len]不是红色,那么就需要一次涂色操作,如果是那么就不需要;对于下一个元素为绿色的情况,需要分别考虑要不要涂改最后一个元素的问题。如果涂,那么就增加一次操作,不涂就不需要。在a为绿色的两个分支中,涂成(或者保留)红色末尾元素的情形,和a为红色的情况的递归是一样,因此这里确实存在重叠子问题——动态规划的另一个要求。至于基准情况,则是当数组只有两个元素时的情况。此时,只能是GG、GR、RG、GG这四种,除了GR需要进行一次涂色之外,其它的均不需要涂色。

用数学公式来表示递归的情形可能更清楚:

其中diff函数判断两个参数是否相等。如果相等,那么就返回0,否则返回1。也就是在从第一个参数变换到第二个参数时所需要的涂色次数。

按自底向上的方式计算最优解的值

在思考如何自底向上的时候,我采用的办法是先自顶向下地演示一遍。如下图所示,其中入口功能的名字为G,例子所使用的数组为RGRG:

显然这里需要构造一个表格来对F过程的中间结果进行存储,因为F是一个二元的函数。尽管F的第一个参数是一个数组,可是原来的数组是不会变的,所以只需要记住当前处理的数组是由原来的数组的前多少个元素组成的前缀即可,因此F的第一个参数可以用数字来代替。因此,在处理过程中需要的是这样的一张表:

(不好意思,图中的空格没有对齐>_<)

那么如何自底向上呢?首先对于参数为1而下一个元素为R的情况,因为是递归函数的基准情况,所以可以直接得到F(1, R)=F([R], R)为0,于是填入0;同样第二行的第一个空格的值也为0。当需要填写第一行的第二个空格的时候,可以知道因为下一个元素为R,所以此处的值只与之前的末尾元素亦为红色R的情形有关,所以这个值只与第一行的前一个值有关,并且此时的元素S[2]为G与R不同,因此需要变换,故增加一;而第二行的第二个空格的值取决于前一列的两个格子的值。此时即计算G([RGG])的值,所以取F([RG], G)和F([RG], R)+1的较小值,即1。其它空格以此类推,最终结果为:

由计算出的结果构造一个最优解

显然,最后一列的结果就是所要的值,例如上面的数组[RGRG]的最少涂色次数是1,并且操作是将第二个位置上的G涂成R。这样的操作反映在中间结果中,就是先找出最后一列的元素的值最小的那一行,例如上面就是第二行。然后就是在所有的列中找出所有与下一列的值不一样的列,将其对应的珠子的颜色翻转。例如在上面的表格中,就是将第二列的G涂成R,因为G对应的数字0不同于下一列的数字1。好吧,这一次,我就不给代码了,因为我还没有写出来;)

三个角度思考问题的不同结果

问题一:50个瓶子的故事

一个青年走进了一家便利店买了,爽快地购买了50瓶饮料,并且跟老板扬言说他可以一口气全部喝完。老板听了笑了觉得起来,因为这实在是太不可思议了,并且跟青年保证可以用三个空的瓶子换得一瓶新的饮料继续喝。青年微微一笑,随手拿起了一瓶并且一口气喝下了第一瓶,然后用神情的眼眸望向老板,问到:“呵呵,老板,你猜一下,我最后总共可以喝到多少瓶饮料呢?”而此刻的你,就是那个双眼中充满了疑惑的老板……

threebodies:三种思考方式

思路一:一遍又一遍地计算!

老板想,这个年轻人可能会采用这样的策略来喝饮料:首先把50瓶饮料全部喝掉,这样就可以得到50个空瓶子,然后用50个空瓶子来和自己进行交换,可以换得16瓶新的饮料,并且还剩下了2个原有的空瓶。接下来再把16瓶新装的饮料喝完,这样就得到了18个空瓶子,那么就可以继续和自己进行交换了。然后可以用全部的18个瓶子换得6瓶新饮料,并且再喝掉。再用6个空瓶子换得2瓶饮料继续喝掉,那么就会剩下2个空瓶,也就没办法再继续换下去了,所以最后的结果应该是74瓶!

在α世界线中的你,也就是老板就是这样子想的,他得出的结果是74瓶。可惜的是,青年技高一筹,他向你伸出手说:“老板,可以不可以借一瓶给我,这样我喝完之后就有3个空瓶了,还给了就相当于一瓶新的饮料,你也不亏啊。”你想了想,觉得倒也合情合理,于是答应了。所以最终的结果是,青年一共喝了75瓶饮料。

思路二:找出递推公式!

老板是个函数式语言程序员,他发现了要计算这样的过程的结果,可以利用递归!他假设了有一个函数叫做F,这个函数接受一个正整数作为参数,并且可以计算出这个正整数所对应的总共可以额外获得的饮料的数量。如果用50作为参数,那么就是在计算这个青年所提出的问题了。那么怎么递归呢?从一个特殊的情况考虑就是50瓶拿出3瓶来喝掉,并且换得一瓶新饮料,那么也就是说现在得到了一瓶新饮料,并且还剩下48瓶,所以关系应该是:F(50)=1+F(48),以此类推,F(48)=1+F(46),F(46)=1+F(44)等等。那么递推公式就是

F(n)=1+F(n-2)。

而最终的基础情形是n为1(当一开始的n为奇数时)或者n为2(当一开始的n为偶数时),它们对应的值分别为0和1(因为对于下降到n为2的情况,可以和老板借一瓶来凑数),所以如果一开始的参数为50,那么最后的计算结果将是F(50)=24+F(2),即25。那么将可以额外获得的25瓶加上原来的50瓶,青年总共可以喝到75瓶饮料。这一次,β世界线中的你终于得到了正确的答案。

思路三:列方程!

老板是个数学家,他首先意识到了青年可能会向自己借饮料,于是他开始列方程了:假设青年向自己借了x瓶饮料,那么他必须在喝完所有的饮料之后偿还这x瓶,为了能够正好喝完所有饮料而又不需要多还空瓶或者多买几瓶,那么他所借的饮料的数量应该满足这个方程

50+x=3x。

解方程,得到结果为75。在γ世界线中,老板几乎在听到了青年的问题后的瞬间回答了这个问题,青年先是吃了一惊,然后发出了爽朗的笑声……

问题二:圆与弦的故事

很久之前在学校里面的一家书店里面买了一本书,连我自己也觉得不可思议的是,这本书既不是轻小说也不是计算机类的书,它的名字叫做《悖论简史》,副标题还很唬人,叫做“哲学和心灵的迷宫”。这本书里面提到了很多有趣的故事,其中一个是由约瑟夫·路易斯·伯特兰在1889年提出的一个问题:在一个圆内任意拉一条弦,这条弦的长度比圆的内接等边三角形的边长还要长的概率是多少?这个问题在维基百科上也有收录,叫伯特兰悖论)。

至于这个问题的三种解答方法,我就不一一赘述了,反正我也不觉得自己能够把故事再用青年人和老板来重演一遍,各位读者就自己看维基百科上面的说明好了。不过我觉得这个题目很有意思,非常的有意思。首先它和问题一一样,可以从三个不同的角度来进行解答,问题在于,问题一的三个答案在同样的前提下是一样的(即允许青年向老板借一瓶饮料,而实际上即使不能借,前两个思路算出来的结果也是正确的),可是对于伯特兰悖论而言,三种方法算出来的结果截然不同!不过现实和数学毕竟是不一样的,答案终究只有一个,这个是用实践就可以证明的。

后记

从不同的角度看待不同的问题,除了会得到不同的解法之外,不同的解法甚至还可能得出不同的答案,但是这样的答案尽管互相之间是矛盾的,却无法从推理过程中看出问题,不得不承认,数学有时候真的是一种很神奇的东西,尽管不少时候我都会觉得,数学就是符号和规则的游戏,只是碰巧现实世界的模型和数学所使用的模型一致罢了。算了,我对数学的理解也不深刻,就不继续民科下去了。总之,以后多尝试从不同的角度看问题,或许真的会有不同的收获。啊,怎么感觉这文章虎头蛇尾的?!

ProjectEuler第18题

先跑跑题

自从辞掉了那份实习,我仿佛失去了什么东西,以致于在后来的两天里面都有一种无所事事的感觉,做什么事情都不在状态的样子。可能现在的我看起来还是那样子,不过我的自我感觉还可以,虽然看动画占了一天当中不少的时间份额,不过也总算是值得的。当然了,还有阅读小说的时间。最近买了不少小说(同时也不小心错手买了两本漫画),读了大部分,现在还剩下一本《奋斗吧!系统工程师》的第三卷没有打开来读。说到学习方面的话,最近确实是松懈了很多,丝毫没有按照自己在日程安排当中写的那样去做(回家没有网络也算一个原因吧),例如没有看《算法导论》,倒是看了不少和OCaml有关的内容,也掌握了不少OCaml的知识,感觉如果要实际使用的话,只要再努力学习一点库和领域特定的知识就足够了吧——大概是的……

入正题

ProjectEuler的第18题所需要的答案就是从三角形的最上层,到达三角形的最下层的路径中,哪一条路径上数字的和最大,计算出这个最大值就可以了。如果对动态规划的思想有点感觉的话,那么这个问题其实就是可以运用动态规划来解决的一个比较典型的例子了。按照《算法导论》一书中的描述,动态规划算法的设计可以分为下面的四个步骤:

  • 描述最优解的结构
  • 递归定义最优解的值
  • 按自底向上的方式计算最优解的值
  • 由计算出的结构构成一个最优解

要想描述这里的最优解的结构,不妨自己定义一些名词以方便描述。首先给三角形中的每个元素设定一个位置,它们各自的位置由行和列来决定,最上面是第一行,而最下面是最后一行,也就是第十五行。而最上面的那个元素,就是传说中的第一行第一列,给位置取个符号,叫做P(i,j)好了,其中i代表行号,j代表列号。给路径取名为p,那么如果找到了一条从位置P(i,j)到底层的路径p,它上面的数字的和是所有从P(i,j)出发的路径中最大的,那么称这条路径p为所谓的“最大和路径”。

描述最优解的结构

如果从位置P(i,j)开始的路径p是其对应的最大和路径,那么p必然包含了从位置P(i+1,j)或者P(i+1,j+1)开始的最大和路径。要证明这样的东西,可以用反证法(《算法导论》中都是这样的思路)。假设这条路径没有包含通过位置P(i+1,j)的最大和路径作为其一部分,那么就是说存在从位置P(i+1,j)开始到达底层的另一条路径p’,其上面的数字之和比p的对应的那一部分要大。如果真的是这样的话,那么只需要在原来的路径p中,将从位置P(i+1,j)开始的那一部分替换成这条新的路径p’,那么就可以构造出一条新的、从位置P(i,j)开始到达底层的最大和路径p2,并且p2包含的数字之和比p的要大。这与原来的假设,即p是最大和路径相矛盾,所以假设不成立,p包含了通过其上面每一个子位置的最大和路径。同理可以证明对于位置P(i+1,j+1)这样的关系也是成立的。

这就是最优解的结构,也就是最大和路径的构成是怎样的。一个问题的最优解包含了子问题的一个最优解,这就是所谓的最优子结构性质,是运用动态规划来设计算法的一个重要的要求。现在最优解的结构已经找出来了,可是这个东西似乎不是可以拿来计算的东西,毕竟它不是一个量化的东西,所以接下来就要……

递归定义最优解的值

那么应该用怎样的数量来作为可以代表最优解的值呢?其实PE的这个问题本身就提供了非常好的入手点,也就是从某个位置出发,到达底层的路径上的数字的和。因为要从最优解的方面来考虑,所以可以把这个代表最优解的值设定成“从位置P(i,j)开始的最大和路径p所经过的数字的和”。不过这个定义也只是解决了最优解的值从那个方面入手的问题而已,更重要的是,这个最优解的值可以通过怎样的方法计算得来呢?显然,最大和依赖于下面一层中和位置P(i,j)相邻的两个位置所能够得到的最大和,这两个位置分别是P(i+1,j)和P(i+1,j+1)。假设在一个位置中存储的数字为a(i,j),与一个位置相关的最大和记为S(i,j),那么对于一般的i和j而言,S(i,j)=max{S(i+1,j), S(i+1,j+1)}+a(i,j),其中要求j<=i。有两个临界情况,它们分别是当i等于1和15时的情况,一个是处于最上层,另一个则是处于最下层。对于i=1的情况,S(1,1)就是题目所需要的答案,而对于所有i=15的情况,S(15,j)=a(15,j)。(如果可以用LaTeX来排版公式的话表意一定会更加地明确)

按自底向上的方式计算最优解的值

现在的问题就是,要怎么自底向上地计算出这个最优解的值呢?其实很简单,只要从第14层开始一层一层地往上处理就可以了。假设有一个三角形S记录着对应于每一个位置的最大和,那么对于遇到的每一层中的每一个位置P(i,j),只需要在S(i+1,j)和S(i+1,j+1)中选择一个较大的值,然后与a(i,j)相加并且放入表S的对应位置中就可以了。这样当处理完了所有的元素后,也就是遍历到了第一层之后,表S的(1,1)位置就是最终的答案了。不过这里稍微有个可以优化的地方,就是在处理第i层的时候,每一个元素在处理完之后,原先存放的值就没有用处了,因此其实完全可以不需要再使用一个三角形S,而是直接将求和得到的阶段性的那个值放入P(i,j)中。这样下次计算上一层时也不需要三角形S了,而是直接使用下一层的数据就可以了。

由计算出的结构构成一个最优解

第三阶段的计算实际上已经完成了这里的工作,所以可以直接编码了。代码在这里,是用OCaml来写的。

CommonLisp函数调用的CPS变换

之前在新浪博客上已经发表了一篇同样主题的文章了,不过心血来潮想重写一份发到这边的博客上来,顺便看看自己能不能够在自己重写这篇的东西的过程中再发掘出一些有价值的东西,充实一下内容。

什么是CPS

首先双手奉上来自维基百科的Continuation-passing-style条目。CPS一般译作续延传递风格,这里最不好理解的词语莫过于续延了。维基百科上关于续延也有详细的介绍,不过我也可以简单地介绍一下。续延是一种表示接下来所要进行的计算的对象,也就是你在计算了这一步之后需要继续做的事情的一个描述。举个例子,对于Common Lisp代码(+ (+ 1 2) 3)而言,最左边的参数首先会被计算,也就是Lisp实现先计算的是(+ 1 2)这个表达式,于是可以得到返回值为3。那么计算完了最左边的参数之后,Lisp实现接下来要做什么呢?显然,接下来会计算作为直接值的3得到3本身,然后再将第一次计算得到的3和第二次求值得到的3进行相加。而上面的这两个步骤,其实可以用Lisp中的对象进行描述,只需要用一个匿名函数就可以了,写成

(lambda (v) (+ v 3))。

那么我们就可以思考,在这一个匿名函数被计算之后,再一次的接下来的计算又是什么呢?对于在REPL中输入的代码而言,Lisp实现会把表达式最终计算得到的返回值打印在终端上,所以我们可以认为上面的匿名函数,也就是一个计算过程,所对应的续延是

(lambda (u) (print u))。

那么原来的表达式(+ (+ 1 2) 3)就可以写成下面这样的风格的代码:

(+& 1 2 (lambda (v)
          (+& v 3 (lambda (u)
                    (print u)))))

你或许会感到奇怪:这里的+&是个什么东西啊?+&是一个和加法类似的函数,只是它除了会把前两个参数相加之外,还会将这个参数传递给作为第三个参数传入的匿名函数,并进行函数调用。按照维基百科上的说明,CPS代码有两个规范:

  1. 每一个函数都要接受一个续延作为额外的参数;
  2. 每一个函数调用中的参数都只能是一个变量或者λ表达式。

可以说,+&这样的函数是为了将代码变换成CPS才创造出来的。当然了,除了+函数需要进行变换之外,其它的普通函数(regular function)也是需要进行变换的。例如对代码(\ (+ 1 2) 3)进行变换的话,就需要为\函数提供相应的变体,结果应该是:

(+& 1 2 (lambda (v)
          (*& v 3 (lambda (u)
                    (print u)))))。

上面的代码中有个可以稍微琢磨的地方:为什么在两个不同的匿名函数的参数列表中偏偏要使用不同的参数名呢?事实上,在上面的两个变换出来的结果中,完全可以统一使用v或者u来作为参数名,那是因为参数v不需要在第二层嵌套的匿名函数中被使用。可是有时候一开始就进行求值的表达式不一定是马上就被使用的,例如代码(- (+ 1 2) (\ 3 4))*的变换结果就是

(+& 1 2 (lambda (v)
          (*& 3 4 (lambda (u)
                    (-& v u)))))。

可以说,当参数列表表达式中不止一个复杂表达式时,就需要至少两个不重名的参数了。讲了这么多手动变换的事情,现在可以讨论最重要的问题了:

如何对Lisp代码进行CPS变换

如果我们可以对一类简单的代码进行CPS变换了,那么如何在这个基础上对复杂的代码进行CPS变换呢?例如我们有一段简单的代码(op3 (op2 (op1 a b) c) d),并且我们已经有了一个通用的功能F可以对其中的嵌套的表达式(op2 (op1 a b) c)进行变换,那么要如何将其和外层的对op3函数的调用结合在一起呢?显然,我们可以先把(op2 (op1 a b) c)换掉,换成一个普通的符号v,以表示一个变量。那么接下来我们的处理对象就是一个稍微简单的表达式(op3 v c)了,对于这种参数列表均由变量所构成的表达式,要将其变换成CPS代码只需要修改其函数为加&的形式,并且添上一个额外的参数——续延就可以了。至于这个续延应该是由调用者提供,而又可以使用默认的(lambda (XXX) (print XXX))的。所以,上面的代码最终会变成

(经过F处理的代码 (lambda (v)
                (op3& v c (lambda (XXX)
                            (print XXX)))))。

对内层的表达式应用F处理完之后还要再计算外层表达式的续延,而计算续延正是函数F所做的事情,所以实际上对一个复杂的表达式做CPS变换,是一个递归的过程。用两段代码进行变换可以有更直观的体验:假设我们有一个正确实现的变换函数F,它接受一个代码和一个续延,并产生出对代码进行CPS变换所得到的结果。那么如果应用在代码(+ (+ 1 1) 3)上,就是

(F (+ (+ 1 1) 3) (lambda (v) (print v)))。

显然,这段代码应该和下面的这段代码是等价的:

(F (+ 1 1) (lambda (u)
             (+& u 3 (lambda (v)
                       (print v)))))。

并且上面这段代码的续延参数部分,和下面的这段代码是等价的:

(F (+ u 3) (lambda (v) (print v)))。

是不是就是说,对于一个复杂的表达式expr0,如果想要在提供一个额外续延cont0的情况下,将其正确变换成CPS形式,那么可以先提取出它的第一个被求值的子表达式expr1,将原来子表达式出现的地方替换为一个变量,那么原本的表达式就变成了expr1对应的续延cont1。此时先将cont1和cont0传入函数F进行CPS变换,得到的结果cont将会成为和expr1一起传入函数F进行变换,并最终得到对expr0和cont0进行变换的正确结果呢?显然这是对的,因为cont0紧随expr0求值,而expr0可以拆分为两部分:expr1以及紧随其求值的cont1。那么显然cont0紧随cont1求值,所以cont0是cont1的续延,同样需要进行CPS变换,然后得到新的代码作为expr1的续延继续进行变换,那么最终就会得到代码,它反映的求值顺序正是expr1 -> cont1 -> expr0。

那么重点就在于怎么把原本的expr0给拆分成expr1和cont1,以及具体结合代码和续延的技术细节了。假设实现拆分功能的函数叫做split-funcall,那么它需要在什么情况下做什么事情呢?一般而言,split-funcall处理的是有复杂的子表达式的代码,那么它需要能够在整个表达式expr0中找出尽量左的一个复杂子表达式,也就是expr1。如果找到这样的expr1了,那么就需要同时找出对应的续延cont1并将两者都返回;如果没有这样的expr1,那么直接返回逻辑假和整个expr0就可以了。说到需要返回多个值的情况,正是Common Lisp的values函数派上大用场的时候了。

对于含有复杂子表达式的情况,split-funcall函数会返回提取到的子表达式和对应的续延,那么这里的续延应该用什么样的形式来表示呢?为了方便使用从split-funcall内部所gensym出来的符号,所以直接返回一个经过构造的lambda表达式就可以了,但是在递归调用函数F时,不能直接对其进行变换处理,因为lambda表达式不是一个会对参数求值的操作符,所以真正需要变换的是lambda表达式的函数体。因此必须先拆开lambda表达式,对其函数体进行变换并再次构造成lambda表达式,以传递给函数F使用。

最后,贴一下自己放在Gist上的代码:

连分数与ProjectEuler的第66题

可耻的蛮力法

ProjectEuler的第66题的传送门。话说今天挺累的,去实习单位那边做了一下小小的阶段性总结,然后走回了学校的另一个门,吃完饭又走回学校另一头的我自己的宿舍,别提有多累了。看来今天这样的运动量也够了,今晚的跑步就先搁置了吧。好了,回到正题,也就是ProjectEuler的第66题。第66题乍看起来似乎很简单,无非就是查找一个满足条件的所有x当中的最大值而已。于是像几乎所有的其它题目一样,我尝试使用蛮力法来解决这个题目,而为了保险起见,我为自己的查找单个d所对应的最小的x的函数的查找过程设置了上界,因此保证了每一个函数调用都会结束。然后就开始对所有小于1000的d进行查找了,一开始判断一个数是不是平方数的方法有误,计算出了结果却是错的。待我修改了之后重新运行了一次程序,结果更令我大吃一惊——对于d为61的情况,在上限之下找不到结果——尼玛我设的上界可是一亿啊!(最近对一亿特别有感情)

抛弃蛮力法重新上路

再试了几次之后,我确定自己的方法是没有错的,所以真正的答案就是对于有些d而言结果确实无法在上界之下找到(最后计算到了真正的答案之后我才发现自己用蛮力法是多么的天真无邪可爱不懂事……)。于是我放弃了自己的方法,转而在网上寻找别人的求助。在Google中输入关键字后,很快就有英文的博客出现在了候选项中。为了不放过任何的学习机会,我点击了第一个。进去之后才发现,这个问题原来还真不简单……

数学的逆袭

ProjectEuler的第66题是一道不折不扣的数学题。在第一个博客中,我看到了博主提到了丢番图方程以及两个我不太懂的单词convergent和continue fraction。这时候还没啥感觉,只是对博主说他以0.x级别的速度做出来这道题目感到震惊和难以置信,然后又转而去看了Google到的第二个链接。说实在的,真的非常感谢这个链接的博主,因为正是他的指引才让我知道了一个关于连分数的极好的讲解,看完了博主的文章后大致知道了这道题目是怎么一回事,然后就一头扎进了那个讲解里面去看了。好吧,为了做题我又回去研究数学了。

大致的数学内容

首先题目中出现的方程是所谓的“丢番图方程”,并且可以归为更具体的类别叫做“佩尔方程”,幸运的是,对于佩尔方程的解是一个已经研究过的问题,并且根据维基百科上的说明,当d不为平方数时,佩尔方程对每一个d都有解,这是由拉格朗日证明了的。所以即使是使用蛮力法,也尽可以放心地去从1开始遍历所有的自然数——你总会找到那个心仪的它的!除了证明了有解之外,佩尔方程的解法也是被人们研究过的,并且有几种不同的解法。可惜的是本人的英语水平和数学水平都不是很强,只能看懂中文维基百科中关于佩尔方程的用连分数求解方法,因此也决定了使用这个方法来解决第66题。

重点来了:怎么计算一个数的算术平方根的连分数形式?

方法来源在前面提及的关于连分数的极好的讲解那里,不过重点其实在于用程序实现这个东西。一开始的时候我觉得这个东西可能要用到符号计算,然后就开始在那里纠结要用怎样的方式来表达一个数的算术平方根才好。到后来我盯了那个表格很久之后我才发现我错了,根本不是酱紫的!压根就不需要什么符号计算,只是纯粹的数值计算就足够了。这一切的一切的关键,就在于怎么把一个数拆分成一个整数加上一个未知数的倒数的形式。

(为了方便起见用了原文中的例子)首先,如果要计算√14,那么按照算法(请自己看上面的链接里的英文原文)的第一步,要找到一个数m,使得m的平方是一个最接近14的完全平方数。显然这个数是9,但是怎么算呢?可以一个个地从1开始找(太慢了一边去!),另一个方法是用计算器求平方根的功能直接计算得到3.7416575,然后对这个结果取不大于它的最大整数(也就是所谓的floor),得到了3。那么就可以把√14表示成3+1/x1的形式。

这样我们得到了√14的一个等级的连分数近似形式3/1(也就是3啊)。显然3*3-14*1*1得到-5,所以连分数3/1不是所希望的解,因此需要继续计算第二级的连分数近似,那么要怎么算呢?我们只要把上式中的x1也表示成连分数的形式就可以了,但是必须先求出x1的某个数值表示形式,不然无法应用上面的第一步。方法是把x1用√14和其它数来表示。于是有

x1 = 1/(√14-3) = (√14+3)/(√14-3)(√14+3) = (√14+3)/5

按照前面的方法,floor((√14+3)/5)的结果为1,所以x1可以写成1+1/x2的形式,那么√14就可以写成3+1/(1+1/x2)的形式,忽略未知的1/x2就得到了连分数4/1,仍然不是方程x^2-Dy^2=1的解。总之继续这么进行下去,就可以得到满足上面的方程的整数解了,并且其中的x必定是所有解当中最小的一个。

规律在哪?紧盯表格!

表格的第一列是Finding,显然,每一行的Finding的值决定了在Step 1中计算得到的红色的数字是多少。如果知道了每一行的Finding是多少,就有办法计算出那些红色的数字了。在Finding中出现的x1、x2和x3,其实就是前一行最后所计算出来的那些值罢了。不难发现x1、x2和x3其实都有相同的结构,那就是它们都是(√14-a)/b的形式。而a和b分别为3、2、2和5、2、5。如果再想想就会知道,其实一开始的√14也满足这样的形式。对于√14而言,a为0而b为1。既然有了规律和相应的符号表示,那么就可以从代数的角度来找规律了。加入要计算算术平方根的数是n,红色的要计算的数为m,那么在第i次计算中

(√n+a_(i-1))/b_(i-1) = m_i + 1/x_i

显然要计算的就是m_i和x_i,而x_i其实就是由a_i和b_i所构成的,因此变换x_i就可以得到

x_i = (√n-(a_(i-1) - m_ib_(i-1)))/((n-(a_(i-1) - m_ib_(i-1))^2)/b_(i-1))

上面的公式太丑了,LaTeX版本在这里。这样也就知道了对应于这个xi的a和b分别为多少了,参见前面给出的LaTeX所描述的公式的图片的链接。这些公式实际上是递推公式,也就是说你必须有了前一个值之后才能计算出下一个值。如果是希望快速计算出指定的连分数的一个部分的话,那么这种方式不适合,不过用在这里却刚好,因为我不知道第几个连分数的部分才是解,所以一定是从第一个近似连分数一直迭代过去的。

知道了计算方法,那么剩下的编码过程也就简单了很多了,详情请参见我的解法

后记

这一次的收获还真不少。首先是关于题目本身的。以前我做ProjectEuler的题目,几乎都是直接使用蛮力法来解决的,不过这一次蛮力法彻底失败了,因为消耗的时间实在是太久了所以没有必要完全计算出来了(实际上我没有完全计算,因为设置了上限在中途就发现问题了)。而上网搜索才发现这其实是一道彻头彻尾的数学题——当然了,还是需要写程序来算的。也强烈地让我认识到了,PE的题目看中的,真的如之前在豆瓣上的讨论所看到的,注重的是数学能力,而不是运用一些经典的算法的能力。第二个,是关于所谓的“过早优化是万恶之源”的说法的感想。

一开始我并不知道用蛮力法来计算是不实际的,因此我一直在尝试着改进蛮力法的性能——是的,我还没有确定这个东西是否能够正确地计算出结果的时候我已经开始考虑优化的事情了。问题出在哪里呢?就在于我对于所遇到的很多题目都是尝试使用蛮力法来解决的,以致于我有了这样的思维定势:每当我发现运行时间过长时,我就会觉得一定是我的代码性能不好,因此会尝试对其进行优化,例如加上类型声明或者使用记忆化之类的。可是偏偏这样走上了歪路,因为正确的做法是分析一下问题,找到正确的解法,而不是在错误的解法上不断地尝试优化。如果我一直优化下去,那么永远不会得到正确的答案——过早优化是万恶之源~

第三条——糟糕,洗完澡忘记了第三条是什么了!>_<(总算想起来了,于23:36)在这一次的解法中,对于连分数的构造是一个递推的过程,实际上就有种可以用递归来解决的味道。刚想着怎么表示这么一个构造连分数的过程的时候,我忽然灵光一闪,想到了只看过却从来没有使用过的技术——把闭包当作数据结构来使用。于是根据自己看《SICP》的经验,我弄了个叫做make-cf的函数,只要传递一个整数给它,那么就可以得到相应的一个闭包,对这个闭包做不同的操作就有不同的结果,而且那些状态信息还可以由闭包自己保持。等我用起来之后才发现,用闭包好像是一个很有用的想法,因为

这样子相当具有复用的可能!

代码中的make-cf、update-cf、to-cf和get-cf-list,完全可以写入一个package中然后作为一个独立的模块来提供,这样子以后的一些程序也可以使用了——PE上好像还有不少用到连分数的题目呢^_^虽然用CLOS完全可以实现这里提及的闭包的功能,可是比起CLOS提供的面向对象功能,闭包反而更有封装的感觉。总之在CLOS和闭包中,我更喜欢这种用闭包来实现的风格;-)

PE的第26题

今天上百度贴吧的ProjectEuler吧时发现大家在讨论第26题的一个解法的原理[求值]求解释原理,然后话题很快又从对解法的原理的解释转移到了对性能的攀比之中——这也是人之常情啦,哪个做PE题目的人不希望自己的方法是尽量快的呢^_^看了一下吧主的解法的运行时间,发现居然不是毫秒级别的,顿时对自己以前的解法需要运行多久心生好奇,于是在已经打开的SLIME中加载了以前的源文件,一运行,发现相当地快,速度上是吧主给出解法的快一百倍,连我自己都吓了一跳,不过还是掩盖不了自己内心的欢喜。

我的思路

我不知道吧主是怎么做的,他在贴吧里面没有给出代码,不过我倒是可以给一下我的解法的链接第26题。刚翻出来看的时候我自己也看蒙了,完全不知道自己当初究竟是怎样的思路的,也不知道自己当初是在怎样的情况下想出这样的代码的。不过再仔细看了一会儿之后,总算有点明白是什么意思了。这其中的做法,还得从小学的时候学习除法来说起……

哦,不好意思,说太远了,没必要追溯到小学那里去,不过思路本身可能确实就是小学的除法,只不过是找了一下其中的规律,然后用计算机代替了手动计算而已。考虑一个简单的情况,例如一除以二,要怎么计算呢?嗯,因为1比2要小,所以计算结果应该是个小数,所以商必然有0.(零以及小数点),然后在1后面添一个0,再继续计算。这时候我们知道了2×5=10,所以在商的部分再添上一个5,就得到了余数为0的情况。因为余数为0,所以我们知道2是可以整除1的,所以计算就到此结束了,因此1/2=0.5。

上面的例子是可以整除的情况,因此在小数点后面并没有循环的部分,所以循环部分的长度理所当然的就是0。那如果是一除以六呢?计算方法是一样的,因为1比6小,所以商添上0.,而给1添上一个0得到10,而10除以6的商为1余数为4。接下来给4添上一个0得到40,再进行40除以6的计算过程。最后得到的结果是一个无限循环小数,按照第26题的写法就是0.1(6)。不过且慢,这里有个地方值得注意,那就是对于得到余数为4的情况,我们为其添上了一个0再继续进行计算,这个步骤和一开始为1添上0再进行计算难道有什么本质的差别吗?

显然没有啊!而且计算40除以6的结果是6.(6),如果直接把这个计算1除以6时的第一步得到的商进行拼接,就得到了0.1(6)啊。也就是说,小学的时候学到的手动进行除法计算的方法,实际上可以分解成一个递归的算法。具体如何分解不是这里的讨论重点,这里的重点在于怎样从递归的过程中发现可以得到循环部分的长度的方法。

余数的奥秘

如果在手动计算的过程中,遇到了某个曾经在余数的位置上出现过的数,那么还有必要继续计算下去吗?显然没有,40除以6得到的第一个余数是4,而这个余数比6小(事实上我们都知道,所有的余数都比除数要小),就需要先将其乘上10再继续计算下去。结果显而易见,一乘上10,就又得到了一开始的40了,这样的话要是继续计算下去,那么结果一定是在重复前面的那些动作,并且永无休止。结论就是,当你遇到了一个余数是之前出现的数的时候,计算就不需要继续下去了,此时根据历史积累的信息,就可以知道循环部分的长度是多少。这也就是我的代码中第一个函数cycle-length的内部辅助函数rec的作用。

rec接收三个参数,第一个参数就是被除数,第二个数是除数,第三个数是这一次计算得到的商在原来的小数部分上是位于哪一个位置上的一个整数。对于每一个出现过的被除数,都将它们记录在了一个内部的哈希表中(为了查找速度的尽可能快),如果一个被除数已经被计算过了,那么就直接取出它所对应的商所在的位置,然后用现在的商所在的位置减掉前者,就知道了循环部分的长度了;如果没有出现过,那么就计算出这一次计算的余数,如果余数为0,意味着除数可以整除被除数,所以没有循环部分可言,长度为0;如果不能整除,那么这个余数的10倍就是新的被除数(因为余数必定小于除数,所以要乘以10直到大于除数为止),位置计数器加上1,重新进行递归。