如何用斐波那契来计算各种方式的骨牌瓦片？

Question

(这可能看起来已经回答了，但我正在寻找更具体的东西。)对于家庭作业，我需要写一个方法来计算矩形被2*1的骨牌瓦片平铺的不同方式。从我所能看到的，它应该是该区域的斐波那契数。我写了在编译器中编译的代码，但不确定它是否真的有意义，也不知道从哪里开始。我如何才能更好地实现这一点？

public static int domino(int n, int m) // the method signature is what I must use according the hw instructions
{
int area =  n*m; // calculating the area of the passed in rectangle
int dominoes = area/2; // calculating how many dominos will be needed to cover the area
if (dominoes<=2) { // because fib 1 equals 1 and fib 2 equals 1
    return 1;
} //also the stopping point
else {return domino(dominoes-1, 0) + domino(dominoes-2, 0);}
}

我不需要担心这个作业的效率。

Answer 1

您没有使用递归调用正确地计算Fibonacci数。您正在执行以下操作：

else {return domino(domino-1，0) +domino(domino-2，0);}

所以本质上，在第一个递归调用n == (dominoes - 1)和m == 0中。这意味着计算面积总是得到0，因为任何东西乘以0等于0。

我的建议是使用额外的Fibonacci函数，如下所示：

public static int domino(int n, int m) {
    // return the fibonacci number of the number of dominoes in the given rectangle
    return fib((n * m) / 2);
}

public static int fib(int n) {
    if(n <= 2)
        // seed values of the fibonacci sequence
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}