1、鞍点是指矩阵中的某元素A[i][j]是第i行中值最小的元素，同时又是第j列中值最大的元素。试设计一个算法求矩阵A中的所有鞍点。
1 #include <stdio.h> 2 3 #define M 4 4 #define N 5 5 /* 求二维数组的所有鞍点 */ 6 void saddlePoint(int arr[M][N]) 7 { 8 int i,j,k,min,c,count=0; 9 int minI[N] = {0}; /* 存储c个, 第i行最小元素所在列 */ 10 for(i=0; i<M; ++i ){ 11 min = arr[i][0]; /* 二维数组第i行第0个元素 */ 12 c = 1; 13 minI[c] = 0; 14 for(j=1; j<N; ++j){ 15 if(arr[i][j]<min){ 16 min = arr[i][j]; 17 c = 1; /* 第i行最小元素的个数 */ 18 minI[c] = j; /* 第i行最小元素的下标j */ 19 } 20 else if(arr[i][j]==min){ /* 第i行存在多个最小元素 */ 21 c++; /* 第i行最小元素 共c个*/ 22 minI[c] = j; /* 第i行最小元素 所在列j */ 23 } 24 } 25 for(j=1; j<=c; ++j){ 26 k=0; 27 while(k<M && arr[i][minI[j]]>=arr[k][minI[j]]) 28 k++; /* 如果第i行最小元素大, 列k++ */ 29 if(k>=M){ /* 第i行最小元素是第j列的最大元素 */ 30 count++; /* 鞍点个数++ */ 31 /* 鞍点所在行、列、数据 */ 32 printf("arr[%d][%d]=%d ", i, minI[j],min); 33 } 34 } 35 } 36 if(count==0) 37 printf("鞍点不存在 "); 38 else 39 printf("有%d个鞍点 ", count); 40 } 41 42 int main() 43 { 44 int arr[M][N] = { {6,6,5,7,5}, 45 {8,7,4,8,1}, 46 {7,6,5,8,5}, 47 {9,2,2,4,3} 48 }; 49 saddlePoint(arr); 50 return 0; 51 }
2、设计一个算法，实现将一维数组A（下标从1开始）中的元素循环右移k位，要求只用一个元素大小的辅助空间，并给出算法的时间复杂度。
1 /* 算法复杂度O(n) */ 2 #include <stdio.h> 3 4 #define N 100 5 void reverse(int a[],int n){ 6 int i,t; 7 for(i=0; i<n/2; ++i){ 8 t = a[i]; 9 a[i] = a[n-i-1]; 10 a[n-i-1] = t; 11 } 12 } 13 14 void rotate(int a[], int n, int k){ 15 k %= n; 16 reverse(a+1,n); 17 reverse(a+1,k); 18 reverse(a+1+k,n-k); 19 } 20 21 int main() 22 { 23 int arr[N] = {0,1,2,3,4,5,6}; 24 int i, n = 6, k = 2; 25 rotate(arr,n,k); 26 for(i=1; i<n; ++i){ /* 下标从1开始 */ 27 printf("%d ",arr[i]); 28 } 29 return 0; 30 }
/*算法复杂度O(n^2)*/ #include <stdio.h> #define N 100 void reverse(int a[],int n, int k){ int i,j; k %= n; for(i=0; i<k; ++i){ a[0] = a[n]; for(j=n-1; j>=1; j--) a[j+1] = a[j]; a[1] = a[0]; } } int main() { int arr[N] = {0,1,2,3,4,5,6}; int i, n = 6, k = 2; reverse(arr,n,k); for(i=1; i<n; ++i){ /* 下标从1开始 */ printf("%d ",arr[i]); } return 0; }