大家好,又见面了,我是全栈君,今天给大家准备了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;
}
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117628.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...