Young氏矩阵的实现(PASCAL)

来源：百度知道 编辑：UC知道 时间：2024/06/30 14:06:48
一个m*n的Young氏矩阵(Young tableau)是一个M*N的矩阵，其中每一行的数据都从左到右排序，每一列的数据都从上到下排序。Young氏矩阵中了能会有些∞数据项，表示不存在的元素。所以，Young氏矩阵可以用来存放r≤mn个有限的数。
给出一个在非空m*n的Young氏矩阵上实现EXTRACT-MIN的算法(去掉并返回矩阵中的具有最大关键字的元素)的算法,使其运行时间为O(m+n)。你的算法应该使用一个递归子过程，它通过递归地解决(m-1)*n或m*(n-1)的子问题来解决m*n的问题。(提示：考虑以下MAX-HEAPIFY，既是建堆的过程。)

算法：
总是于最右上角的元素x比较；
1）如果为无限，那么元素只可能在后M-1行中
2）如果比无限小，那么最大元素只可能在前N-1列中或者就是他；

young氏矩阵去掉一行或一列还是young氏矩阵；
所以每次比较最少去掉一行或一列，这样复杂度就是o(m+n);

Program ex;
Const
maximum = 10000;

Var
n, m, i, j: longint;
a: array [1..100, 1..100] of longint;

Function find(x1, y2: longint): longint;
var
k: longint;
begin
if (x1 > n) or (y2 < 1) then
begin
find := -maximum;
exit;
end;
if a[x1, y2] = maximum then
k := find(x1, y2 - 1) else
begin
k := find(x1 + 1, y2);
if a[x1, y2] > k then
k := a[x1, y2];
end;
if k <> maximum then
find := k else
find := 0;
end;

Begin
readln(n, m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i, j]);
readln;
end;

writeln(find(1, m));