hello erlang, part 1

练习重点

  1. erlang是单赋值的,就好像都经过java里边的final修饰过
  2. erlang没有内置的循环结构,这个和大多数语言是不一样的
  3. erlang是函数式语言,需要理解模式匹配编程方式
  4. erlang经常会遇到递归, 并且支持尾递归函数调用

练习1:数据库demo

作为学习erlang里边的模式匹配,熟悉语法。 编写一个数据库模块db.erl,它能够存储、检索、删除元素。我们需要实现的接口有:

db:new()                   %% Db.
db:destroy(Db)             %% ok.
db:write(Key, Element, Db) %% NewDb.
db:delete(Key, Db)         %% NewDb.
db:read(Key, Db)           %% {ok, Element} | {error, instance}.
db:match(Element, Db)      %% [Key1, ..., KeyN].

实现代码

-module(db).

%% Exported Functions
-export([new/0, write/3, read/2, match/2, delete/2, destroy/1]).

%% API Functions
new() -> [].
destroy(_) -> ok.
write(Key, Element, DB) -> [{Key,Element}|DB].
delete(Key, DB) -> delete_local(Key, DB, []).
read(Key, DB) ->
	case DB of
		[{Key, Element}|_] -> {oKey, Element};
		[_|ODB] -> read(Key, ODB);
	    _ -> {error, instance}
	end.
match(Element, DB) -> match_local(Element, DB, []).

%% Local Functions
match_local(Element, DB, LIST) ->
	case DB of
		[{Key, Element}|ODB] -> match_local(Element, ODB, [Key|LIST]);
		[_|ODB] -> match_local(Element, ODB, LIST);
	    _ -> LIST
	end.

delete_local(Key, DB, NDB) ->
	case DB of
		[{Key, _}|ODB] -> delete_local(Key, ODB, NDB);
		[H|ODB] -> delete_local(Key, ODB, [H|NDB]);
	    _ -> NDB
	end.

当然,case语句同样可以用如下代码替代:其中第三行的Key因为没有使用就换成_, 不然会提示警告variable ‘Key’ is unused。

delete_local(Key, [{key, _}|ODB], NDB) -> delete_local(Key, ODB, NDB);
delete_local(Key, [H|ODB], NDB) -> delete_local(Key, ODB, [H|NDB]);
delete_local(_, _, NDB) -> NDB;

练习2:排序算法

下面练习一下快速排序和归并排序,再熟悉一下模式匹配和递归的写法。

-module(sort).
-export([quicksort/1, mergesort/1]).

%% 快速排序
quicksort([H|Tail]) ->
	lists:append([quicksort(lists:filter(fun(X) -> X < H end, Tail)), 
				  [H], 
				  quicksort(lists:filter(fun(X) -> X >= H end, Tail))]);
quicksort(L) -> L.

%% 归并排序
mergesort(A) ->
	case length(A) of
		0 -> [];
		1 -> A;
		LEN -> M = length(A) div 2,
			   merge(mergesort(lists:sublist(A, 1, M)), 
					 mergesort(lists:sublist(A, M + 1, LEN - M)), [])
	end.
merge(A, [], L) -> lists:append([L, A]);
merge([], B, L) -> lists:append([L, B]);
merge([HA|TA], [HB|TB], L) -> 
	if
		HA > HB -> merge([HA|TA], TB, lists:append([L, [HB]]));
		true -> merge(TA, [HB|TB], lists:append([L, [HA]]))
	end.

马踏棋盘的算法思考

马踏棋盘

将马随机放在国际象棋的8×8棋盘的某个方格中,马按走棋规则进行移动。 要求每个方格只进入一次,走遍棋盘上全部64个方格。

又是回溯?

这个做法和前面几个问题是差不多的(数独(sudoku)游戏),所以这里就不做太多解释了。 总体来说,就是可选的解空间是8个方向。回溯的代码就不多提了,需要说的是,这里简单的回溯 效率不好,需要跑很久才出结果。我们有什么方式可以优化一下!

贪心是否有效?

首先,我们可以对可供选择的方向进行过滤,对于它相连的8个方向所在的点, 在当前的局面下,假如存在两个点只有一条路可以到达,那么可以直接回溯, 因为无论走哪个方向都不能走完整个棋盘。假如存在一个点,它只有一条路可以到达, 那么下一步必须走这个方向。

但是,即使我们过滤了一些路径,效率还是没有非常大的提升。我们需要考虑一种贪心的思路: 在可选的方向中,优先选择出口最少的目标点。因为优先选择出口少的点, 就可以让出口少的点尽量少,使得最后剩下的点有比较多的入口,这样最终达到目的的概率就会大些。

虽然这个思路,我觉得不好直接证明,不过我修改了一些代码实现,的确效率得到非常大的提升。 就我那个机器,ruby代码,不到1s,64个点的情况就全部处理完了。

代码示例

def init
  @arr = Array.new(8)
  (0..7).each do |i| @arr[i] = Array.new(8, 0) end
  @path = Array.new(64) 
  @ok = false
  @poss = [[-2, 1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, -1], [-1, -2], [1, -2]]
end
# 判断[x,y]是否在棋盘内并未走过
def valid?(x,y)
  x>=0 && x<8 && y>=0 && y<8 && @arr[x][y]==0
end

# 判断当前点有哪些方向可以走
def filter(mark)
  posz, mustpos = {}, nil
  a, b = @path[mark]
  @poss.each do |pos|
    axp, bxp = a+pos[0], b+pos[1]
    if valid?(axp, bxp)
      sz = 0
      @poss.each do |ps|
        ap, bp = axp+ps[0], bxp+ps[1]
        sz+=1 if valid?(ap, bp) # 存在空点
      end
      if sz>0
        posz[pos] = sz
      else
        mustpos.nil? ? (mustpos = pos) : (return [])
      end
    end
  end
  # 对目标点的方向多寡进行排序
  mustpos.nil? ? posz.keys.sort {|a,b| posz[a]<=>posz[b]} : [mustpos]
end

def walk(mark)
  if mark==63
    @ok = true
    return
  end
  a, b = @path[mark]
  filter(mark).each do |pos|
    rp = [a+pos[0], b+pos[1]]
    @path[mark+1] = rp
    @arr[rp[0]][rp[1]] = 1
    walk(mark+1)
    @ok ? return : (@arr[rp[0]][rp[1]] = 0)
  end
end

(0..7).each do |i|
  (0..7).each do |j|
    init
    @path[0] = [i,j]
    @arr[i][j] = 1
    walk(0)
    if @ok
      @path.each_with_index do |ps, idx|
        @arr[ps[0]][ps[1]] = idx
      end
      @arr.each do |ar| p ar end
      puts
    else
      "no solution"
    end
  end
end

数独(sudoku)游戏

数独游戏

在9×9格的大九宫格中有9个3×3格的小九宫格,并提供17个以上的数字。 根据这些数字,利用逻辑和推理,在其它的空格上填入1到9的数字。 每个数字在每个小九宫格内只能出现一次,每个数字在每行、每列也只能出现一次。

思路与数据结构

使用回溯法来不断尝试就可以了,可以用一个二维数组来arr[9][9]表示整个数独,其中还没有填上的用0表示。 我们还需要有个方法来判断能否在[i,j]这个格子上填入某个值。 同样还需要一个变量来表示是否已经找到解。另外,我使用了mark(0~80)作为每个格子的序号, 深度搜索的时候就从0开始处理,直到mark=80的时候出现一个解。

ruby代码示例

# 判断能否在[i,j]上填入val
def is_ok?(i,j,val)
  (0..8).each do |m|
    return false if @arr[i][m] == val && m!=j #判断行不重复
    return false if @arr[m][j] == val && m!=i #判断列不重复
  end
  (i-i%3..i-i%3+2).each do |m|
    (j-j%3..j-j%3+2).each do |n|
      return false if @arr[m][n] == val && i!=m && j!=n #判断小九宫格不重复
    end
  end
  true
end
# 用来输出数独
def print; (0..8).each { |m| p @arr[m] }; end

# 用来表示是否找到解
@ok = false
# 处理序号为mark开始的格子
def walk(mark)
  m, n = mark/9, mark%9
  val = @arr[m][n]
  # 当前已经有初始值的情况
  if val != 0 
    mark == 80 ? @ok = true : walk(mark+1)
    return
  end

  # 没有初始值的情况
  (1..9).each do |v|
    if is_ok?(m, n, v)
      @arr[m][n] = v
      @ok = true and return if mark==80 # 找到一个解
      walk(mark+1) #填好值之后,继续深度搜索
      return if @ok
    end
  end
  @arr[m][n]=0 # 都处理完,没有找到就恢复
end

walk(0)
@ok ? print : (p "no solution")

回溯法的基本步骤:

  1. a定义问题的解空间
  2. a确定易于搜索的解空间结构
  3. a以深度优先搜索的策略搜索解空间,并在搜索过程中用剪枝函数避免无效搜索

回溯法的基本结构

我们考虑递归的方式(比较容易理解),递推的以后再讨论。

# init
flag = false # 标记是否找到解
u = {} # 已知解, 并假设(x1,x2....xn)为可选的解空间

def backtrack(k)
  (x1..xn).each do |x|
    if is_ok?(x, k) # 过滤无效的解
      u.add(x) # 把x加入已知解u
      backtrack(k+1) if u.is_part? # 部分解的情况,继续处理
      flag = true and exit if u.is_full? # 找到解并退出
      # fail的时候有可能需要对u进行恢复
    end
  end
  # fail的时候有可能需要对u进行恢复
end

backtrack(1) # 从1开始搜索
flag ? p u : "no solution"

简单的楼梯问题

问题描述

有个楼梯,一个人一次可以走1级或2级,那么走上一条100级的楼梯,有多少种不同的走法?

找到规律

先找到规律,从简单情况开始,设f(n)是n级楼梯的走法数量。那么就有:

  1. n=1,肯定只有一种走法,即f(1)=1
  2. n=2,可以一级级走或者一次两级,即f(2)=2
  3. 对于n>2的情况,如果第一次走1级,剩下的楼梯有f(n-1)种走法,如果走2级,剩下的楼梯有f(n-2)种走法。 那么总的走法是f(n)=f(n-1)+f(n-2)。

斐波纳契数列

说白了,这是个斐波纳契数列。计算的时候简单的动态规划即可。下面是简单的ruby源码:

a,b=1,2
98.times {b,a=a+b,b}
p b #=> 573147844013817084101

看,真的是一个天文数字来的。

一笔画游戏

在android上看过一个一笔画的小游戏,规则很简单,要连续一笔,不能重复。 当然,到后面比较难的时候还会限制方向,有些线路必须走多次等等。并不是觉得这有游戏做得多么的好,或者很有创意。 我只是从程序员的角度来看问题,用程序是怎么处理的。 我们只需要尝试所有可能的路径就可以了,这里用了回朔法,是一种优化过的穷举,

先来考虑一下数据结构。我们给所有的点加上编号1-n,所有的连线可以用二维数组表示a[n+1][n+1],值为0表示不可联通, 其他表示需要经过的次数(我实现的时候是采用类似稀疏矩阵的链表表示)。
至于给矩阵增加多一列,主要是考虑处理方便,还考虑到起始点不好确定,所以加个虚拟点,
同时增加虚拟点到其他n个点的连接,这样我们深度遍历的时候从虚拟点开始就可以了。
另外我们需要一个链表来存放走过的路径,还需要一个标记来表示找到路径,无需继续尝试。

初始化的伪代码如下,

(0..n).each do |k| a[0][k]=1 end #虚拟点
@path = [] # 走过的路径
@ok=false # 标记是否完成

接下去我们需要一个回溯算法(参考数独(sudoku)游戏),代码比较简单,这里就不展示代码示例了。

需要注意的是,找到一个可走的路径时(例如从i到j,a[i][j]>0),深度遍历的时候需要对这个值减1,回溯的时候加1就可以了。 而对于走过的路径path,是否需要回退呢? 其实我们关心的是把刚刚走过的路径加入路径的正确位置, 如果选择数组的话,在回溯的时候就不可以不回退了,而对于链表,回退则是必要的。

总体来说,这个游戏的实现是比较简单的,有兴趣的同学可以自己实现一下。