馬鞍數，是指數陣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數陣中的馬鞍數
主要定義,查找算法,
主要定義
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;}