《算法笔记》2.4小节——C/C++快速入门->数组

问题 A: 习题6-4 有序插入

题目

题目描述

有一个已排好序的数组，要求输入一个数后，按原来排序的规律将它插入到数组中。

假设数组长度为 10，数组中前 9 个数（这 9 个数要求从键盘上输入，输入时要满足自小到大的输入顺序）已经按从小到大进行排序。

然后再从键盘上输入一个整数，将此整数插入到前有序的 9 个数中，使得最终的 10 个数依然是从小到大有序的。

输入

第一行输入以空格分隔的 9 个整数数，要求按从小到大的顺序输入。

第二行输入一个整数

输出

从小到大输出这 10 个数，每个数一行。

样例输入

1
2
1 11 21 31 41 51 61 71 81
45

样例输出

1
2
3
4
5
6
7
8
9
10
1
11
21
31
41
45
51
61
71
81

提示

定义数组时，把数组长度定义为 10.

题解

思路

思路就是先定位到插入的地方，然后大于要插入的数依次后移，然后将被插入的数插入即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    long long in[10];
    for (int i = 0; i < 9; i++)
    {
        scanf("%lld ", &in[i]);
    }
    long long n;
    scanf("%lld", &n);
    for (int i = 0; i < 10; i++)
    {
        // 定位插入的位置
        if (in[i] >= n)
        {
            // 依次后移
            for (int j = 9; j > i; j--)
            {
                in[j] = in[j - 1];
            }
            // 插入
            in[i] = n;
            break;
        }
    }
    for (int i = 0; i < 10; i++)
    {
        printf("%lld\n", in[i]);
    }

    system("pause");
    return 0;
}

问题 B: 习题6-5 数组元素逆置

题目

题目描述

将一个长度为 10 的整型数组中的值按逆序重新存放。

如：原来的顺序为 1，2，3，4，5，6，7，8，9，0，要求改为 0，9，8，7，6，5，4，3，2，1

输入

从键盘上输入以空格分隔的 10 个整数。

输出

按相反的顺序输出这 10 个数，每个数占一行。

样例输入

1
1 2 3 4 5 6 7 8 9 0

样例输出

1
2
3
4
5
6
7
8
9
10
0
9
8
7
6
5
4
3
2
1

题解

思路

思路比较简单，首尾交换即可，直到中间位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[10];
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < 5; i++)
    {
        swap(a[i], a[9 - i]);
    }
    for (int i = 0; i < 10; i++)
    {
        printf("%d\n", a[i]);
    }

    system("pause");
    return 0;
}

问题 C: 习题6-6 杨辉三角

题目

题目描述

按要求输入如下格式的杨辉三角

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

最多输出 10 层

输入

输入只包含一个正整数 n，表示将要输出的杨辉三角的层数。

输出

对应于该输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开

样例输入

1
5

样例输出

1
2
3
4
5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

题解

思路

思路也确实比较清晰，首先可以初始化一下前两行，因为前两行不适用公式；接下来就是公式化的东西：

  • j == 0与i == j

代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[100][100], n = 0;
    scanf("%d", &n);
    // 初始化
    a[0][0] = 1, a[1][0] = 1, a[1][1] = 1;
    // 获得杨辉三角形
    for (int i = 2; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
            }
            else
            {
                a[i][j] = 1;
            }
        }
    }
    // 输出杨辉三角形
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            printf("%d", a[i][j]);
            // 输出空格
            if (i != j)
            {
                printf(" ");
            }
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int n;
		// Java新建多维数组：
		// type[][] name = new type[sizeA][sizeB];
		int[][] a = new int[100][100];
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		a[0][0] = 1;
		a[1][0] = 1;
		a[1][1] = 1;
		// Java中一定要注意数组的越界问题
		for (int i = 2; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i) {
					a[i][j] = 1;

				} else {
					a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				System.out.print(a[i][j]);
				if (i != j) {
					System.out.print(' ');
				}
			}
			System.out.print('\n');
		}
	}
}

问题 D: 习题6-12 解密

题目

题目描述

有一行电文，已按如下规律译成密码：

A-->Z a-->z

B-->Y b-->y

C-->X c-->x

...... ......

即第一个字母变成第26个字母，第i个字母变成第（ 26-i+1 ）个字母，非字母字符不变。要求根据密码译回原文，并输出。

输入

输入一行密文

输出

解密后的原文，单独占一行。

样例输入

1
ZYX123zyx

样例输出

1
ABC123abc

题解

思路

可以创建一个英文字母数组，大小写均可，然后利用 ±32 获得另一个数组即可。

对于字符转换的处理就是 C[25 - ((int)in[i] - 65)]，先将输入的字符根据大小写减去 65 或 97，然后转换成int型，就找到了在我们创建的数组的下标，然后再转换成相应的字符就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    char C[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char in[100];
    scanf("%s", in);
    int count = strlen(in);
    for (int i = 0; i < count; i++)
    {
        if (in[i] >= 'A' && in[i] <= 'Z')
        {
            printf("%c", C[25 - ((int)in[i] - 65)]);
        }
        else if (in[i] >= 'a' && in[i] <= 'z')
        {
            printf("%c", C[25 - ((int)in[i] - 97)] + 32);
        }
        else
        {
            printf("%c", in[i]);
        }
    }
    printf("\n");

    system("pause");
    return 0;
}

问题 E: 习题6-13 字符串比较

题目

题目描述

比较两个字符串 s1 和 s2 的大小，如果 s1>s2，则输出一个正数；若 s1=s2，则输出 0；若 s1 < s2，则输出一个负数。

要求：不用 strcpy 函数；两个字符串用 gets 函数读入。

例如："A" 与 "C" 相比，由于 "A"<"C"，应输出负数，同时由于 "A" 与 "C" 的 ASCII 码差值为 2，因此应输出 "-2"。

同理："And" 和 "Aid" 比较，根据第 2 个字符比较的结果，"n" 比 "i" 大 5，因此应该输出 "5"

输入

输入 2 行字符串

输出

一个整数，表示这两个字符串 比较的差值，单独占一行。

样例输入

1
2
And
Aid

样例输出

1
5

题解

思路

由于使用getchar()，因此输入就简单很多了，直接gets(s1)即可。可是莫名报错，建议改成cin.getline(s1)，接下来就是判断了，从头到尾，如果出现不一样的字符，那么输出结果就好了，循环的话，以短字符串长度为基准就好，因为该题应该不会出现变长而且相等的字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    char s1[100], s2[100];
    // 在Codeup上报错，建议使用cin.getline(s1, 100)
    cin.getline(s1, 100);
    cin.getline(s2, 100);
    int len = strlen(s1) >= strlen(s2) ? strlen(s2) : strlen(s1);
    for (int i = 0; i < len; i++)
    {
        if (s1[i] != s2[i])
        {
            printf("%d\n", s1[i] - s2[i]);
            break;
        }
    }

    system("pause");
    return 0;
}

问题 F: 例题6-1 逆序输出数组元素

题目

题目描述

从键盘上输入 10 个整数，存储在一个长度为 10 的整型数组中，要求将输入的 10 个数逆序输出。

如输入为：0，1，2，3，4，5，6，7，8，9 输出为 9，8，7，6，5，4，3，2，1，0

输入

10 个整数，以空格分隔

输出

将输入的 10 个整数逆序输出，每个数占一行。

样例输入

1
0 1 2 3 4 5 6 7 8 9

样例输出

1
2
3
4
5
6
7
8
9
10
9
8
7
6
5
4
3
2
1
0

题解

思路

与上面一题思路一致。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[10];
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < 5; i++)
    {
        swap(a[i], a[9 - i]);
    }
    for (int i = 0; i < 10; i++)
    {
        printf("%d\n", a[i]);
    }

    system("pause");
    return 0;
}

问题 G: 例题6-2 数组求解Fibonacci数列问题

题目

题目描述

Fibonacci 数列的特点：第 1，2 个数为 1，1。从第 3 个数开始，概述是前面两个数之和。即：

要求输出 Fibonacci 数列的前20个数。

输入

无

输出

Fibonacci 数列的前 20 个数，每个数占一行。

样例输入

1
无

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

题解

思路

orz 我看成杨辉三角了，zz......根据定义来即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[20];
    a[0] = 1, a[1] = 1;
    for (int i = 2; i < 20; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
    for (int i = 0; i < 20; i++)
    {

        printf("%d\n", a[i]);
    }

    system("pause");
    return 0;
}

问题 H: 例题6-3 冒泡排序

题目

题目描述

从键盘上输入 10 个整数，用冒泡法对这 10 个数进行排序（由小到大）。

输入

以空格分隔的 10 个整数

输出

依次输出排好序的 10 个整数，每个数占一行。

样例输入

1
1 3 5 7 9 2 4 6 8 0

样例输出

1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9

题解

思路

需要注意的是冒泡排序。

冒泡排序

变量i控制循环次数，变量j用来比较交换，交换a[j]与a[j + 1]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[10];
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i < 10; i++)
    {
        for (int j = 0; j < 10 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                swap(a[j], a[j + 1]);
            }
        }
    }
    for (int i = 0; i < 10; i++)
    {
        printf("%d\n", a[i]);
    }


    system("pause");
    return 0;
}

问题 I: 例题6-4 矩阵转置

题目

题目描述

将一个 2 行 3 列的矩阵（二维数组）行列互换，存储到另一个 3 行 2 列的矩阵中。

要求以整型数据为例来解答。

输入

输入 2 行数据，每行 3 个整数，以空格分隔。

输出

行列互换后的矩阵，3 行，每行 2 个数据，以空格分隔。

样例输入

1
2
1 2 3
4 5 6

样例输出

1
2
3
1 4
2 5
3 6

题解

思路

a[i][j]变成a[j][i]即可，相应的，行的 2 变成列的 3，列的 3 变成行的 2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

int main()
{
    int a[2][3];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (j != 2)
            {
                printf("%d ", a[j][i]);
            }
            else
            {
                printf("%d", a[j][i]);
            }
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

问题 J: 例题6-9 字符串求最大值

题目

题目描述

从键盘上输入 3 个字符串，求出其中最大者。

输入

输入 3 行，每行均为一个字符串。

输出

一行，输入三个字符串中最大者。

样例输入

1
2
3
England
China
America

样例输出

1
England

题解

思路

使用三个变量比较好，不然不太方便输出。

三目运算符可以嵌套，一行就解决啦。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    char str1[100], str2[100], str3[100];
    cin.getline(str1, 100);
    cin.getline(str2, 100);
    cin.getline(str3, 100);
    strcmp(str1, str2) > 0 ? (strcmp(str1, str3) > 0 ? printf("%s", str1) : printf("%s", str3)) : (strcmp(str2, str3) > 0 ? printf("%s", str2) : printf("%s", str3));

    system("pause");
    return 0;
}
#算法 #算法笔记
《算法笔记》2.4小节——C/C++快速入门->数组
https://excelius.xyz/《算法笔记》2-4小节——c-c-快速入门-数组/
作者
Ther
发布于
2021年11月1日
许可协议