java - 如何用斐波那契计算多米诺骨牌的各种方式？

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

您没有使用递归调用正确计算斐波那契数。您正在执行:

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

本质上，在第一个递归调用中，n == (dominoes - 1) 和 m == 0。这意味着计算面积的结果始终为 0，因为任何值乘以 0 都等于 0。

我的建议是使用额外的斐波那契函数，如下所示:

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);
}