实验名称：实验五　数组的程序设计
  班级        学号      姓名     
  实验地点        完成日期    成绩           
（一）实验目的
1．掌握一维和二维数组定义、赋值和使用方法；
2．掌握字符数组和字符串函数的用法；
3．掌握与数组有关的算法（特别是排序算法）。
（二）实验内容
1．Problem Description对于输入的n个整数，先进行升序排序，然后进行二分查。
Input测试数据有多组，每组测试数据的第一行是一个整数n(1<=n<=100)，第二行有n个各不相同的整数待排序，第三行是查询次数m(1<=m<=100)，第四行有m个整数待查。处理到文件
结束。
Output每组测试分2行输出，第一行是排序后的升序的结果，每个数据之间1个空格；第二行是查的结果，若到则输出排序后元素的位置（从1开始），否则输出0，每个数据之间1个空格。（8005）
2．Problem Description如果矩阵A中存在这样的一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个程序计算出矩阵A的马鞍点的值。
Input输入数据首先包含一个整数T，表示测试实例的个数，然后是T组测试数据。
每组测试数据首先是2个正整数m,n (1 <= m, n <= 100)，分别表示二维数组的行和列。然后是二维数组的信息，数据之间用空格分割，每个数组元素均为int型范围.
说明：为了方便起见，我们假设二维数组的元素各不相同。
Output对于每组测试数据, 输出马鞍点的值，若不存在鞍点，输出Impossible。（1208）
3．对给定的数据进行排序。每组测试数据的结构是：第一行为一个整数N （0<N<100），表示后面有N个整数(每个整数最多可达80位)需要排序输出，先按长度排（短的在前），如长度一样则按大小排（小的在前）。若遇到N等于零，则运行结束。每组结果之间留一个空行。（1154）
（三）实验具体步骤
1．Problem Description对于输入的n个整数，先进行升序排序，然后进行二分查。
Input测试数据有多组，每组测试数据的第一行是一个整数n(1<=n<=100)，第二行有n个各不相同的整数待排序，第三行是查询次数m(1<=m<=100)，第四行有m个整数待查。处理到文件结束。
Output每组测试分2行输出，第一行是排序后的升序的结果，每个数据之间1个空格；第二行是查的结果，若到则输出排序后元素的位置（从1开始），否则输出0，每个数据之间1个空格。（8005）
解题思路：
首先，认真解读题目，该题首先是要用到排序，因为还要进行查二分查，所以就要有两个数组，设为a数组和b数组,即在a数组中查b数组里的元素，如果查到就输出该元素在a数组中的位置，查不到就输出零。在输入一个n时，由n控制a数组的元素个数，输入n个数，然后用对a数组进行升序排序。然后输入一个m,用来控制b数组的元素个数，然后是输入m个数到b数组，接下来就是要做二分查，将n个元素分成个数大致相同的两半，取a[mid]与欲查的b[i]作比较，如果b[i]< a[mid],则在a[mid]左边在进行二分查，否则就在a[i]的右边进行查。如果b[i]=a[mid]则到b[i];就.输出b[i]在数组a[i]里的下标(mid+1)，并退出循环。如果不到就输出0。
关键代码：
while(scanf("%d",&n)!=EOF)   
    {   
        for(i=0;i<n;i++)     
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++)
        {     
              for(j=0;j<n-i-1;j++)   
            {     
                if (a[j]>a[j+1])   
                {         
                    t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;   
                } 
            }
        }     
        for(i=0;i<n;i++)
        { 
            if (i>0)     
                printf(" "); 
            printf("%d",a[i]);
        }
        printf("\n");
        scanf("%d",&m);   
        for(i=0;i<m;i++)                 
        {         
            int t,mid;       
            scanf("%d",&t); 
            int s=0,e=n-1;           
            while(s<=e)                   
            {             
                mid=(s+e)/2;           
                if(a[mid]==t) break;             
                else if (t>a[mid]) s=mid+1;
                else e=mid-1;
            }             
            if(s>e) mid=-1;
            if(i>0)
                printf(" ");
            printf("%d",mid+1);       
        }   
        printf("\n");     
  }     
2．Problem Description如果矩阵A中存在这样的一个元素A[i][j]满足下列条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个程序计算出矩阵A的马鞍点的值。
Input输入数据首先包含一个整数T，表示测试实例的个数，然后是T组测试数据。
每组测试数据首先是2个正整数m,n (1 <= m, n <= 100)，分别表示二维数组的行和列。然后是二维数组的信息，数据之间用空格分割，每个数组元素均为int型范围.
说明：为了方便起见，我们假设二维数组的元素各不相同。
Output对于每组测试数据, 输出马鞍点的值，若不存在鞍点，输出Impossible。（1208）
解题思路：
首先是要定义一个二维数组,根据输入的m(行数),n（列数）,得到一个矩阵，然后先求第i行的最小元素，先设一个e=0为最小，然后再跟该行里的第j个元素去比较，如果到比e小的，就把j的值赋给e,当到最小的那个值时，因为还要判断该值是否是第j列中值最大的元素，所以需要先把此时的j的值临时赋给一个变量s;然后就让min去列中比较，遇到比min大的就结束循环，如果一直到最后都没有遇到比min大的，就说明min此时是最大的，也就是说，它就是要的鞍马点，然后输出a[s][e]，否则就说明不到鞍马点，输出Impossible。因为要进行循环，所以要增加一个标签f，赋初值为0；当到鞍马点是f=1;否则f=0;根据它来输出不存在的情况。
关键代码：
for(b=0;b<T;b++)
    {
        scanf("%d %d",&m,&n);
        for(x=0;x<m;x++)
        {
            for(y=0;y<n;y++)
                scanf("%d",&a[x][y]);
        }
        int f=0; 
        for(i=0;i<m;i++) 
        {
            g=m; 
            e=0; 
            s=i; 
            for(j=0;j<n;j++)  //查一行中的最小值
            { 
                if(a[s][e]>a[s][j]) e=j; 
            }   
            for(d=0;d<m;d++)  //查一列中的最大值
            { 
                if(a[d][e]>a[s][e]) break; 
                else g=g-1; 
            } 
            if(g==0) 
            { 
                printf("%d\n",a[s][e]); 
                f=1; 
            } 
        } 
        if(g!=0&&f==0)
            printf("Impossible\n"); 
    }
3．对给定的数据进行排序。每组测试数据的结构是：第一行为一个整数N （0<N<100），表示后面有N个整数(每个整数最多可达80位)需要排序输出，先按长度排（短的在前），如
长度一样则按大小排（小的在前）。若遇到N等于零，则运行结束。每组结果之间留一个空行。（1154二维字符串数组怎么定义）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。