C 语言答疑-02

By Von Brank | 2020/11/07 | Audience: 120L0213

集成开发环境（IDE）, 在线评测系统的(Online Judge)的推荐与使用

IDE
- Dev-Cpp
- Visual Studio Code
OJ
- www.luogu.com.cn
- leetcode-cn.com
算法可视化
- visualgo.net/zh

知识点梳理

数组

数组能够解决的基本问题

给出 $N$ 个数，计算它们的平均数

#include <stdio.h>
int main()
{
    int n, sum = 0, x;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &x);
        sum += x;
    }
    printf("%lf", (double)sum / n);
    return 0;
}

注意到不需要记录每一个输入的数

给出 $N$ 个数（ $N \le 100$ ），输出所有大于平均数的数

#include <stdio.h>
const int maxn = 105;
int main()
{
    int n, sum = 0;
    int a[maxn]; //定义数组
    double avg;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]); //读入数组
        sum += a[i];
    }
    avg = (double)sum / n;
    for(int i=1; i<=n; i++) //遍历数组
    {
		if(a[i] > avg) printf("%d ", a[i]); //输出数组元素
    }
    return 0;
}

要记录很多数字，需要使用数组存储

数组的定义

/*
 * 一维数组
 */
<变量类型> <变量名称>[元素数量];

int numbers[100];
double numberss[100];
for(int i=1; i<=n; i++)
	scanf("%d", numbers[i]);
/*
 * 二维数组
 */
<变量类型> <变量名称>[第一维长度][第二维长度];

int numbers[100][100];

元素数量必须是整数
C99 标准之前，定义数组时元素数量应是常量或用宏定义实现
C99 标准之后，在函数定义数组时元素的数量可以是变量，但全局变量数组定义的元素数量仍只能使用宏定义

数组的集成初始化

一维数组

int a[1050] = {0, 1, 1, 2, 3, 5, 8, 13,};

int a[] = {0, 1, 1, 2, 3, 5, 8, 13,};

int a[1050] = { [1] = 1, 1, 2, 3, 5, 8, 13,};

二维数组

int a[105][105] =
{
    {0, 1, 1, 2, 3, 5, 8, 13,},
    {0, 1, 2, 4, 8, 16, 32, 64,},
};
int b[][4] =
{
    {0, 1, 2, 3,},
    {0, 2, 4, 6,},
};

二维数组第二维长度必须被定义

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

以下定义方式在 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;
}

数组的赋值

错误示范

1
2
3

int a[1050] = {0, 1, 2, 3, 4, 5,};
int b[1050];
b = a;

正确示范

int a[1050] = {0, 1, 2, 3, 4, 5,};
int b[1050];
for(int i=0; i<=5; i++)
    b[i] = a[i];

数组的遍历

将数组从头至尾验视一次
一般使用for循环进行数组遍历

一些遍历数组的例子

数组的遍历赋值

1 2	for(int i=1; i<=n; i++) b[i] = a[i];

数组的遍历初始化
1
2
for(int i=1; i<=n; i++)
a[i] = 0;

遍历数组查找元素

for(int i=1; i<=n; i++)
{
    if(key == a[i])
    {
        ans = i;
        break;
    }
}

输出比平均值大的数

for(int i=1; i<=n; i++)
{
    if(a[i] > avg)
    {
        printf("%d ", a[i]);
    }
}

输出数组中所有值

for(int i=1; i<=n; i++)
{
    printf("%d ", a[i]);
}

数组作为函数的参数

对于一维数组，不能在[]中给出数组的大小
无法再利用sizeof()函数给出数组的大小

往往需要再传入一个变量来描述数组大小

int search(int key, int a[], int len)
{
    int ans = -1;
    for(int i=1; i<=len; i++)
    {
        if(a[i] == key)
        {
            ans = i;
            break;
        }
    }
    return ans;
}

字符串简介

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()将一个字符串拷贝到另一个字符串的后面，连成一个长的字符串

数组其他注意事项

数组是一种容器，有如下特点：
- 一个数组中所有元素类型相同
- 数组一旦定义，不能改变大小
- 任意维度的数组在内存中的排列是连续的
数组中的每一个单元是数组类型的一个变量，使用数组时[]中的数字称为下标或索引，下标从 $0$ 开始计数
一个拥有 $n$ 个元素的数组，下标的范围是 $[0, n-1]$ ，以大于等于 $n$ 的下标访问数组可能会造成数组越界导致程序崩溃，但是编译器在编译时并不会检查数组是否越界，因此务必保证程序只使用有效下标访问数组

创建数组时，应给予冗余的数组元素个数，如

#include <cstdio>
const int maxn = 1050; //对于1e3的数据范围，给予额外50个元素
int main()
{
    int n;
    int a[maxn];
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    return 0;
}

~~因数组越界而扣分所造成的损失比计算机内部多几个int所造成的内存消耗严重得多（~~

数组的应用

洛谷 P5737 【深基 7.例 3】闰年展示

输入 $x,y(1582\le x < y \le 3000)$ ，输出$[x,y] $区间中闰年个数，并在下一行输出所有闰年年份数字，使用空格隔开。

不使用数组

#include <stdio.h>

int main()
{
	int x, y, cnt = 0;
	scanf("%d %d", &x, &y);
	for(int i=x; i<=y; i++)
	{
		if(i % 4 == 0 && !(i % 100 == 0 && i % 400 != 0))
		{
			cnt++;
		}
	}
	printf("%d\n", cnt);
	for(int i=x; i<=y; i++) //需要做两遍计算
	{
		if(i % 4 == 0 && !(i % 100 == 0 && i % 400 != 0))
		{
			printf("%d ", i);
		}
	}
	return 0;
}

使用数组

#include <stdio.h>

int main()
{
	int x, y, cnt = 0;
    int leapYear[1050];
	scanf("%d %d", &x, &y);
	for(int i=x; i<=y; i++)
	{
		if(i % 4 == 0 && !(i % 100 == 0 && i % 400 != 0))
		{
			leapYear[++cnt] = i;
		}
	}
	printf("%d\n", cnt);
	for(int i=1; i<=cnt; i++)
    {
        printf("%d", leapYear[i]);
    }
	return 0;
}

洛谷 P1255 数楼梯

楼梯有 $N(N \leq 50 )^*$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

不使用数组

#include <stdio.h>
long long Fib(int n)
{
	if(n == 0 || n == 1) return 1;
	return Fib(n-1) + Fib(n-2);
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", Fib(n));
	return 0;
}

运行结果：

使用数组

#include <stdio.h>
const int maxn = 10050;
int main()
{
	int n;
    long long a[maxn];
	scanf("%d", &n);
	a[0] = 0;
    a[1] = 1;
    for(int i=2; i<=n; i++)
        a[i] = a[i-1] + a[i-2];
    printf("%lld", a[n]);
	return 0;
}

*运行结果：AC!!! :)

洛谷 P1464 Function

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

如果 $a \le 0\quad or\quad b \le 0 \quad or\quad c \le 0$ 就返回值 $11$
如果 $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!!! :)

C 语言庶事

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

没什么目的，只是为了方便计算

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

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

各数据类型的输入输出

	数据类型
`%d`	`int`
`%u`	`unsigned int`
`%lld`	`long long`
`%llu`	`unsigned long long`

浮点数

令人头疼的精度问题

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

C 语言程序设计其他注意事项

不要把SSE当成IDE
C 语言上机测试提交前一定要在本地编译通过并用样例数据测试
循环变量使用 $i, j, k$

int a, tmp;
for(a = 1, tmp = 0; a <= n; a++) //错误示范
{
    ...
    ...
}

int i;
int tmp = 0;
for(i = 1; i <= n; i++) //正确示范
{
    ...
    ...
}

遵循 C 语言标准代码规范

运算符两端空格
1
2
3
int a=b+1; //错误示范

int a = b + 1; //正确示范
~~当然，嫌for循环内空格太多也可以不遵循本条~~

采用缩进风格

if(n == 0) //错误示范
{
a = b + 1;
b ++;
}

if(n == 0)  //正确示范
{
    a = b + 1;
    b ++;
}

避免把多行语句写在同一行

int a = b + 1; b++;  //错误示范

int a = b + 1;  //正确示范
b++;

几道题

洛谷 P1177 【模板】快速排序

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

对于 $100\%$ 的数据， $N \leq 10^5$

相亲数

输入一个数 $n$ ，输出 $[0, n]$ 范围内每一对相亲数

注：相亲数指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等

洛谷 P3383 【模板】线性筛素数

给定一个范围 $n$ ，有 $q$ 个询问，每次输出区间 $[0, n]$ 范围内第 $k$ 小的素数。

对于 $100\%$ 的数据， $n \leq 10^8$ ， $q \leq 10^6$ ，保证输入合法

洛谷 P1706 全排列问题

输入一个数 $n$ 输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输出的所有排列按字典序排序

对于 $100\%$ 的数据， $1 \leq n \leq 9$

C语言答疑-02

C 语言答疑-02

目录

集成开发环境（IDE）, 在线评测系统的(Online Judge)的推荐与使用

知识点梳理

数组

数组能够解决的基本问题

数组的定义

数组的集成初始化

数组的赋值

数组的遍历

数组作为函数的参数

字符串简介

ASCII 码表

字符串的定义与初始化

字符串的输入与输出

常用字符串函数

数组其他注意事项

数组的应用

洛谷 P5737 【深基 7.例 3】闰年展示

洛谷 P1255 数楼梯

洛谷 P1464 Function

C 语言庶事

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

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

各数据类型的输入输出

浮点数

C 语言程序设计其他注意事项

几道题

洛谷 P1177 【模板】快速排序

相亲数

洛谷 P3383 【模板】线性筛素数

洛谷 P1706 全排列问题