EDUCoder编程实训题解（9.一维数组和二维数组）

丷欲丷

1.编辑与调试 　2.顺序结构　 3.选择结构一　4.选择结构二　 5.循环一 　6.循环二　 7.函数
8.递归与嵌套函数 　9.一维数组和二维数组 　10.字符数组 　11.指针一 　12.指针二 　13.结构体
14.文件
一维数组和二维数组

第1关：排序问题

任务描述
本关任务:将十个数进行从大到小的顺序进行排列。
输入
输入十个整数。
输出
以从大到小的顺序输出这个十个数。
测试说明
样例输入：
1 2 3 4 5 6 7 8 9 10
样例输出：
10 9 8 7 6 5 4 3 2 1
解题说明
功能封装到函数，实现程序复用。
解题程序
#include<stdio.h>

#define N 10
int a[N];

/* 从大到小的冒泡排序 */
void bubbleSort(int numbers[], int array_size)
{
  int i, j, temp;

  for (i = (array_size - 1); i > 0; i--)
    for (j = 1; j <= i; j++)
      if (numbers[j-1] < numbers[j]) {
        temp = numbers[j - 1];
        numbers[j - 1] = numbers[j];
        numbers[j] = temp;
      }
}

int main(void)
{
    /*********Begin*********/
    int i, j;

    for(i = 0; i < N; i++)
        scanf("%d", &a);
   
    /* 冒泡排序 */
    bubbleSort(a, N);

    for(i = 0; i < N; i++)
        printf("%d ", a);
    printf("\n");
    /*********End**********/
    return 0;
}

第2关：查找整数

任务描述
题目描述：给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。
输入
第一行包含一个整数n。
第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。
第三行包含一个整数a，为待查找的数。
输出
如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。
测试说明
样例输入：
6
1 9 4 8 3 9
9
样例输出：
2
数据规模与约定：
1 <= n <= 1000
解题程序
/* 第2关：查找整数 */

#include<stdio.h>

#define N 1000
int a[N];

int main(void)
{
    /*********Begin*********/
    int n, x, i;

    /* 读入数据 */
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &a);
    scanf("%d", &x);
   
    /* 查找数据 */
    for(i = 0; i < n; i++)
        if(a == x) break;

    printf("%d\n", i == n ? -1 : i + 1);   
    /*********End**********/
    return 0;
}

第3关：计算数组中元素的最大值及其所在的行列下标值

任务描述
题目描述:按如下函数原型编程从键盘输入一个m行n列的二维数组，然后计算数组中元素的最大值及其所在的行列下标值。其中m和n的值由用户键盘输入。已知m和n的值都不超过10。
输入
输入数组大小：“%d,%d”
下面输入数组中元素。
输出
输出格式：
数组大小输入提示信息：“Input m, n:”
数组元素输入提示信息："Input %d*%d array: "
输出格式：“max=%d, row=%d, col=%d”
样例输入
5,5
1 2 3 4 5
4 5 6 100 2
3 2 1 5 6
1 2 3 5 4
3 5 6 4 8
样例输出
Input m, n:Input 5*5 array:
max=100, row=2, col=4
解题程序
/* 第3关：计算数组中元素的最大值及其所在的行列下标值 */

#include<stdio.h>

#define N 1000
int a[N][N];

int main(void)
{
    /*********Begin*********/
    int m, n, i, j;

    /* 读入数据 */
    printf("Input m, n:");
    scanf("%d,%d", &m, &n);
    printf("Input %d*%d array:\n", m, n);
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &a[j]);

    int maxa = a[0][0], row = 0, col = 0;
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(a[j] > maxa) maxa = a[j], row = i, col = j;

    printf("max=%d, row=%d, col=%d\n", maxa, row + 1, col + 1);
   
    /*********End**********/
    return 0;
}

第4关：二分查找

任务描述
题目描述:将n个从小到大排序的整数（n<1000000）从1~n进行编号，并一个待查找的整数m，请使用二分法进行查找。
输入
输入包括3行，第一行为整数n，第二行包括n个整数，以空格分隔，第三行为整数m。
输出
如果能够在序列中找到整数m，则输出编号（如果存在多个编号，返回编号最小的），如果不存在，则输出None。
测试说明
样例输入：
10
1 2 4 5 6 7 8 9 10 11
10
样例输出：
9
解题程序
/* 第4关：二分查找 */

#include<stdio.h>

#define N 100
int a[N];

int main(void)
{
    /*********Begin*********/
    int n, x, i, j, mid;

    /* 读入数据 */
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &a);
    scanf("%d", &x);

    /* 二分查找 */
    int ans = -1;
    i = 0, j = n - 1;
    while(i <= j) {
        mid = (i + j) / 2;
        if(a[mid] == x) {
            ans = mid;
            break;
        } else if(a[mid] > x)
            j = mid - 1;
        else if(a[mid] < x)
            i = mid + 1;
    }

    if(ans == -1)
        printf("None\n");
    else
        printf("%d\n", ans + 1);
    /*********End**********/
    return 0;
}

第5关：鞍点

任务描述
题目描述:找出具有m行n列二维数组Array的“鞍点”，即该位置上的元素在该行上最大，在该列上最小，其中1<=m,n<=10。
输入
输入数据有多行，第一行有两个数m和n，下面有m行，每行有n个数。
输出
按下列格式输出鞍点：
Array[j]=x
其中x代表鞍点，i和j为鞍点所在的数组行和列下标，我们规定数组下标从0开始。
一个二维数组并不一定存在鞍点，此时请输出None
我们保证不会出现两个鞍点的情况，比如：
3 3
1 2 3
1 2 3
3 6 8
样例输入：
3 3
1 2 3
4 5 6
7 8 9
样例输出：
Array[0][2]=3
解题程序
/* 第5关：鞍点 */

#include<stdio.h>

#define N 10
int a[N][N], maxa[N], mina[N];

int main(void)
{
    /*********Begin*********/
    int m, n, i, j;

    /* 读入数据 */
    scanf("%d %d", &m, &n);
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &a[j]);

    /* 初始化最值：行的最大值、列的最小值 */
    for(i = 0; i < m; i++)
        maxa = a[0];
    for(i = 0; i < n; i++)
        mina = a[0];

    /* 计算最值：行的最大值、列的最小值 */
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++) {
            if(a[j] > maxa)
                maxa = a[j];
            if(a[j] < mina[j])
                mina[j] = a[j];
        }

    /* 找鞍点并且输出结果 */
    int flag = 1;
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            if(maxa == mina[j]) {
                flag = 0;
                printf("Array[%d][%d]=%d\n", i, j, maxa);
                break;
            }
    if(flag)
        printf("None\n");
    /*********End**********/
    return 0;
}

第6关：删除最大值

任务描述
题目描述:输入10个互不相同的整数并保存在数组中，找到该最大元素并删除它，输出删除后的数组
输入
输入10个互不相同整数
输出
输出删除最大元素后的数组
样例输入：
1 2 3 4 5 6 7 8 9 0
样例输出：
1 2 3 4 5 6 7 8 0
解题说明
真正把数据删除，动作太多，计算量太大。做个标记即可，计算速度快。
解题程序
/* 第6关：删除最大值 */

#include<stdio.h>

#define N 10
int a[N];

int main(void)
{
    /*********Begin*********/
    int i;
    for(i = 0; i < N; i++)
        scanf("%d", &a);

    int maxa = a[0], k = 0;
    for(i = 1; i < N; i++)
        if(a > maxa) maxa = a, k = i;

    for(i = 0; i < N; i++)
        if(i != k)
            printf("%d ", a);
    printf("\n");
    /*********End**********/
    return 0;
}

第7关：杨辉三角

任务描述
题目描述：还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
测试说明
平台会对您的代码进行运行测试，如果实际输出与预期输出相同，则算通关。
输出
打印出杨辉三角图形的10行。格式见题目描述部分。每个整数后面接一个空格来分隔开整数
解题程序
/* 第7关：杨辉三角 */

#include<stdio.h>
#include<string.h>

#define N 10
int a[N + 1];

int main(void)
{
    /*********Begin*********/
    memset(a, 0, sizeof(a));
    a[1] = 1;

    int i, j;
    for(i = 1; i <= N; i++) {
        for(j = i; j >= 1; j--)
            a[j] += a[j - 1];
        
        printf("%d", a[1]);
        for(j = 2; j <= i; j++)
            printf(" %d", a[j]);
        printf("\n");
    }
    /*********End**********/
    return 0;
}

1.编辑与调试 　2.顺序结构 　3.选择结构一　 4.选择结构二　 5.循环一　 6.循环二　7.函数
8.递归与嵌套函数 　9.一维数组和二维数组 　10.字符数组 　11.指针一 　12.指针二 　13.结构体
14.文件

雨的前世

沙发？？？