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)

  • 如果a0orb0orc0a \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(a1,b,c)+w(a1,b1,c)+w(a1,b,c1)w(a1,b1,c1)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(1tin)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,2311][-2^{31}, 2^{31}-1]
  • unsigned int数据范围是[0,2321][0, 2^{32}-1]

各数据类型的输入输出

  • 整数类型的输入输出
数据类型
%d int
%u unsigned int
%lld long long
%llu unsigned long long
  • 二进制,八进制,十六进制的整数(引用自:c.biancheng.net/view/1759.html)

    • 二进制

      • 二进制数以0bOB开头,只能包含01两个数
      • 标准 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不是有效的八进制数字
    • 十六进制

      • 0x0X开头
      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 明明的随机数

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

洛谷 P1177 【模板】快速排序(朴素算法)

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

对于100%100\%的数据,N104N \leq 10^4

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

给出两个字符串 s1s_1s2s_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_2len1,len2104len_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

在上面的样例中,从 738757 \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$盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含 191 - 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