迭代法塔的问题，如果中国

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

看递归解决方案。使用Perl语言完成了不到一分钟。

sub hanno_recursive {

my ($from, $to, $reserve, $n) =  @_;

if (1 == $n) {

print “move $n from $from to $to\n”;

return;

}

hanno_recursive($from, $reserve, $to, $n -1);

print “move $n from $from to $to\n”;

hanno_recursive($reserve, $to, $from, $n -1);

}

极其简洁优美。充分体现了递归的优雅。

接下来。考虑迭代解法。考虑将问题分解为树结构。非常显然， 将A B C看成一个圈， 则左右子树具有某种对称。即顺时针或逆时针旋转。

这样。我们全然能够通过左树求得右树， 问题变成为了线性递归， 这个非常easy转换为迭代。

原理知道了， 写这个代码，还是比較费劲， 花了1个小时才调好。

sub hanno_iterate { my ($from, $to, $reserve, $n) =  @_; my @left = (); my @right = (); #move to leaf node my $count = $n; while ($count > 1) { my $tmp = $to; $to = $reserve; $reserve = $tmp; $count–; } for (my $index = 1; $index <= $n; $index++) { my $new = “move $index from $from to $to\n”; push @left, $new; while ($new = shift @right) { push @left, $new; } last if ($index == $n); if (($index % 2) == ($n % 2)){ # anti-clock $from -> $to, $reserve->$from, $to -> $reserve foreach my $opt(@left) { my $left_value = “$opt”; $left_value =~ tr/ABC/CAB/; push @right, $left_value; } } else { # clock $from -> $reserve, $reserve->$to, $to -> $from foreach my $opt(@left) { my $left_value = “$opt”; $left_value =~ tr/ABC/BCA/; push @right, $left_value; } } my $tmp = $to; $to = $reserve; $reserve = $tmp; } foreach my $opt(@left) { print $opt; }

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117628.html原文链接：https://javaforall.cn