C 语言答疑-03#

ASCII 码表#

• tool.ip138.com/ascii_code

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

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

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

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

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

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

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

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

字符串的定义与初始化#

char s[100];

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

字符串的输入与输出#

• %s会将当前位置与下一个空格或回车之间的字符串赋值给字符串s

char s[100];
scanf("%s", s);
printf("%s", s);

• 上述写法中，scanf会将输入字符串的首位赋值给s[0]
• 每个字符串都以'\0'结尾

常用字符串函数#

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

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

以下定义方式在 C 语言中可以通过编译

#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++中可以

#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;
}

记忆化搜索#

洛谷 P1464 Function

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

• 如果$a \le 0\quad or\quad b \le 0 \quad or\quad c \le 0$就返回值$1$
• 如果$a>20\quad or\quad b>20\quad or\quad c>20\quad$就返回$w(20,20,20)$
• 如果$a<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)$

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

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

• 不使用数组

  #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;
  }

  运行结果：

  

• 使用数组（记忆化）

  #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!!! :)

最长上升子序列#

给出一个序列$a_1, a_2, a_3, ... a_n$，找出其中最长的子序列$a_{t_1}, a_{t_2}, a_{t_3}, ...a_{t_m} (1 \leq t_i \leq n)$，满足$a_{t_i} < a_{t_{i+1}}$

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;
}

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

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

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

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

各数据类型的输入输出#

• 整数类型的输入输出

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

  • 二进制

    • 二进制数以0b或OB开头，只能包含0和1两个数
    • 标准 C 语言不支持该二进制写法，只有某些编译器支持

    //合法的二进制
    int a = 0b101;  //换算成十进制为 5
    int b = -0b110010;  //换算成十进制为 -50
    int c = 0B100001;  //换算成十进制为 33
    //非法的二进制
    int m = 101010;  //无前缀 0B，相当于十进制
    int n = 0B410;  //4不是有效的二进制数字

  • 八进制

    • 使用时以0开头，只能包含0~7这八个数

    //合法的八进制数
    int a = 015;  //换算成十进制为 13
    int b = -0101;  //换算成十进制为 -65
    int c = 0177777;  //换算成十进制为 65535
    //非法的八进制
    int m = 256;  //无前缀 0，相当于十进制
    int n = 03A2;  //A不是有效的八进制数字

  • 十六进制

    • 以0x或0X开头

    //合法的十六进制
    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大写，表明以大写字母的形式输出十六进制数。

浮点数#

• 令人头疼的精度问题

  #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

  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
  相比较
  
  二者不同

• 解决方案

  #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	编译后的目标文件

  • 一步编译：

    gcc hello.c -o demo

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

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

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

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

• 1.h的编写

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

• 算数表达式

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

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

  思考：下列程序的输出值

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

• 关系表达式

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

  int n;
  scanf("%d", &n);
  switch(n)
  {
      case 3 || 4:
          printf("YES!!!");
          break;
      case 5 || 6:
          printf("NO!!!");
          break;
      default:
          printf("No idea.");
          break;
  }

  考虑下列语句的含义

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

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

  如：

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

• 逻辑表达式

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

  int abs(int x)
  {
      if(x < 0) return -x;
      else return x;
  }

  int abs(int x)
  {
      return x < 0 ? -x : x;
  }

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

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