在台上唱歌，最牛逼的不是唱完后观众热烈的掌声，而是开始歌唱时整个喧嚣的人群瞬间安静下来，静静地聆听。----anonymous
问题
Young氏矩阵是满足这样性质的m*n矩阵，它其中每一行的数据都从左到右排序，每一列的数据都从上到下排序。Young氏矩阵会有一些∞数据项，表示不存在的元素。所以，Young氏矩阵可以用来存放人r<=mn个有限的数。下图就是一个Young氏矩阵的例子。
- 给出在一个非空m*n的Young氏矩阵上实现EXTRACT-MIN的算法，使其运行时间为O(m+n)。定义T(p)为EXTRACT-MIN在任何m*n Young氏矩阵上的最大运行时间，其中p=m+n。给出表达T(p)的，界为O(m+n)的递归式，并解该递归式。
- 说明如何在O(m+n)时间内，将一个新元素插入到一个未满的m*n Young氏矩阵中。
- 在不用其它排序算法帮助的情况下，说明利用n*n Young氏矩阵对你n^2个数排序的运行时间为O(n^3)。
- 给出一个运行时间为O(m+n)的算法，来决定一个给定的数是否存在于一个给定的m*n Young氏矩阵中。
解：
- 可以利用类似于max_heapify的递归思想，将最小元素A[1,1]取出后再用∞赋值A[1,1]，然后对交换后的矩阵左上角元素进行递归操作reverse_young_min_heapify，直到整个矩阵符合Young氏矩阵的规则。T(p) = T(p-1) + O(1)，解递归式易得：T(p) = O(m+n)。
- 也是利用堆的思想，先将A[m,n]赋值为待插入元素，然后进行堆化递归操作即可。
- 利用extract_min易证。
- 思路是从矩阵右上角开始，如果该元素==k，则找到；如果该元素<k，则删去最上行，重复操作；如果该元素>k，则删去最右行，重复操作；
// realization of young tableau
// basic operation includes: insert,extract_min and find
// declare a[][] as a global array then all function delcaration can be greatly simplified
#include <iostream>
#include <ctime>
#include <cstdlib>
int a[11][11],b[101];
void insert(int a[][11],int);
void young_min_heapify(int a[][11],int,int);
int extract_min(int a[][11]);
void reverse_young_min_heapify(int a[][11],int,int);
void isfound(int a[][11],int,int,int);
void print();
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
const int infinity = 101;
const int m=10;
const int n=10;
using namespace std;
int main()
{
int i,j;
srand(time(0));
for(i=1;i<=100;i++)
b[i]= rand()%100;
cout<<"randomly generated numbers are: \n";
for(i=1;i<=100;++i)
cout<<b[i]<<(i%10==0?'\n':' ');
cout<<"corresponding Young matrix is:\n";
for(i=1;i<11;++i)
for(j=1;j<11;++j)
a[i][j] = infinity;
//a[i][j] = 10*i+j;
for(i=1;i<=100;++i)
insert(a,b[i]);
print();
int min = extract_min(a),num;
cout<<"the minimum element is : "<<min<<endl;
cout<<"Young tableau after min extraction is: \n";
print();
cout<<"input the number you are looking for: ";
cin>>num;
isfound(a,m,n,num);
return 0;
}
void insert(int a[][11],int element)
{
if(a[m][n] != infinity)
{
cerr<<"matrix is full,cannot insert anymore\n";
return ;
}
a[m][n] = element;
young_min_heapify(a,m,n);
}
void young_min_heapify(int a[][11],int i,int j)
{
int x,y;
if (i>1 && a[i][j] < a[i-1][j])
{
x = i-1;
y = j;
}
else { x = i; y = j;}
if (j>1 && a[x][y] < a[i][j-1])
{
x = i;
y = j-1;
}
if (x !=i || y !=j)
{
swap(a[i][j],a[x][y]);
young_min_heapify(a,x,y);
}
}
int extract_min(int a[][11])
{
int min = a[1][1];
a[1][1] = infinity;
reverse_young_min_heapify(a,1,1);
return min;
}
void reverse_young_min_heapify(int a[][11],int i,int j)
{
int x,y;
if (i<m && a[i][j] > a[i+1][j])
{
x = i+1;
y = j;
}
else { x = i; y = j;}
if (j<n && a[x][y] > a[i][j+1])
{
x = i;
y = j+1;
}
if( x!= i || y!= j)
{
swap(a[i][j],a[x][y]);
reverse_young_min_heapify(a,x,y);
}
}
void isfound(int a[][11], int x, int y, int k)
{
if ( x==0 || y == 0)
{
cout<<"k is not found\n";
return;
}
if (a[1][y] == k)
cout<<"k is found at ("<<1+m-x<<", "<<y<<")\n";
else if (a[1][y] > k) { isfound(a,x,y-1,k);}
else isfound(a+11,x-1,y,k);
}
void print()
{
int i,j;
for(i=1;i<11;++i)
for(j=1;j<11;++j)
cout<<a[i][j]<<(j==10?'\n':' ');
}
codeblocks使用心得 目前还没有找到直接watch指针指向数组全部内容的方法。目前达到的程度仅仅是：
- 对于一维数组，例如 int a[] = {...}，使用add watch a 可以查看数组内容；但是如果令int *b = a，需要设置watch b，然后选择watch as array；
- 对于二维数组，例如 int a[][] = {...}，使用add watch a，选择watch as array选项，确定start和count就可以查看整个数组内容。或者使用dereference of a，然后watch as array。其中后者更加方便，因为可以显示数字序号。