算法是程序的核心,无关语言。适当的了解算法,可以帮你完成一些看似不可能完成的任务。递归能够把复杂问题简单化,有点类似于高中数学中的归纳推理法。DFS,深度优先搜索算法,是图论算法中的一种。DFS 就是一种暴力穷举法,把所有的情况都进行探索下,不遗漏也不重复。由于计算空间和时间的限制,有时候我们不需要穷举所有的情况,找到一种满足的条件,就可以终止,或者找到最优的情况就可以终止。
第24题一马当先,来源于pythontip网站
#!/usr/bin/perl -wuse strict;# 设置棋盘大小 8*8my $col_n=8;my $row_m=8;my ($col_now,$row_now)=(0,0);my @step;#DFS:一条路走到底的穷举法#refer:http://baike.baidu.com/view/288277.htm#step1 产生一个矩阵表示棋谱my @chess;for my$key1(0..$col_n){map{$chess[$key1][$_]=0}(0..$row_m);#0代表没有走过,1代表走过}#step2 设置马的走法my $steps=[[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];#step3 设置全局变量,一条路走到底的变量#@chess也是全局变量my $flag=0;my $step_num=0;my $minnum=10000000;my @paths=();go($col_now,$row_now,@oldpaths);print $flag,"\n";print $minnum,"\n";{my $col_now=shift;my $row_now=shift;#把走过的地方添加到路径中push @paths,$col_now,$row_now;$chess[$col_now][$row_now]=1; #访问过了的标志$step_num++;#实现剪枝,如果step_num 比已有的minnum 要大就不要探索了。if($step_num >$minnum){return}if($col_now==$col_n and $row_now==$row_m) #判断这条路是否走成功{$flag=1;print "success\n,you have access the destination\n";print "paths:";print join ",",@paths;print "\n";$minnum=$minnum<$step_num?$minnum:$step_num;return 1;}#下一步可能的走法for my $step(@$steps){my $col_new=$col_now+$step->[0];my $row_new=$row_now+$step->[1];#print "$col_new $row_new\n";if($col_new>0 and $col_new<= $col_n and $row_new>0 and $row_new<=$row_m){if($chess[$col_new][$row_new]==0){# print " goto $col_new $row_new\n";#递归 走下一步go($col_new,$row_new,@newpaths);#关键 回复全局变量#pop shiftpop @paths;pop @paths;# print join ",",@paths;# print "\n";$step_num--;$chess[$col_new][$row_new]=0;}}}}__END__
核心是第7步,稍微想想整个模型,就可以了。
最近一直没有给大家推送一些perl知识。最主要原因,没有找到值得推送的内容。另外在这段时间里,看了一些python模块,一些c++,一些c。在化学信息领域,目前python的模块比perl的模块多的多,比如RDKIT,openbabel,pybel,pymol,而perl里面只有2个,一个是功能有限的HackaMol。一个是没有人维护的PerlMol。
c++ 中的class 我觉得是最经典的,好多用法也接近于动态语言,值得学习,推荐
如果你觉得perl没什么好学的,推荐你看<<高阶perl>>这本书。第一章就是递归与回调。