C 语言答疑-03

​ By Von Brank | 2020/11/12

目录

  • 网站推荐
  • 近期知识梳理
  • 几道题
  • 答疑
funny

网站推荐

知识点梳理

字符串简介

ASCII 码表

  • tool.ip138.com/ascii_code

  • char既是整数也是字符，取决于你怎么看它

    以下两个printf语句输出都是1

    1
    2
    printf("%c\n", 49);
    printf("%d\n", 1);

    以下两个printf语句输出都是49

    1
    2
    printf("%c\n", '1');
    printf("%d\n", 49);

    以"char的方式"看待49这个整数，它是字符1

    以"int的方式"看待1这个字符，他是整数49

  • '\n'，'\t'与空格

字符串的定义与初始化

1
2
3
char s[100];

char str[100] = "Hello World!!!";

字符串的输入与输出

  • %s会将当前位置与下一个空格或回车之间的字符串赋值给字符串s
1
2
3
char s[100];
scanf("%s", s);
printf("%s", s);
  • 上述写法中，scanf会将输入字符串的首位赋值给s[0]
  • 每个字符串都以'\0'结尾

常用字符串函数

  • 需要#include <string.h>
  • getchar()单字符输入，putchar()单字符输出
  • strlen()计算字符串长度
  • strcmp()比较两个字符串是否相同
  • strcpy()将一个字符串赋值给另一个字符串
  • strcat()将一个字符串拷贝到另一个字符串的后面，连成一个长的字符串

数组补充

将变量作为数组定义的元素数量，并作集成初始化的注意事项

以下定义方式在 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
#include <stdio.h>
#define maxn 100
int main()
{
    int a[maxn] = {0, 1, 2, 3,};
    return 0;
}

------------------------------

#include <stdio.h>
int main()
{
    int a[100] = {0, 1, 2, 3,};
    return 0;
}

------------------------------

#include <stdio.h>
int main()
{
    const int maxn = 100;
    int a[maxn] = {0, 1, 2, 3,};
    return 0;
}

------------------------------

#include <stdio.h>
int main()
{
    int maxn = 100;
    int a[maxn] = {0, 1, 2, 3,};
    return 0;
}

以下定义方式在 C 语言中无法通过编译，但是在 C++中可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
const int maxn = 100;
int main()
{
    int a[100] = {0, 1, 2, 3,};
    return 0;
}

-------------------------------

#include <stdio.h>
int main()
{
    const int maxn = 100;
    int a[100] = {0, 1, 2, 3,};
    return 0;
}

初识动态规划（DP）

记忆化搜索

洛谷 P1464 Function

对于一个递归函数w(a,b,c)w(a,b,c)

  • 如果a≤0orb≤0orc≤0a \le 0\quad or\quad b \le 0 \quad or\quad c \le 0就返回值11
  • 如果a>20orb>20orc>20a>20\quad or\quad b>20\quad or\quad c>20\quad就返回w(20,20,20)w(20,20,20)
  • 如果a<ba<b并且$b<c 就返回就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$
  • 其它的情况就返回w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)

这是个简单的递归函数，但实现起来可能会有些问题。当a,b,ca,b,c均为1515时，调用的次数将非常的多。你要想个办法才行.

对于一些特殊情况，比如 w(30,−1,0)w(30,-1,0)既满足条件11又满足条件22，这种时候我们就按最上面的条件来算，所以答案为11

  • 不使用数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <stdio.h>
    int w(int a, int b, int c)
    {
    	if(a <= 0 || b <= 0 || c <= 0) return 1;
    	else if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    	else if(a < b && b < c) return w(a, b, c-1) + w(a, b -1, c - 1) - w(a, b, c - 1);
    	else return w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1);
    }
    int main()
    {
    	int a, b, c;
    	while(1)
    	{
    		scanf("%d %d %d", &a, &b, &c);
    		if(a == -1 && b == -1 && c == -1)
    		{
    			break;
    		}
    		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    	}
    	return 0;
    }

    运行结果：

    BykPLd.png

  • 使用数组（记忆化）

    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
    #include <stdio.h>
    int vis[25][25][25];
    void init()
    {
        for(int i=0; i<=20; i++)
        {
            for(int j=0; j<=20; j++)
            {
    			for(int k=0; k<=20; k++)
                {
                    vis[i][j][k] = -1;
                }
            }
        }
    }
    int w(int a, int b, int c)
    {
        if(a <= 0 || b <= 0 || c <= 0)
    		a = b = c = 0;
        if(a > 20 || b > 20 || c > 20)
    		a = b = c = 20;
        if(vis[a][b][c] != -1) return vis[a][b][c];
    	else if(a <= 0 || b <= 0 || c <= 0) return vis[0][0][0] = 1;
    	else if(a < b && b < c) return vis[a][b][c] = w(a, b, c - 1) + w(a, b -1, c - 1) - w(a, b, c - 1);
    	else return vis[a][b][c] = w(a - 1, b, c) + w(a - 1,  b- 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }
    int main()
    {
    	int a, b, c;
    	while(1)
    	{
    		init(); //计算每组数据前要初始化数组
    		scanf("%d %d %d", &a, &b, &c);
    		if(a == -1 && b == -1 && c == -1)
    		{
    			break;
    		}
    		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
    	}
    	return 0;
    }

    运行结果：AC!!! :)

最长上升子序列

给出一个序列a1,a2,a3,...ana_1, a_2, a_3, ... a_n，找出其中最长的子序列at1,at2,at3,...atm(1≤ti≤n)a_{t_1}, a_{t_2}, a_{t_3}, ...a_{t_m} (1 \leq t_i \leq n)，满足ati<ati+1a_{t_i} < a_{t_{i+1}}

1
2
3
4
5
6
7
8
9
10
11
12
13
int a[MAXN], d[MAXN];
int dp() {
  d[1] = 1;
  int ans = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++)
      if (a[j] < a[i]) {
        d[i] = max(d[i], d[j] + 1);
        ans = max(ans, d[i]);
      }
  }
  return ans;
}

C 语言庶事

整数是怎么表达的——原码，反码，补码

  • 这些规定没什么别的目的，只是为了方便计算

各数据类型的表达范围与自然溢出

  • int类型有 32 位，表达范围为[−231,231−1][-2^{31}, 2^{31}-1]
  • unsigned int数据范围是[0,232−1][0, 2^{32}-1]

各数据类型的输入输出

  • 整数类型的输入输出
数据类型
%d int
%u unsigned int
%lld long long
%llu unsigned long long

  • 二进制，八进制，十六进制的整数（引用自：c.biancheng.net/view/1759.html）

    • 二进制

      • 二进制数以0b或OB开头，只能包含0和1两个数
      • 标准 C 语言不支持该二进制写法，只有某些编译器支持
      1
      2
      3
      4
      5
      6
      7
      //合法的二进制
      int a = 0b101;  //换算成十进制为 5
      int b = -0b110010;  //换算成十进制为 -50
      int c = 0B100001;  //换算成十进制为 33
      //非法的二进制
      int m = 101010;  //无前缀 0B，相当于十进制
      int n = 0B410;  //4不是有效的二进制数字

    • 八进制

      • 使用时以0开头，只能包含0~7这八个数
      1
      2
      3
      4
      5
      6
      7
      //合法的八进制数
      int a = 015;  //换算成十进制为 13
      int b = -0101;  //换算成十进制为 -65
      int c = 0177777;  //换算成十进制为 65535
      //非法的八进制
      int m = 256;  //无前缀 0，相当于十进制
      int n = 03A2;  //A不是有效的八进制数字

    • 十六进制

      • 以0x或0X开头
      1
      2
      3
      4
      5
      6
      7
      //合法的十六进制
      int a = 0X2A;  //换算成十进制为 42
      int b = -0XA0;  //换算成十进制为 -160
      int c = 0xffff;  //换算成十进制为 65535
      //非法的十六进制
      int m = 5A;  //没有前缀 0X，是一个无效数字
      int n = 0X3H;  //H不是有效的十六进制数字

    • 输入与输出

      short int long
      八进制 %ho %o %lo
      十进制 %hd %d %ld
      十六进制 %hx 或 %hX %x 或 %X %lx 或 %lX
      • %hx、%x 和 %lx 中的x小写，表明以小写字母的形式输出十六进制数
      • %hX、%X 和 %lX 中的X大写，表明以大写字母的形式输出十六进制数。

浮点数

  • 令人头疼的精度问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <stdio.h>

    int main()
    {
        if(1.1 + 0.1 == 1.2)
            printf("YES!!!");
        else
            printf("NO!!!");
        return 0;
    }

    以上程序输出的是NO

  • 1.1 + 0.1为什么不等于1.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
    0.1转化为二进制的结果是一个循环小数:
    0.00011001100110011001100110011001100110011001100110011010
    double类型在二进制下的精度是53位有效数字，超出部分四舍五入

    同理将1.1转化为二进制:
    1.0001100110011001100110011001100110011001100110011010

    二者相加
     	0.00011001100110011001100110011001100110011001100110011010
    +	1.0001100110011001100110011001100110011001100110011010
    ---------------------------------------------------------------
     	1.0011001100110011001100110011001100110011001100110100



    将结果转化为十进制：
    1.20000000000000018

    将1.2转化为二进制：
    1.0011001100110011001100110011001100110011001100110011

    与1.1+0.1的二进制结果:
    1.0011001100110011001100110011001100110011001100110100
    相比较

    二者不同

  • 解决方案

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <stdio.h>
    const double eps = 1e-6;
    double eps(double x)
    {
          return x < 0 ? -x : x;
    }
    int main()
    {
    	if((abs(1.1 + 0.1 - 1.2) < eps)
    		printf("YES!!!");
    	else
    		printf("NO!!!");
    	return 0;
      }

以"\"开头的字符

  • 格式控制字符串中的一类字符

    字符 意义
    \b 回退一格
    \t 转到下一个制表位
    \n 换行
    \r 回车
    \" 双引号
    \' 单引号
    \\ 反斜杠

  • 基本的文件读写

  • 思考：如何输出%d这个字符串本身

#include <stdio.h>是什么——头文件简介

  • 头文件是扩展名为 .h 的文件，包含了 C 函数声明和宏定义，被多个源文件中引用共享。有两种类型的头文件：程序员编写的头文件和编译器自带的头文件

  • gcc 的编译过程

    • 分步编译：

      • 预处理：gcc -E hello.c -o hello.i

      • 编 译： gcc -S hello.i -o hello.s

      • 汇 编：gcc -c hello.s -o hello.o

      • 链 接：gcc hello.o -o hello_elf

        选项 含义
        -E 只进行预处理
        -S大写 只进行预处理和编译
        -c小写 只进行预处理、编译和汇编
        -o file 指定生成的输出文件名为file
        文件后缀 含义
        .c C 语言文件
        .i 预处理后的 C 语言文件
        .s 编译后的汇编文件
        .o 编译后的目标文件

    • 一步编译：

      1
      gcc hello.c -o demo

      此指令依然经过：预处理、编译、汇编、链接的过程

  • 编译预处理指令——以#开头的指令

  • 在编译预处理中，编译器会将头文件中的所有内容原封不动地“抄”到.c文件中

  • 头文件内应只包含变量与的函数声名，不应包含变量与函数的定义

  • 1.h的编写

算术表达式，关系表达式与逻辑表达式

  • 算数表达式

    1
    2
    3
    4
    5
    6
    7
    a = a + b;
    b = b + 1

    a = a * +b;
    a = a * -b;

    a=b+=c++-d+--e/-f;

    优先级：(++i --i) > (* /) > (+ -) > (i++ i--) > (= += *= -= /= %=)

    思考：下列程序的输出值

    1
    2
    3
    int a = 0, b = 10, c = 8, d = 1, e = 1, f = 1;
    a=b+=c++-d+--e/-f;
    printf("%d", a);

  • 关系表达式

    考虑下列程序对于输入3的结果

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int n;
    scanf("%d", &n);
    switch(n)
    {
        case 3 || 4:
            printf("YES!!!");
            break;
        case 5 || 6:
            printf("NO!!!");
            break;
        default:
            printf("No idea.");
            break;
    }

    考虑下列语句的含义

    1
    2
    3
    4
    printf("%d", 5 > 3);
    printf("%d", 3 && 0);
    printf("%d", !0);
    a = 7 > 2 + 4;

    关系运算优先级：（算术运算）> (关系运算) > (赋值)

    如：

    1
    2
    3
    4
    5
    if(a * b + c > c / d -e)
    {
    printf(“hello world”);
    }
    int f = a * b + c > c / d –e;

  • 逻辑表达式

    下列两个函数实现的效果完全相同

    1
    2
    3
    4
    5
    int abs(int x)
    {
        if(x < 0) return -x;
        else return x;
    }
    1
    2
    3
    4
    int abs(int x)
    {
        return x < 0 ? -x : x;
    }

变量的作用域与递归函数的本质

  • 本地变量的作用域
  • 全局变量在定义时会自动初始化为 0，而本地变量不会，这意味着本地变量的初值是随机的，其取决于上一个使用这块内存的程序
  • 离开作用域的变量会被销毁
  • 递归的过程中究竟发生了什么？

C 语言程序设计上机测试其他注意事项

  • 不要把SSE当成IDE

  • C 语言上机测试提交前一定要在本地编译通过并用样例数据测试

  • 善用输出调试与单步调试

几道题

洛谷 P1059 明明的随机数

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了NN个11到10001000之间的随机整数(N≤100)(N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

洛谷 P1177 【模板】快速排序（朴素算法）

给出NN个数，将其从小到大排序.

对于100%100\%的数据，N≤104N \leq 10^4

洛谷 P3375 【模板】KMP 字符串匹配（朴素算法）

给出两个字符串 s1s_1 和 s2s_2，若 s1s_1 的区间 [l,r][l, r] 子串与$ s_2完全相同，则称完全相同，则称 s_2 在在 s_1 中出现了，其出现位置为中出现了，其出现位置为l$。
现在请你求出 s2s_2 在 $s_1 $中所有出现的位置。

对于100%100\%的数据，s1,s2s_1, s_2的长度为len1,len2len_1, len_2，len1,len2≤104len_1, len_2 \leq 10^4

洛谷 P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中，从 7→3→8→7→57 \to 3 \to 8 \to 7 \to 5 的路径产生了最大

洛谷 P1219 [USACO1.5]八皇后 Checker Challenge

一个如下的 6×66×6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

八皇后问题

上面的布局可以用序列2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5 来描述，第 ii 个数字表示在第ii行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 61\ 2\ 3\ 4\ 5\ 6

列号 2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33个解。最后一行是解的总个数。

输入样例#1

1
6

输出样例#2

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

P1784 数独【选做】（困难但有趣）

数独是根据$ 9 \times 9$盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 1−91 - 9 ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入一个一个未填的数独，输出一个填好的数独。

输入样例#1

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

输出样例#1

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