河内塔代码中的错误

Question

在编写河内塔的递归解决方案时，我的代码适用于 1、2 和 3 个圆盘，但之后就不行了。无法弄清楚我做错了什么。

package recursion;

import java.util.List;

import org.springframework.util.Assert;

import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;

public class Hanoi {

    private static List<Integer> reference = Lists.newArrayList(4, 3, 2, 1);

    private static List<Integer> aList = Lists.newArrayList(reference);
    private static List<Integer> bList = Lists.newArrayListWithCapacity(aList.size() - 1);
    private static List<Integer> cList = Lists.newArrayListWithCapacity(aList.size());

    public static void main(String[] args) {

        hanoi(aList, bList, cList);
        System.out.println(cList);
        Assert.isTrue(cList.equals(reference));
        Assert.isTrue(aList.size() == 0);
        Assert.isTrue(bList.size() == 0);
        System.out.println("done");

    }

    private static void hanoi(List<Integer> aList, List<Integer> bList, List<Integer> cList) {
        if (aList.size() == 1) {
            cList.add(aList.remove(0));
            return;
        }
        hanoi(aList.subList(1, aList.size()), cList, bList);
        print();
        hanoi(aList.subList(0, 1), null, cList);
        print();
        hanoi(bList, aList, cList);
        print();
        System.out.println("=======================================");
    }

    private static void print() {
        System.out.println(aList);
        System.out.println(bList);
        System.out.println(cList);
        Assert.isTrue(Ordering.natural().reverse().isOrdered(aList));
        Assert.isTrue(Ordering.natural().reverse().isOrdered(bList));
        Assert.isTrue(Ordering.natural().reverse().isOrdered(cList));
        System.out.println("******************************************");
    }
}

Answer 1

您的算法基于以下假设：在第一步（和最后一步）中，河内塔总是移动除一个切片之外的所有切片。

这个假设是错误的。子问题移动较小的塔。

为您的 hanoi 方法添加参数大小。三个步骤都要调整：

第 1 步和第 3 步应该只移动 size-1
第 2 步不应该移动第一个切片，而是最后一个（最上面的）

河内塔代码中的错误

bug in towers of hanoi code

java

algorithm

recursion

towers-of-hanoi