数据�l�构�W�五章算法设计题[5]_跨考网

1�Q�请�~�写完整的程序。如果矩�?/span>A中存在这��L(f��ng)��一个元�?/span>A[i,j]满��条�g:A[i,j]是第i行中值最���的元素,且又是第j列中值最大的元素�Q�则�U�C�������矩阵的一个马鞍点。请�~�程计算�?/span>m*n的矩�?/span>A的所有马鞍点�?/span> �?a target="_blank">上�v大学 2000 �?/span> �Q?/span>20分）(j��)】【中�U�院自动化所 1997�?/span>

　　【参考答案�?/span>

　　[题目分析] ��L��马鞍�Ҏ(gu��)��直接的方�?/span>,是在一行中扑և�一个最���值元�?/span>,然后���(g��)查该元素是否是元素所在列的最大元�?/span>,如是,则输��Z��个马鞍点,旉���复杂度是O(m*(m+n)).本算法��用两个辅助数�l?/span>max�?/span>min,存放每列中最大值元素的行号和每行中最���值元素的列号,旉���复杂度�ؓ(f��)O�Q?/span>m*n+m�Q�，但比较次数比前种���法�?x��)增加，也多使用向量�I�间�?/span>

　　int m=10, n=10;

　　void Saddle(int A[m][n])

　　//A�?/span>m*n的矩�?/span>,本算法求矩阵A中的马鞍�?/span>.

　　{int max[n]={0}, //max数组存放各列最大值元素的行号,初始化�ؓ(f��)行号0;

　　min[m]={0}, //min数组存放各行最���值元素的列号,初始化�ؓ(f��)列号0;

　　i, j;

　　for(i=0;i<m;i++) //选各行最���值元素和各列最大值元�?/span>.

　　for(j=0;j<n;j++)

　　{if(A[max[j]][j]<A[i][j]) max[j]=i; //修改�W?/span>j列最大元素的行号

　　if(A[i][min[i]]>A[i][j]) min[i]=j; //修改�W?/span>i行最���元素的列号.

　　}

　　for (i=0;i<m;i++)

　　{j=min[i]; //�W?/span>i行最���元素的列号

　　if(i==max[j])printf(�?/span>A[%d][%d]是马鞍点�Q�元素值是%d�?/span>,i,j,A[i][j]); //是马鞍点

　　}

　　}// Saddle

　　[���法讨论] 以上���法假定每行�Q�列�Q�最多只有一个可能的马鞍点，若有多个马鞍�?/span>,因�ؓ(f��)一�?/span>(或一�?/span>)中可能的马鞍�Ҏ(gu��)��值是相同的，则可用二�l�数�l?/span>min2�Q�第一�l�是行向量，是各行行��P���W�二�l�是列向量，存放一行中最大值的列号。对最大��g��同样处理�Q���用另一二维数组max2�Q�第一�l�是列向量，是各列列��P���W�二�l�存该列最大值元素的行号。最后用�c�M��上面�Ҏ(gu��)���Q�找出每�?/span>(i)最���值元素的每个列号�Q?/span>j�Q�，再到max2数组中找该列是否有最大值元素的行号�Q?/span>i�Q�，若有�Q�则是马鞍点�?/span>