馬鞍數

馬鞍數，是指數陣n*m中在行上最小而在列上最大的數。

如：數陣n*m，其中 n=5 m=5

1 6 7 8 9

4 5 6 7 8

3 4 5 2 1

2 3 4 9 0

5 6 7 6 8

則第5行第1列的數字“5”即為該數陣的一個馬鞍數。

基本介紹

• 中文名：馬鞍數
• 外文名：Saddle number
• 簡介：指數陣n*m中在行上最小
• 例子：數陣n*m，其中 n=5 m=5
• 問題描述：求一個n×n數陣中的馬鞍數

主要定義

馬鞍數，是指數陣n*m中在行上最小而在列上最大的數。如：數陣n*m，其中 n=5 m=5

1 6 7 8 9

4 5 6 7 8

3 4 5 2 1

2 3 4 9 0

5 6 7 6 8

則第5行第1列的數字“5”即為該數陣的一個馬鞍數。
可以證明，一個數陣中要么存在唯一一個馬鞍數，要么不存在馬鞍數。

查找算法

對於任一數陣n*m，如數陣中存在馬鞍數則輸出其在數陣中的位置，否則提示數陣不存在馬鞍數（點）。以下用C實現特殊的數陣情形，問題描述：求一個n×n數陣中的馬鞍數，輸出它的位置。一般情形只需仿照以下算法實現即可。程式編譯運行及輸入輸出結果如右圖所示：

-----------------------------------c語言實現------------------------------------

#include<stdio.h>void main(){int p[30][30];//數陣最大為30*30int n,i,j;int min,x,y;int exist;printf("請輸入n*n數陣中n的大小:如5\n");scanf("%d",&n);printf("請輸入該%d*%d數陣中每個元素的大小,如若為2*2數陣,輸入2,3,4,5\n",n,n);for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d,",&p[i][j]);}for(i=1;i<=n;i++){for(j=1;j<=n;j++){printf("%-3d ",p[i][j]);}printf("\n");}for(i=1;i<=n;i++){min=p[i][1];x=i;y=1;//行最小for(j=1;j<=n;j++){if(p[i][j]<min){min=p[i][j];y=j;}}//列最大for(j=1;j<=n;j++){if(p[x][y]<p[j][y])break;}if(j>n){printf("馬鞍數在該數陣中的位置為(行,列):(%d,%d)\n",x,y);exist=1;}}if(exist==0)printf("該數陣中不存在馬鞍數!\n");}

c實現查找數陣中馬鞍數運行結果

-----------------------------------c語言實現----------------------------------

#include<stdio.h>  #include<stdlib.h>  #define M 4  #define N 4  void main(){    int a[M][N], i, j;//定義數組    int MinNum[4], MaxNum[4];    int t = 0;    //輸入4*4的數組    for (i = 0; i < M; i++)    {   for (j = 0; j < N; j++)   {  scanf_s("%d", &a[i][j]);   }    }    //找出每行中最小的數值    for (i = 0; i < M; i++)    {   MinNum[i] = a[i][0];           //此時假設每一行的最小值是第一個數即a[i][0]     for (j = 1; j < N; j++)       //找出行中的最小值     {  if (MinNum[i] > a[i][j])   { MinNum[i] = a[i][j]; //將值賦值給對應數組  }}   printf("%d\n", MinNum[i]);    }    //找出每列中最大的數值    for (j = 0; j < N; j++)    {   MaxNum[j] = a[0][j];   //此時假設每一行的最小值是第一個數即a[0][j]   for (i = 1; i < M; i++)   //找出列中的最大值            {  if (a[i][j] > MaxNum[j])  { MaxNum[j] = a[i][j]; //將值賦值給對應數組  } }   printf("%d", MaxNum[j]);    }    for (i = 0; i < M; i++)//遍歷所有元素    {   for (j = 0; j < N; j++)   {  if (a[i][j] == MinNum[i] && a[i][j] == MaxNum[j])//看是否存在對應元素既是所在列最大數，又是所在行最小數  { t = 1; printf("\nCongratulation！You has found the number which is %d,and It's in the %d line, the %d column", a[i][j], i+1, j+1);  }}    }    if (t == 0)//當t 等於0時，表面沒有此數    {   printf("\nSorry，This number is non-existent.");    }    system("pause");}

--------------------------------c++實現－－－－－－－－－－－－－－

#include<iostream>#include<cstdio>using namespace std;#define MAX 1001//極端情況int a[MAX][MAX];int main(){    int n , m;    scanf("%d%d",&n,&m);    for(int i = 0 ; i < n ; ++i)    {        for(int j = 0 ; j < m ; ++j)        {            scanf("%d",&a[i][j]);        }    }    bool noans=true;    for(int i = 0 ; i < m ; ++i)    {        int tMAX=a[0][i],tMAXn=0;        for(int j = 1 ; j < n ;++j)//遍歷數組查找到列最大        {            if(tMAX<a[j][i])            {                tMAX=a[j][i];                tMAXn=j;            }        }        //找到列最大後查找是否是行最小        bool check=true;        for(int j = 0 ; j < m ;++j)        {            if(a[tMAXn][j]<tMAX && j!=i)            {                check=false;                break;            }        }        if(check)        {            printf("%d %d %d",tMAXn+1,i+1 ,tMAX);            noans=false;            break;        }    }    if(noans)    {        printf("No");    }    return 0;}