九位不同数字乘法等式的递归与非递归回溯算法（三）
（……续上篇）
4 非递归回溯算法
将递归结构转化为非递归结构通常使用栈结构模拟系统调用进行转化[4]，但这样转化后的非递归结构与递归结构并没有本质区别，只是将系统递归调用时现场保护、恢复改为手动压栈与出栈[5][6]．通过分析递归回溯算法，可知对第n位数字的搜索为一个循环，该循环结束条件是搜索成功或n<1，循环内部首先保存n到k中，然后，如果第n位数字搜索失败则将n减1继续循环，直到第n位搜索成功，并且n=k；如果n<k，则将n加1继续循环．
下面的函数使用非递归回溯的算法在数组r中搜索前n位数字均不相同的排列．
- function NRS(n: integer;var r: TArr): boolean;
- var
- flag: boolean;
- k: integer;
- begin
- k:= n;
- flag:= false;
- repeat
- inc(r[n]);
- if r[n] > 9 then
- begin
- r[n]:= 0;
- dec(n);
- end
- else if not Clash(n, r) then
- if k = n then
- flag:= true
- else
- inc(n);
- until flag or (n < 1);
- result:= flag;
- end;
如果前n位数字可以找到符合条件的排列，则函数NRS返回“真”，否则返回“假”．
非递归回溯算法其它部分与递归回溯算法相同，仅在过程Equation中调用函数RS改为调用函数NRS即可．
5 实验测试及结论
经过编程计算共得到如下9组解：
- 12×483=5796；18×297=5346；27×198=5346；
- 28×157=4396；39×186=7254；4×1738=6952；
- 4×1963=7852；42×138=5796；48×159=7632．
通过分析算法，显然两种算法的时间复杂度均为O(n2)[5]，且执行操作基本相同，理论上算法耗时应趋于一致，但递归算法由于系统必须进行现场保护、恢复，所以耗时应该略大于非递归算法．在PC机P4-3GHz上由Delphi 2009实现，五次测试取平均值：递归算法耗时203ms，非递归算法耗时188ms，递归算法比非递归算法慢约8%．
参考文献
[1]Aho Alfred,Ullman Jeffrey,Hopcroft et al．The design and analysis of computer algorithms[M]．北京：机械工业出版社，2007．
[2]Levitin Anany, 潘彦[译]．算法设计与分析基础．北京：清华大学出版社，2004．
[3]郭继展，郭勇，苏辉．程序算法与技朽精选．北京：机械工业出版社，2008．
[4]吕国英，任瑞征，钱宇华．算法设计与分析．北京：清华大学出版社，2006．
[5]王晓东．计算机算法设计与分析[M]．北京：电子工业出版社，2001．
[6]严蔚敏，吴伟民．数据结构[M]．2版．北京：清华大学出版社，1996．
The recursive and non-recursive backtrack algorithms for nine different numerals constitute a equation of multiplication
BAI Yu
(School of Mathematics & Computer Science, Shanxi Datong University, Datong Shanxi, 037008)
Abstract: In this paper, analyze the "nine different numerals constitute a equation of multiplication", design a recursive backtrack algorithm and non-recursive backtrack algorithm, gave the general design for exhaustive algorithm of NP problem, at the same time, compared the characteristics of two algorithms, and experimental testing.
Keywords: Exhaustive algorithm; Recursive backtrack algorithm; Non-recursive backtrack algorithm; NP problem
（全文完）