杨氏矩阵（Young tableau）是一种简单却很神奇的数据结构，具有类似于堆的操作和性质。在实际中可能不是很常用，但在面试中却经常遇到，比较考察程序员的算法思维能力。 本文主要讲解下杨氏矩阵的定义及一般的操作和计数问题。 现在我们不考虑没有元素的格子，杨氏矩阵会变成一种不规则的形状，如 现在可以计算把1到n这n个元素放到这个形状的钩子里面的方法总数（称为钩长公式），方法总数等于n！除以所有格子的钩长的乘积。例如，上述的结果为 11!/(1 * 2*3*4 * 3*4*5 * 4*5*6*7) = 33。 特殊地，1到2*n这2*n个数填入一个2 x n的杨氏矩阵的填法个数为 (2*n)! / (n! * (n+1)!)，答案很大要求模时可以利用扩展欧几里得算法求出每个除数的逆，把除法转化为乘法。 二 初始化和打印 以下的代码中把矩阵定义为全局变量，方便在函数中使用。另外用常量oo表示无穷大，初始化为一个很大的整数。 打印时就相当于打印一个矩阵，为了美观，把无穷大输出为oo的符号。 const int mx = 100, oo = 1<<30; int Young[mx][mx], m, n;//杨氏矩阵，长，宽 void init() { m = n = 4; int a[] = { 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16}; int len = sizeof(a) / sizeof(a[0]); sort(a, a+len); for (int i = 0, id = 0; i < m; i++) for (int j = 0; j < n; j++) Young[i][j] = id < len ? a[id++] : oo; } void print() { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) if (Young[i][j] == oo) printf("%s ", "oo"); else printf("%2d ", Young[i][j]); printf("\n"); } printf("\n");
Read full article from 杨氏矩阵的操作与计数 » NoAlGo博客
No comments:
Post a Comment