关于找鞍点的算法！：）谢谢指教！：）

fydream · 发表于 2004-12-5 18:28:25

[code:1]/*找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点*/
#define m 3
#define n 3
int andian(int b[m][n])
{
int a,h,i,max_line,min_lie;
int c[m][n];
for(i=0;i<m;i++)
{
   for(a=0;a<n;a++)
      max_line=c[i][0];/*设每行的第一列都是这一行最大的元素*/
      if(c[i][a]>max_line)
         max_line=c[i][a];/*在列循环中如果找到一个书大于c[i][0]那就把这个数，赋值给max_line*/
}
for(a=0;a<n;a++)
{
for(i=0;i<m;i++)
      min_lie=c[0][a];
      if(c[i][a]<min_lie)
         min_lie=c[i][a];/*和上面的意思大致相同，只不过是反过来*/
}
if(max_line==min_lie)/*经过这两个大循环，如果找到的这两个说相同，说明，这个说就是鞍点*/
      h=min_lie;
return(h);
}
main()
{
int a[m][n],i,j,x;
printf("请输入一个三行三列的数组\n");
for(i=0;i<m;i++)
      for(j=0;j<n;j++)
   scanf("%d",&a[m][n]);
int andian(int a[m][n]);
x=a[m][n];
printf("%d\n",x);
} [/code:1]
我的编译结果：
[code:1]fydream@linux:~/源代码/unit 7> ./dreamdead
请输入一个三行三列的数组
1 2 3 5 6 7 8 4 9
9
[/code:1]
[code:1]鞍点应该是3亚？怎么给我答应出来的是9呀？我的程序8成是些错了，但是我现在思路很乱，请兄弟们给予指教亚！谢谢了！：）[/code:1]

sagaeon · 发表于 2004-12-5 19:38:09

[code:1]/*找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点*/
#define m 3
#define n 3
int andian(int b[m][n]) // b没用到？？？？？？？？？？？？？
{
int a,h,i,max_line,min_lie;
int c[m][n];
for(i=0;i<m;i++)
{
   for(a=0;a<n;a++)
      max_line=c[i][0];  //放在这儿？？？？？？？？？？？？？？？？？？？？
      if(c[i][a]>max_line)
         max_line=c[i][a];/*在列循环中如果找到一个书大于c[i][0]那就把这个数，赋值给max_line*/
}
for(a=0;a<n;a++)
{
for(i=0;i<m;i++)
      min_lie=c[0][a];
      if(c[i][a]<min_lie)
         min_lie=c[i][a];/*和上面的意思大致相同，只不过是反过来*/
}
if(max_line==min_lie)/*经过这两个大循环，如果找到的这两个说相同，说明，这个说就是鞍点*/
      h=min_lie;
return(h);
}
main()
{
int a[m][n],i,j,x;
printf("请输入一个三行三列的数组\n");
for(i=0;i<m;i++)
      for(j=0;j<n;j++)
   scanf("%d",&a[m][n]);
int andian(int a[m][n]);
x=a[m][n];  //x永远都是 a[3][3]！！！！！！！！！！！！！！！！！！！！！！！1
printf("%d\n",x);
} [/code:1]

fydream · 发表于 2004-12-6 19:57:08

好的！我知道乐！谢谢！我在改改！：）

fydream · 发表于 2004-12-6 20:26:04

不对！我的程序有很大的错误！我得好好改改了！谢谢老兄指教！：）

fydream · 发表于 2004-12-6 21:50:47

今天太晕了！我说什么也不能把这个鞍点的函数定义好！。。。。。。
求助！！：）谢谢！：)

fydream · 发表于 2004-12-6 22:08:43

请谅解小弟我的愚笨！我只能改成这样了！
[code:1] /*找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点*/
#define m 3
#define n 3
main()
{
  int andian(int b[m][n]);
  int a[m][n],i,j,x;
  printf("请输入一个三行三列的数组\n");
  for(i=0;i<m;i++)
for(j=0;j<n;j++)
   scanf("%d",&a[i][j]);
  x=andian(a[m][n]);
  printf("%d\n",x);
}
int andian(int b[m][n])
{
  int a,h,i,j,max_line,dian;
  int c[m][n];
  while(i<m)
  { i=0;
max_line=c[i][0];
for(a=0;a<n;a++)
{
   if(c[i][a]>max_line)
   {max_line=c[i][a];
   for(j=0;j<m;j++)
      if(c[j][a]<c[i][a])
      dian=c[j][a];
   }
   }
   i++;
}
return(dian);
} [/code:1]
[code:1]fydream@linux:~/源代码/unit 7> gcc -o dreamdead 78shiyan.c
78shiyan.c: In function `main':
78shiyan.c:12: warning: passing arg 1 of `andian' makes pointer from integer without a cast
fydream@linux:~/源代码/unit 7> ./dreamdead
请输入一个三行三列的数组
1 2 3 4 5 6 7 8 9
134514032
fydream@linux:~/源代码/unit 7>
[/code:1]
我今天太晕了！请兄弟们帮助改改！！太谢谢了！：）

sagaeon · 发表于 2004-12-6 22:29:00

你的dian不是每个分支都有返回值的。你在dian定义处赋0看看就明白了。

sagaeon · 发表于 2004-12-6 22:34:33

摘自严蔚敏《数据结构》c版[code:1]void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点
{
  for(i=0;i<m;i++)
  {
for(min=A[i][0],j=0;j<n;j++)
   if(A[i][j]<min) min=A[i][j]; //求一行中的最小值
for(j=0;j<n;j++)
   if(A[i][j]==min) //判断这个(些)最小值是否鞍点
   {
      for(flag=1,k=0;k<m;k++)
      if(min<A[k][j]) flag=0;
      if(flag)
      printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);
   }
  }//for
}//Get_Saddle
[/code:1]

fydream · 发表于 2004-12-7 22:32:59

谢谢！：）我再好好想想！我就不信我搞不定它！！！！

fydream · 发表于 2004-12-7 23:33:31

小弟我求得了一个真确的源代码，但是有些地方不是很明白！清兄弟们指教指教！：）
[code:1]#include "stdio.h"
#define M 3
#define N 3

int andian(int b[M][N])

{ int i,j,m,Row,Lie,dian;
for(i=0;i<M;i++)//遍历所有行
{
   dian=b[i][0];
   Row=i;
   for(j=1;j<N;j++)
   if(b[i][j]>dian)//找到一行中的最大值
   {
      dian=b[i][j];
      Lie=j;
   }
   for(m=0;m<M;m++)//判断一行中的最大值是否是所在列的最小值
   if(b[m][Lie]<dian)
      break;
   if(m==M)
   {
      printf("鞍点在第%d行，第%d列\n",Row+1,Lie+1);
      return (dian);
   }
}
printf("没有鞍点\n");
return 0;
}
main()
{
  int a[M][N],i,j,x;
  printf("请输入一个三行三列的数组\n");
  for(i=0;i<M;i++)
for(j=0;j<N;j++)
   scanf("%d",&a[i][j]);
  x=andian(a);
  printf("%d\n",x);
}[/code:1]
第一个不明白的地方是：
[code:1]    for(m=0;m<M;m++)//判断一行中的最大值是否是所在列的最小值
   if(b[m][Lie]<dian)
      break;
   if(m==M)
   {
      printf("鞍点在第%d行，第%d列\n",Row+1,Lie+1);
      return (dian);
   }[/code:1]
为什么第一个if判断的是b[m][Lie]<dian而第二个if却判断的是m==M??
第二个不明白的地方是：
[code:1] for(i=0;i<M;i++)//遍历所有行
{
   dian=b[i][0];
   Row=i;
   for(j=1;j<N;j++)
   if(b[i][j]>dian)//找到一行中的最大值
   {
      dian=b[i][j];
      Lie=j;
   }
   for(m=0;m<M;m++)//判断一行中的最大值是否是所在列的最小值
   if(b[m][Lie]<dian)
      break;
   if(m==M)
   {
      printf("鞍点在第%d行，第%d列\n",Row+1,Lie+1);
      return (dian);
   }
}
printf("没有鞍点\n");
return 0;
}[/code:1]
在这个大循环中，那个break是结束的哪个循环呀？：）
就是这两个疑问，谢谢指教！：）

sagaeon · 发表于 2004-12-7 23:50:00

楼主要独立思考哦

fydream · 发表于 2004-12-8 09:14:07

好的！我明白了！：）我要自己搞定它！：）

sagaeon · 发表于 2004-12-8 09:43:07

[quote:e93749b2e5="fydream"]好的！我明白了！：）我要自己搞定它！：）

[/quote]赞！

fydream · 发表于 2004-12-8 10:39:35

[code:1]#include "stdio.h"
#define M 3
#define N 3

int andian(int b[M][N])

{ int i,j,m,Row,Lie,dian;
for(i=0;i<M;i++)/*遍历所有行*/
{
   dian=b[i][0];/*设每一行的第一个元素是鞍点*/
   Row=i;/*接受行数，以便以后打印鞍点的行数*/
   for(j=1;j<N;j++)/*在行循环中嵌套行中的元素循环，以便进行比较，找出行中最大元素*/
   if(b[i][j]>dian)/*找到一行中的最大值*/
   {
      dian=b[i][j];/*在嵌套的列循环中，把找到的大于dian的那个元素的值，赋给dian*/
      Lie=j;/*接受列数，以便以后打印鞍点所在的列数*/
   }
   for(m=0;m<M;m++)/*判断一行中的最大值是否是所在列的最小值*/
      if(b[m][Lie]<dian)/*判断行中最大点所在的列，这个点是不是在它坐在的列的最小值*/
         break;/*???如果是最小值，就退出大循环？？？？我觉得这时候应该接受鞍点的值呀，但是他为什么要退出循环，去打印“没有鞍点呢？？？*/
   if(m==M)/*小弟愚笨，个人认为m不可能等于M呀？？？，但是为什么要判断m==M时，才返回andian呢？此时andian的值是什么呢？？？*/
   {
      printf("鞍点在第%d行，第%d列\n",Row+1,Lie+1);
      return (dian);
   }
}
printf("没有鞍点\n");
return 0;
}
main()
{
  int a[M][N],i,j,x;
  printf("请输入一个三行三列的数组\n");
  for(i=0;i<M;i++)
for(j=0;j<N;j++)
   scanf("%d",&a[i][j]);
  x=andian(a);
  printf("%d\n",x);
}[/code:1]

sagaeon · 发表于 2004-12-8 11:00:08

1.如果楼主的对，也只能找到一个鞍点。因为你找到一个就返回了。
2.break跳出最小包围(smallest enclosing)的循环语句。就是里面那个for。
3.找鞍点：假如b[m][Lie]<dian,那就是说这个点不是最小值，那就绝对不会是鞍点，因此break。但如果一直到结束也找不到一个b[m][Lie]<dian，说明这个dian就是当前列最小值，就是鞍点。这句“一直到结束也找不到”就由 m==M　来判断。而如果中间有一点b[m][Lie]“>”dian，m就不会等于M（最后一行的行号）。

		自动登录	找回密码
密码			注册