找马鞍点！ - 编程论坛

#2

诸葛修勤2011-04-17 11:59

找马鞍点

什么意思这句话？

#3

王一南2011-04-17 12:49

回复 2楼诸葛修勤

就是想找马鞍点，结果运行不出来结果，希望给小弟解决哈！
感觉for循环关系理得不是很清楚!

[ 本帖最后由王一南于 2011-4-17 12:51 编辑 ]

#4

pangding2011-04-17 13:43

狭义的鞍点是指矩阵中的一个元素，它拥有“在其所在列中，它是最小元素；而在其所在行里，它是最大元素”的性质。
楼主找的好像是行最小列最大。不过也没事，应该是差不多的意思。

矩阵的鞍点在搞对策博弈之类的问题时会经常用到。
方法一般是扫描每一行，把最大值记住。再在所有得到的最大值中找一个最小值。如果鞍点存在，好像一定是这个值，验证一下就行了。如果不是鞍点就说明这个矩阵没有鞍点。
如果是楼主说的那种“鞍点”，就用相反的找就行了。

我现在记的也不是很清楚，说的算法可能不对。有兴趣的自己找找资料呗。

#5

诸葛修勤2011-04-17 15:58

程序代码：

/*
鞍点
*/
#include <stdio.h>

#define M 100
#define N 100

struct node
{
    int col;//
    int row;//
};

int array[M][N] = {0};
int p = 0;//行
int q = 0;//列

void init_array()
{
    int i,j;

    printf("请输入您想输入的矩阵的行数和列数：\n");
    scanf("%d %d",&p,&q);
    printf("请按行输入矩阵(%d行%d列)：\n",p,q);
    for(i=0;i<p;i++)
    {
        for(j=0;j<q;j++)
        {
            scanf("%d",&array[i][j]);
        }
    }
}

//找出行数为row中最小数的下标值
int search(int row)
{
    int index = 0;
    int recode = 0;

    for (; index < q; ++index)
    {
        if ( array[row][recode] > array[row][index] )
        {
            recode = index;
        }
    }

    return recode;
}

//判断下标index在col列中是否为最大是返回true
bool is_col_max(int col, int index)
{
    int i = 0;

    for (; i<p; ++i)
    {
        if ( i != index && array[index][col] <= array[i][col] )
        {
            return false;
        }
    }

    return true;
}

void deal()
{
    int sum_row = 0;//待处理的总行数计数器

    if ( p != sum_row )
    {
        ++sum_row;
    }
    else
    {
        return;
    }

    struct node index, temp;

    index.row = sum_row - 1;
    index.col = search(sum_row-1);//找出最小值的下标 sum_row行中

    while (p != sum_row)
    {
        ++sum_row;
        if ( array[index.row][index.col] > array[sum_row-1][index.col] )
        {//如果满足在列数上保持最大值的记录则不更改马鞍点
        }
        else
        {
            temp.row = sum_row - 1;
            temp.col = search(temp.row);

            if (temp.col == index.col)
            {//更改马鞍点
                index = temp;
            }
            else
            {
                if (is_col_max(temp.col, temp.row))
                {//更改马鞍点
                    index = temp;
                }
                else
                {//暂时没有满足条件的马鞍点
                    index.col = -1;//表示没有满足的

                    if ( p != sum_row )
                    {
                        ++sum_row;
                    }
                    else
                    {
                        break;
                    }

                    index.row = sum_row - 1;
                    index.col = search(sum_row-1);
                }
            }
        }
    }
    if ( index.col == -1 )
    {
        printf("\t您输入的矩阵无马鞍点！\n");
    }
    else
    {
        if ( is_col_max(index.col, index.row) )
        {
            printf("\t%d\n", array[index.row][index.col]);
        }
        else
        {
            printf("\t您输入的矩阵无马鞍点！\n");
        }
    }

}

int main(void)
{
    init_array();

    deal();

    return 0;
}

#6

诸葛修勤2011-04-17 15:58

唉写的不成样子啦

#7

王一南2011-04-17 16:12

回复 6楼诸葛修勤

怎么写的这么多？不是写很少就可以吗？

#8

liuyangxi2012-03-28 21:51

#include<stdio.h>
#define M 100
#define N 100
void main()
{

    int i,j,k,p,q,temp,small;
    int a[M][N];
    printf("请输入您想输入的矩阵的行数和列数：\n");
    scanf("%d %d",&p,&q);
    printf("请按行输入矩阵(%d行%d列)：\n",p,q);
    for(i=0;i<p;i++)
    {
        for(j=0;j<q;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
      //temp=1;这个没用的
    for(i=0;i<p;i++)//控制换行
    {
        small=a[i][0];
        for(j=0;j<q;j++)
        {
            if(small>a[i][j])
                small=a[i][j];//记录最小数 8

            if(a[i][j]==small)//处理在i行中等于small的元素
            {
                for(k=0;k<p;k++)//从该列的第一个元素比较
                {
                    if(small<a[k][j])
                        temp=0;//small不是列最大
                    else//添加的else语句
                        temp=1                }
                if(temp==1)    //if 里的语句是==，您只写了=
                    printf("a[%d][%d]=%d是所输矩阵的马鞍点\n",i,j,small);//当循环正常结束时，则为马鞍点
            }

        }
    }
    if(temp==0) printf("您输入的矩阵无马鞍点！");//同上面得到if语句

    //初来乍到，有不对的地方请各位指教


}