找鞍点

鞍点：

矩阵A_m×n中的元素A[i][j]是第i行中的最小值，同时是第j列中的最大值，则此元素为该矩阵的一个鞍点。

试编写程序，确定鞍点在矩阵中的位置。

思路：

1、分别将行最小、列最大存在两个三元表里

2、暴力查找

  1 #include <iostream>
  2 using namespace std;
  3 
  4 const int MAX_COL = 10, MAX_ROW = 10;
  5 struct elemt
  6 {
  7     int row, col;
  8     int val;
  9 };
 10 //Init
 11 void Init(int &nr, int &nc, int a[][MAX_COL]);
 12 //solve
 13 void solveIt(int a[][MAX_COL], int nr, int nc);
 14 //AppendElemt(n_rowMin, n_row, min, i, j);
 15 void AppendElemt(elemt tgt[], int &n, int val, int i, int j);
 16 
 17 int main()
 18 {
 19     int a[MAX_ROW][MAX_COL], nr, nc;
 20     Init(nr, nc, a);
 21     solveIt(a, nr, nc);
 22     system("pause");
 23     return 0;
 24 }
 25 void solveIt(int a[][MAX_COL], int nr, int nc)
 26 {
 27     elemt n_rowMin[MAX_COL*MAX_ROW], n_colMax[MAX_COL*MAX_ROW];
 28     int n_row, n_col = n_row = 0;
 29     
 30     //行最小
 31     for (int i = 0; i < nr; i++)
 32     {
 33         //判断行最小是否唯一
 34         int min = a[i][0], counter = 1;
 35         for (int j = 0; j < nc; j++)
 36         {
 37             if (a[i][j] < min)
 38             {
 39                 min = a[i][j];
 40                 counter = 1;
 41             }
 42             else if (a[i][j] == min)
 43             {
 44                 counter++;
 45             }
 46             else
 47                 continue;
 48         }
 49         //如果只有一个最小值，找到存完就break
 50         for (int j = 0; j < nc; j++)
 51             if (a[i][j] == min && !(counter - 1))
 52             {
 53                 AppendElemt(n_rowMin, n_row, min, i, j);
 54                 break;
 55             }
 56             else if (a[i][j] == min && (counter-1))
 57             {
 58                 AppendElemt(n_rowMin, n_row, min, i, j);
 59             }
 60             else
 61                 continue;
 62     }
 63 
 64     //列最大
 65     for (int i = 0; i < nc; i++)
 66     {
 67         //判断列最大是否唯一
 68         int max = a[0][i], counter = 1;
 69         for (int j = 0; j < nr; j++)
 70         {
 71             if (a[j][i] > max)
 72             {
 73                 max = a[j][i];
 74                 counter = 1;
 75             }
 76             else if (a[j][i] == max)
 77             {
 78                 counter++;
 79             }
 80             else
 81                 continue;
 82         }
 83         for (int j = 0; j < nr; j++)
 84             if (a[j][i] == max && !(counter - 1))
 85             {
 86                 AppendElemt(n_colMax, n_col, max, j, i);
 87                 break;
 88             }
 89             else if (a[j][i] == max && (counter - 1))
 90             {
 91                 AppendElemt(n_colMax, n_col, max, j, i);
 92             }
 93             else
 94                 continue;
 95     }
 96     int nSP = 0;
 97     for (int i = 0; i < n_row; i++)
 98     {
 99         for (int j = 0; j < n_col; j++)
100         {
101             if (n_rowMin[i].row == n_colMax[j].row&&n_rowMin[i].col == n_colMax[j].col&&n_rowMin[i].val == n_colMax[j].val)
102             {
103                 nSP++;
104                 cout << "(" << n_rowMin[i].row+1 << "," << n_rowMin[i].col+1 << ")=" << n_rowMin[i].val << endl;
105             }
106         }
107     }
108     cout << "共有" << nSP << "个鞍点" << endl;
109 }
110 void Init(int &nr, int &nc, int a[][MAX_COL])
111 {
112     cout << "请输入矩阵的行、列：" << endl;
113     cin >> nr >> nc;
114     cout << "请输入此矩阵：" << endl;
115     for (int i = 0; i < nr; i++)
116         for (int j = 0; j < nc; j++)
117             cin >> a[i][j];
118 }
119 void AppendElemt(elemt tgt[], int &n, int val, int i, int j)
120 {
121     tgt[n].row = i;
122     tgt[n].col = j;
123     tgt[n++].val = val;
124 }

View Code

使用循环的方法

思路：

1、遍历每一行的每一个元素（因为最值可能不唯一），假设该元素为鞍点，即行最小、列最大

2、验证，顺序输出

//循环实现找鞍点
#include <iostream>
using namespace std;
const int MAX = 10;//存储矩阵的阶数

int arr[MAX][MAX];
int nr,nc;//阶数
void Init();
void Find();

int main()
{
    Init();
    Find();
        return 0;
}
void Find()
{
    //鞍点：行最小值&&列最大值

    bool br, bc;//判断列最大和行最小
    int min_e, max_e;
    int flag = 0;//记录鞍点的个数
    for (int i = 0; i < nr; i++) {

        for (int j = 0; j < nc; j++)
        {
            //判断arr[i][j]是否为为行最小
            min_e = arr[i][j];
            br = true;//假设为行最小
            int t = nc;
            while (t--) {
                if (arr[i][t] < min_e) {
                    br = false;
                    break;
                }
            }
            //判断arr[i][j]是否为列最大
            bc = true;
            t = nr;
            max_e = arr[i][j];
            while (t--) {
                if (arr[t][j] > max_e) {
                    bc = false;
                    break;
                }
            }
            //结合
            if (br&&bc) {
                cout << "(" << i + 1 << "," << j + i << ")" << endl;
                flag++;
            }
        }
    }
    if (!flag) {
        cout << "无鞍点" << endl;
    }
    else
        cout << "共" << flag << "个" << endl;
}
void Init() {
    cout << "请输入矩阵的行数和列数：";
    cin >> nr >> nc;
    cout << "请输入该矩阵：";
    for (int i = 0; i < nr; i++)
        for (int j = 0; j < nc; j++)
            cin >> arr[i][j];
}

View Code