用ocaml实现汉诺塔游戏

这是要交的算法作业

这东西真的是想了很久才想出这么一个算法。以前也尝试过不少,但是都以实现过于复杂而放弃。

(* 程序说明: *) 
(* 汉诺塔(移盘子)游戏,本程序绘图并求解了该问题。 *) 

(* 规则简介: *) 
(* 三个柱子,上面串着若干个大小各不相等的盘子。 *) 
(* 初始状态:所有的盘子都在最左侧的柱子上,从上往下按从小到大依次叠在一起。 *) 
(* 终止状态:所有的盘子都在最右侧的柱子上,从上往下按从小到大依次叠在一起。 *) 
(* 操作规则:一次只许移动一个盘子,将其从一个柱子移动到另一个柱子上。 *) 
(* 要求小盘子不能放在大盘子下面。 *) 

(* 算法分析: *) 
(* 由于这是一个典型的递归问题,所以我采用了ocaml语言编写。 *) 

(* 我的算法基于如下两个猜测: *) 
(* 1、最优解的解法是唯一的。 *) 
(* 2、当前步的决策只与当前步的状态有关,与上一步(及前几步)所执行的操作无关。 *) 

(* 后者使得我不需要使用数据结构来存储除当前盘子的位置状态以外的任何信息(很多的人 *) 
(* 在求解此问题的时候使用了栈),这使得程序编写得以更简便。 *) 

(* 算法的实现: *) 
(* 算法的核心问题在于如何根据当前的盘子的位置来决定该把哪个盘子移动到哪里。 *) 
(* 把盘子按从小到大编号为:1、2、3、4、5、6、... *) 
(* 三个柱子分别是A,B,C *) 
(* 初始状态下,所有的盘子都在A上,他们应该被移动到C上。 *) 

(* 设编号为x的盘子当前的实际位置是spos,在当前步应该被移动到pos,那么 *) 
(* 我的规则是: *) 
(* 1、最大的盘子,pos=C. *) 
(* 2、设x是一个盘子,它在当前步的实际位置是M。 *) 
(* 若x的实际位置是M,并且应该被移动到M,那么(x-1)应该被移动到M *) 
(* 否则,若x应该被移动到L,并且可以在当前步被移动到L,那么移动它到L。 *) 
(* 否则,(x-1)应该被移动到三根柱子的另外一根。(既非L也非M) *) 

(* 测试环境: *) 
(* 系统:FreeBSD 6.2-RELEASE #19,i386 *) 
(* 编译器/解释器: ocaml 3.09.3 *) 

(* POSIX下的sleep函数会因为收到信号而被信号处理函数打断,而 * 
ocaml的graphics库的实现是基于信号的刷新同步。所以 * 
Unix.sleep函数几乎就失效了。所以就自己模拟了一个Sleep *) 

let mysleep n = 
let start = Unix.gettimeofday() in 
let rec delay t = 
try 
ignore (Unix.select [] [] [] t) 
with Unix.Unix_error(Unix.EINTR, _, _) -> 
let now = Unix.gettimeofday() in 
let remaining = start +. n -. now in 
if remaining > 0.0 then delay remaining in 
delay n 

(* 画竖向的线 *) 
let printVLine pos= 
Graphics.moveto pos 0; 
Graphics.lineto pos (Graphics.size_y()) ;; 

let rec printPlate1 plateHeight plateWidth ypos plateList xpos= 
match plateList with 
[] -> (); 
| serialNumber::l -> 
begin 
(* print_int (List.length plateWidth); *) 
(* Printf.printf "在%d上绘制盘子%d,宽度为%d\n" xpos serialNumber 
(List.nth plateWidth (serialNumber-1) ); *) 

Graphics.fill_ellipse xpos ypos (List.nth (List.rev plateWidth) 
(serialNumber-1) ) plateHeight; 

printPlate1 plateHeight plateWidth (ypos+ plateHeight*2 -2) l 
xpos 
end;; 

let printPlate plateHeight plateWidth ypos plateList xpos= 
printPlate1 plateHeight plateWidth ypos (List.rev plateList) xpos 

let rec buildList l d len= 
if len = 1 then l else 
buildList (( (List.hd l) + d) :: l) d (len-1);; 

let plateWidthList gap len = 
let maxWidth = gap * 4 / 5 in 
let minWidth = gap / 5 in 
let d = (maxWidth - minWidth) / len in 
buildList (minWidth::[]) d len;; 


let rec sum = function 
| [] -> 0; 
| a::l -> a + sum l 

let totalNumberOfPlates plateData = sum (List.map List.length 
plateData);; 

let drawGraph plateData = 
assert(( totalNumberOfPlates plateData) == 7); 
let gap= Graphics.size_x() / 4 in 
let l= gap::2*gap::3*gap::[] in 
begin 
Graphics.clear_graph (); 
List.iter printVLine l; 
List.iter2 (printPlate 20 (plateWidthList gap (totalNumberOfPlates 
plateData) ) 20 ) plateData l; 
end;; 

(* 将数据复原 *) 
let rec orig data left mid right = 
match data with 
| l1::l2::l3::[] -> 
if(left > mid) 
then orig (l2::l1::l3::[]) mid left right 
else if (mid > right) 
then orig (l1::l3::l2::[]) left right mid 
else data; 
| _ -> data;; 

let rec searchPlatePos data x= 
if(List.mem x (List.hd data) ) then 1 
else 1 + (searchPlatePos (List.tl data) x);; 

let movable data x pos spos = 
try 
let l1 = List.nth data spos in 
if( (List.hd l1 == x) &&( (List.length (List.nth data pos) 
== 0) || (x < List.hd (List.nth data pos) ) ) ) then true 
else false; 
with Failure "hd"-> 
print_endline "fail at hd"; 
(* List.map print_int l1; *) 
false; 

| Failure "nth"-> 
print_endline "fail at nth"; 
false; 
;; 

(* pos就三个,除了x,y另外一个是?*) 
let otherPos x y = 
if((min x y) != 1) then 1 
else if((max x y) != 3) then 3 
else 2;; 

let comp x y= 
compare (snd x) (snd y);; 

(* pos是x应该在的位置。*) 
(* spos是x的实际位置 *) 

let moveData data pos spos = 
assert(( totalNumberOfPlates data) == 7); 
try 
let x::l1 = List.nth data spos in 
let l3 = List.nth data pos in 
let opos = (otherPos (pos+1) (spos+1)) -1 in 
let l2 = List.nth data opos in 
let result = fst (List.split (List.sort comp 
((l1,spos)::((x::l3),pos)::(l2,opos)::[]))) in 
(* Printf.printf "要移动的盘子的编号是%d,位置是%d->%d,%d\n" x spos pos opos; 
*) 
(* print_string "盘子总数为:"; *) 
(* print_int (totalNumberOfPlates result); *) 
(* print_newline; *) 
(* print_string "数据为:\nl1:"; *) 
(* List.map print_int (List.nth result 0); print_string "\nl2:"; *) 
(* List.map print_int (List.nth result 1); print_string "\nl3:"; *) 
(* List.map print_int (List.nth result 2); *) 
(* print_endline "Loop End"; *) 
result; 
with Failure "nth"-> 
print_endline "fail at nth"; 
data;; 

(* pos是x应该在的位置。*) 
(* spos是x的实际位置 *) 

let rec updatePos data x pos = 
match x with 
| 0 -> data; 
| _ -> 
assert(( totalNumberOfPlates data) == 7); 
let spos=searchPlatePos data x in 
(* Printf.printf "%d应该在%d,而实际在%d" x pos spos; *) 
(* print_endline "开始计算"; *) 
if (spos == pos) then (* 如果x就在这里,*) 
updatePos data (x-1) pos (* 那么计算x-1应该在哪里 *) 
else if(movable data x (pos-1) (spos-1) ) then 
moveData data (pos-1) (spos-1) (* 递归从这里跳出 *) 
else updatePos data (x-1) (otherPos pos spos) ;; 


let rec mainLoop data= 
match data with 
| []::[]::list::[] -> 
print_endline "end"; 
drawGraph data; 
| l1::l2::l3::[] -> 
let newData=updatePos data (totalNumberOfPlates data) 3 in 
drawGraph newData; 
mysleep 1.0; 
assert(( totalNumberOfPlates newData) == 7); 
mainLoop newData; 
;; 

let _ = 
Graphics.open_graph ""; 
Graphics.set_window_title "Han nuo ta"; 
Graphics.set_color Graphics.black; 
let l1=1::2::3::4::5::6::7::[] in 
let l2= [] in 
let l3= [] in 
let data=l1 :: l2 :: l3 :: [] in 
drawGraph data; 
mysleep 1.0; 
mainLoop data; 
Graphics.wait_next_event [Graphics.Key_pressed];;

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥