c - C中的矩阵问题

Question

在具有 k 个对象的 mxn 矩阵中，将对象放置在矩阵单元格中的方式有​​多少种。(k<=n,m)。举个例子，说明得更清楚，如果“k”个对象中的第一个对象被放置在位置(1,1)，那么下一个对象不能被放置在第一列或第一行，并且对于剩余的其余对象。

问题的输出将类似于:(第 k 个对象，第 n 行，第 m 列)即(3,3,4)或非正式地，“k 个对象可以有多少种方式放置在 (nxm) 个矩阵单元上。

我发现了工作规则，说:[n(n-1)(n-2)...(n-(k-1))][m(m-1)(m-2)...(m-(k-1))] --> 这会给我准确的方法数，k 个对象可以放置在单元格中，并应用约束。

但我无法构建“嵌套 for 循环”条件: 对于(对象) 对于(行) 对于(列)

我正在使用 C!

在构建代码时需要一些帮助!

Answer 1

正如我所说 here , 只需执行 this .

/* n,m,k are constants */
int rook() {
    int i, j, mem[m+1][k+1];
    for (i=0; i<=m; i++)
        mem[i][0] = 1;
    for (j=1; j<=k; j++)
        mem[0][j] = 0;
    for (i=1; i<=m; i++)
        for (j=1; j<=k; j++)
            mem[i][j] = mem[i-1][j] + (n-j+1)*mem[i-1][j-1];
    return mem[m][k];
}

像往常一样，您可以优化它以使用 O(k) 空间。