熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第五章 答案[33]

2013-11-15 15:12:12  來源: 數據結構 

  [題目分析] 尋找馬鞍點最直接的方法是在一行中找出一個最小值元素然後檢查該元素是否是元素所在列的最大元素如是則輸出一個馬鞍點時間復雜度是O(m*(m+n))本算法使用兩個輔助數組max和min存放每列中最大值元素的行號和每行中最小值元素的列號時間復雜度為O(m*n+m)但比較次數比前種算法會增加也多使用向量空間

  int m= n=;
  void Saddle(int A[m][n])
  //A是m*n的矩陣本算法求矩陣A中的馬鞍點
  {int max[n]={} //max數組存放各列最大值元素的行號初始化為行號;
  min[m]={} //min數組存放各行最小值元素的列號初始化為列號;
  i j;
  for(i=;i<m;i++) //選各行最小值元素和各列最大值元素
  for(j=;j<n;j++)
  {if(A[max[j]][j]<A[i][j]) max[j]=i;  //修改第j列最大元素的行號
  if(A[i][min[i]]>A[i][j]) min[i]=j;  //修改第i行最小元素的列號
  }
  for (i=;i<m;i++)
  {j=min[i];             //第i行最小元素的列號
  if(i==max[j])printf(A[%d][%d]是馬鞍點元素值是%dijA[i][j]);  //是馬鞍點
  }
  }// Saddle

  [算法討論] 以上算法假定每行(列)最多只有一個可能的馬鞍點若有多個馬鞍點因為一行(或一列)中可能的馬鞍點數值是相同的則可用二維數組min第一維是行向量是各行行號第二維是列向量存放一行中最大值的列號對最大值也同樣處理使用另一二維數組max第一維是列向量是各列列號第二維存該列最大值元素的行號最後用類似上面方法找出每行(i)最小值元素的每個列號(j)再到max數組中找該列是否有最大值元素的行號(i)若有則是馬鞍點

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23042.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.