程序设计与算法（一）C语言程序设计-郭炜-笔记 （自用）_输入 输入只一行,有六个实数,用空格隔开。这六个数分别是第一个点的横坐标、第一

第一周

1.1 信息在计算机中的表示

字节换算：
1B=8b
1KB=1024B
1MB=1024KB
1GB=1024MB
1TB=1024GB

PS:B byte；b bit

进制转换
进制：2 B，8 O，10 D，16 H
K进制数到十进制数的转换：按权展开
十进制数到K进制数的转换：短除法
取余数 倒序
K进制小数：乘权去整数
取整数 正序
PS：有时会无法转换，例如 0.1D无法转换为二进制

一位十六进制数对应四位二进制数
1 1 1 1
8 4 2 1 ＝15
一位八进制数对应三位二进制数
1 1 1
4 2 1 ＝7

1.2 C++快速入门

C++程序

#include<iostream>
#include<cstdio>
using namespace std;
int main() {
	printf("第一个C++程序：\n");
	printf("Hello World!");
	printf("\n第二个C++程序：输出更多\n");
	int a = 3;
	printf("I have %d dollars.\n", a);
	printf("I want to buy:\na book.");
	printf("\n第三个C++程序：如何输入\n");
	int b,c;
	scanf("%d%d",&b,&c);
	printf("%d", b + c);

	//scanf对于回车、空格 不会赋给字符串，但会赋给字符。(知识点)
	//可以在输入之前用getchar()来获取回车的/n来避免将/n赋给字符
	printf("\n第四个C++程序：输入字符\n");
	char d, e, f;
	getchar();
	scanf("%c%c%c", &d, &e, &f);
	printf("%c%c%c", d, e, f);
	return 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

注释
单行注释：//
多行注释：/* */

1.3 变量和数据类型初探

使用形式
数据类型 变量名;

变量命名规则：字母/下划线 + 数字/字母/下划线
无法和关键字重合

数据类型

sizeof(变量名/类型名)：可以获取变量/类型占用的字节数
没有初始化的值，其值一般是不确定的。
可以自定义变量

1.4 变量和数据类型进阶

有符号整数(二进制)：最高位为符号位 0为正 1位负
正数：绝对值为其除去符号位的其余位
负数：绝对值为其除去符号位的其余位取反再加1

类型转换
double转为int自动舍去小数
char和int可以互相转换：例如’0’ 48；‘A’ 65；‘a’ 97
其中int类型转为char类型时只保留其最低8位，高位部分舍弃。

0x开头的整数为十六进制数；
0开头的整数为八进制数

#include<iostream>
#include<cstdio>
using namespace std;
int main() {
	int a = 01234567;
	int b = 04567;
	int c = 0x1234567;
	int d = 0x4567;
	printf("%c %c %c %c", a, b, c, d);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

1.5 常量

字符型常量

常量
宏定义：
#define 常量名 常量值
宏替换：使用常量名时用对应的常量值(串)来替换它

#include<iostream>
#include<cstdio>
using namespace std;
//数值常量 字符串常量 表达式常量
#define MAX_NUM 1000
#define UNIVERSITY_NAME "Peking University"
#define MYINT i=5

int main() {
	printf("%d\n%s\n", MAX_NUM, UNIVERSITY_NAME);
	int i;
	MYINT;
	printf("%d", i);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

PS：以#为前缀的代码，则为预处理代码，它会在程序编译前先行处理，所以在编译前会进行宏替换，将常量名转化为对应的串，再行编译。
PS：优点 便于修改，增加程序的可维护性

第二周

2.1 输入输出进阶

输入输出控制符
printf和scanf中可以使用以"%"开头的控制符，指明要输入或输出的数据类型及格式。

#include<stdlib.h>
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a = 0b10; //二进制
	int b = 010;  //八进制
	int c = 10;   //十进制
	int d = 0x10; //十六进制
	printf("10对应的值 二进制 八进制 十进制 十六进制\n");
	printf("%15d %6d %6d %6d\n", a, b, c, d);
	printf("10对应的进制 八进制 十进制 十六进制\n");
	printf("%#15d %#6o %#6d %#6x\n", c, c, c, c); //用#输出不同进制的10的标识

	int n=31;
	char e='o';
	double f=1.2345;
	printf("n=%d c=%c f=%lf\n", n, e, f);
	printf("%%x n=%x\n", n);
	printf("%%10.3lf f=%10.3lf\n", f); //保留小数时是默认四舍五入，而不是double转int时直接剔除小数
	printf("%%04d n=%04d\n\n", n);

	printf("C++的输入输出：");
	int n1, n2;
	char c1;
	//cin输入
	cin >> n1 >> c1 >> n2;
	//cout输出
	cout << n1 << endl; //endl自带换行功能
	cout << c1 << endl;
	cout << n2 << endl; 
	system("pause");
	return 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
26
27
28
29
30
31
32
33
34
35
36

可以观察到读入char类型时没读入空格，这时需要的话可以用cin.get()来读入空格。

#include<iostream>
#include<cstdio>
using namespace std;

int main() {
	int n;
	//cin.get()返回值是int类型，所以用int类型接收，读取时也需要转成char类型
	while ((n = cin.get()) != EOF)
	{
		cout << (char)n;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

cin,cout输入输出速度比scanf,printf慢，输入输出数据量大时用后者；不要混用。

2.2 算术运算符和算术表达式

常用算术运算符：=，+=，-=，*=，/=，%=
a = b
其中=为赋值运算符 将b的值赋值给a
a += b
等同于a = a+b
其中a + b时以操作数精度高的类型为准
精度：浮点型>整型>字符型
即 double > long long > int > short > char
例如：2 * 0.5 => 1.0
其余类似
补充说明：
/= 取商
%= 取余
5 /= 2 => 2
5 %= 2 => 1

溢出：整数溢出部分舍弃；实数溢出部分，不易预测
例如：
char类型 127 + 1 = ？
unsigned char类型 255 + 1 =？

#include<iostream>
using namespace std;

int main() {
	char c = 127;
	unsigned char c1 = 255;
	c += 1;
	c1 += 1;
	printf("%d\n", c);
	printf("%d\n", c1);
}
1
2
3
4
5
6
7
8
9
10
11

第二个显然：1111 1111B + 0000 0001B =1 0000 0000B 舍去溢出部分为0000 0000B所以值为0
第一个原因如下：
事先说明：char类型二进制由1个符号位 + 7个数值位组成
0111 1111B + 1B = 1000 0000B
因为-0D＝1000 0000B 原码转为补码 数值位取反+1 二进制为1 0000 0000B 溢出
补码转为原码规则相同 所以 1000 0000B找不到对应的原码 所以将其视为 -128。
在计算机中，数值一律用补码来进行表示和存储。

关于原码补码转换例子：
1010 1010B(原) = 1101 0110B(补)
1101 0110B(补) = 1010 1010B(原)
可见转换规则相同
1.4部分补充：
127D = 0111 1111B(原) = 0111 1111B(补)
-127D = 1111 1111B(原) = 1000 0001(补)
所以127D在计算机存储的二进制是0111 1111；-127D在计算机中存储的二进制是1000 0001

自增自减运算符：++ –
a++;先赋值后运算
++a;先运算后赋值
eg：
int a,b,c = 3;
a = ++c;
b = c++;
则a = 4，b = 4，c = 5

2.3 关系运算符和逻辑表达式

关系运算符：
相等 ==
不等 !=
大于 >
小于 <
大于等于 >=
小于等于 <=
比较的结果是bool类型成立为true反之为false
其中false等价于0，true等价于非0整型值

逻辑运算符和逻辑表达式
&& 与
a && b 当且仅当a和b都为真(或非0)时，结果为true
|| 或
a || b 当且仅当a和b都为假(或0)时，结果为false
! 非
!a a真值取反(true变false，false变true)

其中&&为短路与，也就是说a的真值为false时，直接返回结果false，不会执行b语句。||也类似。
eg：
int a = 0,b = 2;
int n = a++ && ++b;
cout << n << “,” << a << “,” << b;

输出：0,1,2
因为a++先赋值后运算。所以 n = 0 && ++b; n值直接变为0，&&后面的语句没有执行，所以n值为0，a值为1，b值为2。

2.4 其他运算符及运算符优先级

强制类型转换符：类型名本身就是一个运算符，用于将操作数转换为指定类型
eg：
int n = 9;
double f;
f = n / 2; // f = 4
f = (double)n / 2; // 将int类型的n强制转换为double。f = 4.5
运算符优先级
由高到低：
++ – !
* / %
+ -
< <= > >= == !=
&&
||
= += -= *= /= &=
需要留心的是：
算术运算符优先级高于关系运算符；
关系运算符优先级高于&&；
&&优先级高于||；
赋值运算符和算术运算符的简写优先级最低

eg：
问题：
5 + 4 || 0 && 1 的值是？
3 *= 3 + 2 的值是？
1 >= 2 && 0 <= 3 的值是？
答案：
1
15
0

第三/四周

3.1 if语句

if(表达式){
语句组1
}
else if(表达式2){
语句组2
}
…//可以有多个else if
else{
语句组n
}

PS：语句组如果只有一条语句则{}可以省略。
例如：
if(100)
pritnf(100);
就会输出100
PS：0为false 非0为true 常用于整数能否被整除，比如说是n为奇数则为true则表达式可以写成n%2；n为偶数则为true则表达式可写成!(n%2)

PS：else总是和它最近的if配对

3.2 switch语句

switch(表达式){
case 常量1：
语句组1
break;
case 常量2：
语句组2
break;
…//可以有多个case
default: //case都不匹配则执行其中语句组，default也可不写
语句组n+1
}

PS：因为switch不会主动跳出，只会匹配到相应的常量后，顺序执行，所以需要执行完相应语句块后，使用break跳出。（如果某几个case中语句块相同，则可将它们写一块，并将它们之间的break省略）

PS：显然 区间的判断用if 值的判定用switch

3.3/4 for循环

for(表达式1;表达式2;表达式3){
语句块
}
执行流程：

1. 执行表达式1
2. 执行表达式2 若为true则执行语句块，然后进入3；若为false则for循环结束
3. 执行表达式3
4. 转到2
   PS：写表达式时可用,隔开写多个表达式
   例如：
   for(int i=0,j=n;i<j;i++,j–){
   printf(“n=%d+%d”,i,j);
   }

3.5/6 while循环和while循环

while(表达式){
语句组
}

1. 判断表达式是否为真，不为真则转4
2. 执行语句组
3. 转1
4. while语句结束

do{
语句组
}while(表达式);

PS：先执行后判断用do while；先判断后执行用while
PS：确定次数的用for；必须先执行的用do while；其余情况用while

第四周

4.1 break和continue

break关键字 可跳出当前循环

continue关键字 立即结束本次循环，并回到循环体的开头判断是否要执行下一次循环
（在for语句中会执行表达式3再执行表达式2再执行语句块）

PS：在多重循环嵌套中，它们跳出/结束的都是它们所在的循环

4.2 OJ输入数据的处理

scanf()表达式的返回值为int类型，表示成功读入的变量个数

scanf()返回值为EOF(-1)时说明输入数据已经结束

cin >> n >> m… 成功读入所有变量时为true，否则为false

可用于while中表达式
eg：

#include<iostream>
#include<cstdio>
using namespace std;

int main() {
	int n, m;
	while (scanf("%d%d",&n,&m) != EOF) 
	{
		printf("%d\n", n + m);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

#include<iostream>
#include<cstdio>
using namespace std;

int main() {
	int n, m;
	while (cin >> n >> m) 
	{
		printf("%d\n", n + m);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

不断的输入两个整数的和再敲回车，则不停地输出它们的和，直到单独一行输入Ctrl+Z然后回车 程序就会结束

4.3 用freopen重定向输入

PS：\是拿来转义用的字符(常见的如\n 换行)，所以需要输出单纯的\时需要\把\转义成单纯的\。

第五周

5.1 数组

类型名 数组名[元素个数];
eg:int number[10];

PS:char类型自动转为对应的ASCLL码所以也可用作下标
eg:int number[‘A’] 即是 int number[65]

以T a[N];为例

1. 元素的编号叫下标，下标从0开始，通过数组和下标，就能访问元素 例如：a[0]指访问数组a[N]第一个元素的值
2. 元素在内存里是一个挨一个连续存放的
3. 数组占用大小总共为 N * sizeof(T) 字节的存储空间
   3.1 sizeof()也可直接作用于数组 例如：sizeof(a) 返回的就是数组a占用的空间大小
4. 数组名a代表数组的地址，a的地址和a[0]的地址相同，假设为p，则变量a[i]的地址就是p+i*sizeof(T)
5. 作为参数传参时，需要另一个参数来传递数组大小
6. 数组最好定义在main方法外面

5.2 筛法求素数

思路：
自然语言

1. 把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，
2. 然后每次从下一个剩下的数(必然是素数)开始，划掉其n内的所有倍数。
3. 最后剩下的数，就都是素数

空间换时间，加快了计算速度

流程：

1. 设置一个标志数组isPrime，isPrime[i]的值是1就表示i是素数，开始数组元素值全部为1
2. 划掉k的倍数，就是把isPrime[2*k]，isPrime[3*k]…置为0
3. 最后检查isPrime数组，输出isPrime[i]为1的那些i；

代码：

#include<iostream> //筛法求素数
#include<cstdio>
using namespace std;
#define MAX_NUM 10000
char isPrime[MAX_NUM + 1]; //要将MAX_NUM的值也放入判断，又因下标从0开始，所以需要元素个数+1
int main() {
	for (int i = 2; i <= MAX_NUM; i++) //开始假设所有数是素数
		isPrime[i] = 1;
	for (int i = 2; i <= MAX_NUM; i++) { //每次将一个素数的所有倍数标记为非素数
		if (isPrime[i]) //只标记素数的倍数
			for (int j = i * 2; j <= MAX_NUM; j += i) 
				isPrime[j] = 0; //将素数的倍数标记为非素数
	}
	for (int i = 2; i <= MAX_NUM; i++)
		if (isPrime[i])
			cout << i << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.3 数组初始化

在定义一个一维数组的同时，就可以给数组中的元素赋初值
规则如下：

1. 定义时数组容量不填写，根据数组内个数自动填充数组容量
2. 数组内个数小于数组容量，自动补0
3. 数组定义时，可以通过[i]=？给数组内下标i的位置直接赋值，逗号后就是给数组中i+1的位置赋值。
   常用于稀疏数组

演示如下

#include<stdio.h>

int main() {
	int a1[] = { 0,1,2,3,4,5,6,7,8,9 }; //根据数组内个数自动填充数组容量
	int a2[10] = { 0,1,2,3,4,5 };                  //自动补0
	for (int i = 0; i < 10; i++) {
		printf("%d\t", a1[i]);
	}
	printf("\n");
	for (int i = 0; i < 10; i++) {
		printf("%d\t", a2[i]);
	}
	printf("\n");
	printf("a1的元素个数=%d", sizeof(a1)/sizeof(a1[0]));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

用数组取代复杂分支结构
其实就是switch里case常量对应的语句组都是单个值的输出或者改变时
就可以转化为数组里面下标和值的对应
例如：输入数字1~7 输出对应的星期几的英语单词，输入其他数，则输出Illegal

#include<iostream>
#include<string> //使用string必须引用此头文件
#include<cstdio>
using namespace std;
string weekdays = { "Monday" ,"Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday" }; //字符串类型 可存放字符串常量
int main() {
	int n;
	cin >> n;
	if (n > 0 && n < 8)
		cout << weekdays[n];
	else
		cout << "Illegal";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.4 数组越界

数组越界不会导致编译错误，但是可能导致程序运行出错。
因为写入了别的变量的内存空间，或者写入指令的内存空间。

#include<iostream>
#include<cstdio>
using namespace std;
int a[2];
int main() {
	a[-2] = 1;
	a[3] = 1;
	cout << a[-2] << a[3] << a[-99];
	return 0;
}
1
2
3
4
5
6
7
8
9
10

5.5 二维数组

数据类型 变量名[容量][容量];
形似线代中的矩阵
初始化

1. 行数可以不给出，列数必须给出
2. 在定义二维数组时，右侧可用{{},{}}来描述二维数组的行列，但是列数已经给出，外部大括号的内部大括号也可以省略，让计算机自行读取对应列数后，行数+1再行读取
3. 省略的数会自动补0

#include<stdio.h>
int main() {
	int a[][3] = { 1,2,3,4,5,6,7,8 };
	//等同于 int a[3][3] = {{1,2,3},{4,5,6},{7,8,0}}
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++)
			printf("%d ", a[i][j]);
		printf("\n");
	}
}

1
2
3
4
5
6
7
8
9
10
11

例题：矩阵乘法

矩阵行列不会超过8

#include<iostream>
#include<cstdio>
using namespace std;
#define ROWS 8
#define COLS 8
int a[ROWS][COLS];
int b[ROWS][COLS];
int c[ROWS][COLS];
int main() {
	int m, n, p, q;
	cin >> m >> n;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	cin >> p >> q;
	for (int i = 0; i < p; i++)
		for (int j = 0; j < q; j++)
			cin >> b[i][j];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < q; j++) {
			c[i][j] = 0;
			for (int k = 0; k < n; k++)
				c[i][j] += a[i][k] * b[k][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < q; j++)
			cout << c[i][j] << " ";
		cout << endl;
	}

	return 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
26
27
28
29
30
31
32
33
34

第六周

6.1/2 函数

函数定义
返回值类型 函数名(参数1类型 参数1名称，参数1类型 参数1名称···){
语句组
}

eg：int add(int a,int b){
return a+b;
}

PS：

1. 不需要返回值，则返回值类型可以写void
2. 不需要参数，则参数表可以写void 也可以啥都不写
3. 调用函数时传的参数为实参(确定的值)，函数本身的参数为形参(其值依传入参数的值而定)
4. 形参是实参的拷贝，形参的改变不会影响到实参。除非形参类型是数组或引用(指针)。因为那时传的不是值，而是地址。
   数组可以参考5.1的第四点，数组本身传的就是数组第一个元素的地址。
5. 函数一般写在main函数前面；如果需要写在下面，则需要进行函数的原型声明
   返回值类型 函数名(参数表)
   参数名可以省略，参数类型不可省略
   eg：double Distance(double,double,double,double)

#include<iostream>
#include<cstdio>
using namespace std;
static int as[10] = { 0 };

int add(int, int);
void change(int qweqweqw[]);
int main()
{
	int a = 3, b = 5;
	cout << add(a, b) << endl;
	change(as);
	for (int i = 0; i < sizeof(as) / sizeof(as[0]); i++) {
		cout << as[i] << " ";
	}
	return 0;
}
//a+b
int add(int a, int b) {
	return a + b;
}
//把数组a元素置位1
void change(int a[]) {
	for (int i = 0; i < 10; i++) {
		a[i] = 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

6.3 递归初步

一个函数自己调用自己，就是递归

//阶乘
int Factorial(int n){
	if(n<2)
		return 1;
	else
		return n * Factorial(n-1);
}
//斐波那契数列
int Fib(int n){
	if( n ==1 || n == 2)
		return 1;
	else
		return Fib(n-1)+Fib(n-2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

阶乘：当n=5时
5 * Factorial(4)；//Factorial(4)再调用
4 * Factorial(3)；//Factorial(3)再调用
3 * Factorial(2)；//Factorial(2)再调用
2 * Factorial(1)；//Factorial(1)再调用
返回1
最后逐个返回
1
2 * 1
3 * 2 * 1
4 * 3 * 2 * 1
5 * 4 * 3 * 2 * 1

1. 递归本身肯定是需要一个结束条件的，也就是用来终止递归的条件，将自我调用的程序收束回最开始。（因为，递归中止，程序开始收束的时候，函数才会逐个返回值，结束对空间的占用。所以，其实递归挺耗空间的）

6.4 库函数和头文件

#include<头文件>

库函数：C/C++标准规定的编译器自带的函数
头文件：C++编译器提供许多头文件，如iostream cmath string等；头文件内部包含许多库函数的声明以及其他信息，如iostream头文件中cin，cout的定义

6.5 位运算

用于对整数类型变量中的某一位(bit)，或者若干位进行操作。
C/C++语言提供了六种位运算符来进行位运算操作：

eg：
与操作 都为1则为1 否则为0
21 & 18
即 0001 0101 & 0001 0010 ＝ 0001 0000
所以 21 & 18 = 16
PS：\ ^ ~操作符类似，都是先转为二进制，然后按操作符性质进行位操作，然后转回十进制

按位与 & （有0就为0）

1. 通常用来将某变量中的某些位清0且同时保留其他位不变
   例如，如果需要将int类型变量n的低8位全置成0，而其余位不变，则可以执行：
   n = n & 0xffffff00;
   也可以写成：
   n &= 0xffffff00;
2. 也可以用来获取某变量中的某一位。
   例如判断一个int型变量n的第7位（从右往左，从0开始数）是否是1？
   只需看表达式 n & 0X80 的值是否等于0x80即可
   0x80：1000 0000

按位或 | （有1就为1）

1. 通常用来将某变量中的某些位置为1且同时保留其他位不变
   例如，如果需要将int类型变量n的低8位全置成1，而其余位不变，则可以执行：
   n &= 0xff;

按位异或 ^ （不同则为1）

1. 通常用来将某变量中的某些位取反且同时保留其他位不变
   例如，如果需要将int类型变量n的低8位取反，而其余位不变，则可以执行：
   n ^= 0xff;
2. 特点：a^b=c 可推出 c^b=a c^a=b（穷举法可证）（可以用此进行最简单的加密 解密）（可以用此不通过临时变量 交换两个变量的值a^=b;b^=a;a^=b）

按位非 ~

1. 将操作数中的二进制位0变成1,1变成0

左移运算符 <<
a<<b;
将a各二进位全部左移b位后得到的值。左移时，高位丢弃，低位补0。a的值不因运算而改变。

1. 左移n位，就等同于乘以2ⁿ 。而左移操作比乘法操作快得多。

右移运算符 >>
a>>b;
将a各二进位全部右移b位后得到的值。右移时，移出最右边的位就被丢弃。a的值不因运算而改变。

1. 有符号数，右移时，符号位一起移动。原符号位为1，则右移补充1；原符号位为0，则右移补充0。
2. 同理，右移n位，就等同于除以2 。并且将结果往小里取整
   -25 >> 4 = -2
   -2 >> 4 = -1
   18 >> 4 = 1
   
   

位运算符优先级
高到低：
~
<< >>
&
^
|

6.6 位运算思考题

(a>>n)&1
先将a的第n位移到最右边；然后将其 & 1

(a & (1<<n))>>n
先将1左移n位 得到一个除了第n位是1 其余位为0的数 ；然后 & a 得到a的第n位是几 结果就是几；然后右移n位

PS：位运算速度快 能提高运算效率

第七周

7.1/2 字符串

三种形式：

1. 双引号括起来的字符串常量，如"CHINA"等
2. 存放于字符数组中，以’\0’字符(ASCII码为0)结尾
3. string对象。string是C++标准模板库里的一个类，专门用于处理字符串。需引用<cstring>头文件

PS：

1. 字符串常量占用字节数等于字符串中字符数+1，多出来的是结尾字符’\0’
2. 字符串长度不包含’\0’
3. ""空串仍然占据一个字节的存储空间，存放’\0’
4. \" 输出"需使用\将其转义成无特殊意义的"

用一维char数组存放字符串

1. 包含’\0’字符的一维char数组，就是一个字符串。其中存放的字符串即为’\0’前面的字符组成
2. 用char数组存放字符串，数组元素个数应该至少为字符串长度+1
3. 字符数组可用cout printf输出，用cin scanf输入。输入时会自动在字符串末尾加上’\0’

 #include <stdio.h>
int main() {
    char a[]="Hello World";
    char b[]="Hello W\0orld";
    printf("sizeof(a)=%d\n",sizeof(a));
    printf("%s\n%s",a,b);
	return 0;
}
 
1
2
3
4
5
6
7
8
9

前置知识：char类型占一个字节
其中字符数组a里面包含的字符总共11个。但是字符数组a的空间大小是12，所以说明了它会自动在字符数组末尾加上结尾字符’\0’。
在字符数组b中，中间加了结尾字符’\0’，从输出看果然就结尾到’\0’部分。
顺带一提，设定字符数组a容量为11的话，会报错。因为他需要12个空间。

读入到空格就会停止读入，解决方式

1. cin.getline(字符数组,常量a)
   会在输入流中最多读入a个字符到字符数组。（超出的不读入）
2. gets(字符数组)
   读入一行到字符数组，可能导致数组越界。

7.3 字符串库函数

前置知识：

1. 使用字符串函数需要引用C++的#include<cstring>或者C的#include<string.h>
2. 字符串函数根据\0来判断字符结尾
3. 形参为char[]类型，则实参可以是char数组或字符串常量

库函数：

1. 字符串比较大小
   int strcmp(char [] s1,char [] s2); // 逐个字符比较；返回0则相等；返回负数则s1小于s2；返回正数则s1大于s2
2. 字符串拷贝
   int strcpy(char [] dest,char [] src); //拷贝src到dest
3. 求字符串长度
   int strlen(char [] s); //不算结尾的’\0’
4. 字符串拼接
   strcat(char [] s1,char [] s2); //s2拼接到s1后面
5. 字符串转成大写
   strupr(char []);
6. 字符串转成小写
   strlwr(char []);

strlen糟糕用法

char s[100]="test";
for(int i=0;i<lenstr(s);i++)
	s[i]=s[i]+1
1
2
3

执行lenstr本身需要时间，且时间和字符串长度成正比。所以每次调用strlen函数，这是效率上的浪费。

char s[100]="test";
int len=strlen(s);
for(int i=0;i<len;i++)
	s[i]=s[i]+1
1
2
3
4

所以应在循环之前用常数储存字符串的长度
或者用其s[4]=’\0’=0的特性来遍历

char s[100]="test";
for(int i=0;s[i];i++)
	s[i]=s[i]+1
1
2
3

7.4 编写判断子串的函数

int Strstr(char s1[],char s2[]);
如果s2不是s1的子串，返回-1
如果s2是s1的子串，返回其在s1中第一次出现的位置
空串是任何串的子串，且出现位置为0

int Strstr(char s1[],char s2[]){
	if(!s2[0])
		return 0;
	for(int i=0;s1[i];i++){
		int k=i,j=0;
		for(;s2[j];j++,k++){
			if(s1[k]!=j[j])
				break;
		}
		if(!s2[j]){
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 先判断是不是空串，是空串则返回0
2. 遍历字符数组s1，遍历完毕转到5
3. 每取出一个字符都将其作为首位和字符数组s2进行遍历配对，配对失败则跳出循环
4. 每次都配对成功则下标j会指向字符数组s2的’结尾字符\0’，以此为依据判断s2是否为s1的子串，是子串则返回i值
5. s1遍历结束则返回-1

第八周

8.1 指针的基本概念和用法

基本概念

1. 每个变量都被存放在从某个内存地址开始的若干个字节中。
2. 指针，也称作指针变量，大小为4个字节(或8个字节)的变量，其内容代表一个内存地址
   32位的4个字节；64位的8个字节
3. 通过指针，能够对该指针指向的内存区域进行读写
4. * 间接引用运算符
   & 取地址运算符

指针定义：类型名 * 指针变量名;
例如：int * p;

简单来说：p是内存地址；*p是储存在内存地址的内容

#include <stdio.h>
int main() {
    int a=10;
    int * p = &a;
    printf("*p=%d\np=%d\n",*p,p);
    return 0;
}
1
2
3
4
5
6
7

因为我用的是网页C语言编译器，所以地址是0。但总的来说，还是可以看出*p和p的不同的。
指针一般用来指向变量。然后传递参数时用指针传地址。

指针大小

#include <iostream>
using namespace std;

int main()
{
	int i = 3;
	int *pn = &i;
	char *pc;
	float *pf;
	cout << sizeof(*pn) << sizeof(pc) << sizeof(pf);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

显然：指针本身占据8个字节；指向的变量占据的内存大小还是看其本身的数据类型。

8.2 指针的意义和互相赋值

指针的作用：有了指针，就有了自由访问内存空间的手段。
PS：可以通过对变量的地址进行加减操作来访问变量前面或后面的内存区域。

指针的互相赋值：不同类型的指针，如果不经过强制类型转换，不能互相赋值

前置知识：int占4个字节；char占1个字节
int类型指针pn指向c；
*pn中只有第一个字节的值可以确定为0x65，后面三个字节的值不确定。所以执行int n = * pn;时n值不确定；
同理，执行 * pn = 0x12345678时因为不知那三个字节的值能否更改，所以编译不会报错，但是执行时候，可能会报错。

8.3 指针的运算

1. 两个同类型的指针变量，可以比较大小
2. 两个同类型的指针变量，可以相减
   例如T * 类型的指针p1和p2
   p1-p2=(地址1-地址2)/sizeof(T)
3. 指针变量加减一个整数的结果是指针
   例如：int *p;nt n=1;
   p+=n //地址p+n*sizeof(int)
4. 指针变量可以自增、自减
   p++,++p：p指向 n + sizeof(T)
   p–,--p：p指向 n - sizeof(T)
5. 指针可以用下标运算符"[]"进行运算
   p 是一个 T*类型的指针
   n是整数类型的变量或常量
   则 p[n] 等价于 *(p+n)

#include<iostream>
#include<cstring>
using namespace std;

int main() {
	int a[10] = { 0 };
	printf("%d", &a[10]-a);
	return 0;
}
1
2
3
4
5
6
7
8
9

验证了一下2和5。确实是最后会/sizeof(T)

8.4 指针作为函数参数

空指针：地址0不能访问。指向地址0的指针就是空指针。
可以使用NULL关键字对任何类型的指针进行赋值。NULL实际上就是整数0，值为NULL就是空指针。可用作条件表达式。

因为传的是地址，所以交换*p1和*p2地址后，也会影响到主函数中变量m和n的值。

8.5 指针和数组

1. 数组的名字是一个指针常量，指向数组的起始地址。即 a的地址 等价于 &a[0]，但是容量为数组a的容量
   例如：T a[N];
   a的类型时T *
   可以用a给一个T *类型的指针赋值
   a是编译时就确定了的常量，不能够对a进行赋值
2. 作为函数形参时，T *p和T p[]等价
   
   用到了a指向a[0]；*(p+n)等价于p[n]；p=a+1 \\p指向a[1]的地址
   颠倒数组
   
   需要说明的是a指向a[0]，但是其容量是整个数组的容量。传参时，a的容量变为指针类型的8个字节。*a=a[0]。

#include<iostream>
#include<cstring>
using namespace std;

void f(int a[]);
int main() {
	int a[10] = { 1,2,3,4,5,6,7,8,9,0 };
	cout << *a << endl;
	cout << sizeof(a) << endl;
	f(a);
	return 0;
}

void f(int a[]) {
	cout << *a << endl;
	cout << sizeof(a) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第九周

9.1 指针和二维数组

简单来说，二维数组是顺序存储在内存地址中的，所以在内存地址中二维数组的表现形式是多个一维数组首尾衔接。
例如char a[2][3]那么a[0][3]后面的地址就是a[1][0]的地址
指向指针的指针
T ** p;
p是指向指针的指针，p指向的地方1应该存放着一个类型为T *的指针。
*p的类型是T*

9.2 指针和字符串

读入字符串
char name[20];
int n;
scanf("%d%s",&n,name); //scanf读入
cin >> n >> name; //cin读入

9.3 字符串库函数

const 常量的意思
操作实例

9.4 void指针和内存操作函数

void指针
void * p
* p无定义
* 对于p的相关操作如：p++ 等均无定义

内存操作函数



因为是逐字节拷贝，所以转为char类型然后遍历拷贝。
如果两个指针内存范围有重叠，会出错。

9.5 函数指针

定义形式： 类型名(* 指针变量名)(参数类型1,参数类型2,…);
例如：int(*pf)(int,char)
使用方法： 函数指针名(实参表);

#include<stdio.h>
void PrintMin(int a, int b) {
	if (a < b)
		printf("%d", a);
	else
		printf("%d", b);
}


int main() {
	void(*p)(int, int);
	int a = 1, b = 2;
	p = PrintMin;
	p(a, b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

函数指针和qsort库函数

有点迷 标记一下

第十周

10.1 结构（struct）

要用多个不同类型的变量来描述一个事物，则可以用struct来自定义新的数据类型来存放这些变量。
定义方式
struct 结构名
{
类型名 成员变量名;
类型名 成员变量名;
类型名 成员变量名;
…
};
eg：
struct Student
{
unsigned ID;
char szName;
float fGPA;
}
Student是自定义的新的数据类型，自然可以用来定义变量
Student s1,s2;

特性

1. 两个同类型的结构变量，可以互相赋值。但是结构变量之间不能进行比较运算
2. 一般来说，一个结构变量所占的内存空间大小，就是结构中所有成员变量大小之和。
   连续存储。
3. 一个结构的成员变量可以是任何类型的，包括可以是另一个结构类型。
   可以是指向本结构类型的变量的指针

访问结构变量的成员变量：结构变量名.成员变量名
结构变量的初始化：结构变量名 变量名 = {成员变量1,成员变量2,…};
结构数组：结构变量名 变量名[容量];
指向结构变量的指针：结构名 * 指针变量名;
总的来说上面三者的结构变量的使用方法和普通的数据类型的使用方法是一样的。

指向结构变量的指针

1. 通过指针，访问其指向的结构变量的成员变量
   指针->成员变量名
   或：
   (* 指针).成员变量名

#include <stdio.h>
struct StudentEx {
	unsigned int ID;
	int Stu;
	double fGPA;
};
int main() {
	StudentEx Stu;
	StudentEx * pStu = &Stu;
	pStu->ID = 12345;
	(*pStu).fGPA = 3.48;
	printf("%d\n%f", Stu.ID, Stu.fGPA);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

10.2 全局变量、局部变量、静态变量

全局变量和局部变量

• 定义在函数内部的变量叫局部变量（函数的形参也是局部变量）
• 定义在所有函数的外面的变量叫全局变量
• 全局变量在所有函数中均可以使用
  局部变量只能在定义它的函数内部使用

静态变量

• 全局变量都是静态变量。局部变量定义时如果前面加了"static"关键字，则该变量也成为静态变量
• 静态变量的存放地址，在整个程序运行期间，都是固定不变的
• 非静态变量（一定是局部变量）地址每次函数调用时都可能不同，在函数的一次执行期间不变
• 如果未明确初始化，则静态变量会被自动初始化成全0（每个bit都是0），局部非静态变量的值则随机
  静态变量在整个程序运行的过程中只初始化一次

静态变量应用：strtok的实现


其中strchr(char * s1,char * s2)是用来判断s2是否在s1中，如果出现在里面则返回非空指针则为true。

10.3 变量的作用域和生存期

标识符的作用域

• 变量名、函数名、类型名统称为“标识符”。一个标识符能够其作用的范围，叫做该标识符的作用域
• 在一个标识符的作用域之外使用该标识符，会导致“标识符没有定义”的编译错误。使用标识符的语句，必须出现在它们的声明或定义之后
• 在单文件的程序中，结构、函数和全局变量的作用域是其定义所在的整个文件
• 函数形参的作用域是整个函数
• 局部变量的作用域，是从定义它的语句开始，到包含它的最内层的那一对大括号“{}”的右大括号“}”为止
• for循环里定义的循环控制变量，其作用域就是整个for循环
• 同名标识符的作用域，可能一个被另一个包含。则在小的作用域里，作用域大的那个标识符被屏蔽，不起作用。

其他都挺显然的，不过最后一点值得注意一下。

变量的生存期

• 所谓变量的生存期，指的是在此期间，变量占有内存空间，其占有的内存空间只能归它使用，不会用来存放别的东西。
• 而变量的生存期终止，就意味着该变量不再占有内存空间，它原来占有的内存空间，随时可能被派作他用。
• 全局变量的生存期，从程序被装入内存开始，到整个程序结束
• 静态局部变量的生存期，从定义它语句第一次被执行开始，到整个程序结束为止。
• 函数形参的生存期从函数执行开始，到函数返回时结束。非静态局部变量的生存期，从执行到定义它的语句开始，一旦程序执行到了它的作用域之外，其生存期即告终止。

感觉都挺显然…不过概念还是需要了解的

10.4 选择排序和插入排序

选择排序

void SelectionSort(int a[],int size){
    for(int i=0;i<size-1;i++){
        int tmpMin=i;
        for(int j=i+1;j<size;j++){
            if(a[j]<a[tmpMin])
                tmpMin=j;
        }
        int tmp = a[i];
        a[i] = a[tmpMin];
        a[tmpMin] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

插入排序

• 将整个数组a分为有序的部分和无序的两个部分。前者在左边，后者在右边。
• 开始有序的部分只有a[0]，其余都属于无序的部分
• 每次取出无序部分的第一个元素，把它加入到有序元素部分。假设插入到合适位置p，则原p位置及其后面的有序元素，都向右移动一个位子。有序的部分即增加了一个元素

void InsertionSort(int a[], int size) {
	for (int i = 1; i < size; i++) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[i]) {
				int t = a[i];
				for (int k = i; k > j; k--)
					a[k] = a[k - 1];
				a[j] = a[i];
				break;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

10.5 冒泡排序

• 将整个数组a分为有序部分和无序部分。前者在右，后者在左。
• 开始，整个数组都是无序的。有序的部分没有元素。
• 每次要使得无序部分最大的元素移动到有序部分第一个元素的左边。移动的方法是：依次比较相邻的两个元素，如果前面的比后面的大，就交换他们的位置。这样，大的元素就像水里气泡一样不断往上浮。移动结束有序部分增加了一个元素。
• 直到无序部分没有元素

void BubbleSort(int a[], int size) {
	for (int i = size - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[j + 1]) {
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

10.6 程序或算法的时间复杂度

时间复杂度

• 一个程序或算法的时间效率，也称“时间复杂度”，有时简称“复杂度”
• 复杂度常用大的字母0和小写字母n来表示，比如O(n)，O(n²)等。n代表问题的规模
• 时间复杂度是用算法运行过程中，某种时间固定的操作需要被执行的次数和n的关系来度量的。在无序数列中查找某个数，复杂度是O(n)
• 计算复杂度的时候，之统计执行次数最多的（n足够大时）那种固定操作的次数。比如某个算法需要执行加法n² 次，除法n次，name就记其复杂度是O(n²)的
• 复杂度有“平均复杂度”和“最坏复杂度”两种。两种可能一致，也可能不一致
• 如果复杂度是多个n的函数之和，则只关心随n的增长增长得最快的那个函数
  O(n³ +n²) => O(n³)
  O(n³ +2ⁿ) => O(2ⁿ)
  O(n³ +n!) => O(n!)

常用复杂度

• 常数复杂度：O(1)
• 对数复杂度：O(log(n))
• 线性复杂度：O(n)
• 多项式复杂度：O(n^k)
• 指数复杂度：O(aⁿ)
• 阶乘复杂度：O(n!)

部分程序\算法复杂度

• 在无序数列中查找某个数（顺序查找） O(n)
• 平面上有n个点，要求出任意两点之间的距离 O(n²)
• 插入排序、选择排序、冒泡排序 O(n²)
• 快速排序 O(n*log(n))
• 二分查找 O(log(n))

第十一周

11.1 STL排序算法sort

STL概述

• STL (Standard Template Library) 标准模板库
• 包含常用算法和数据结构，如查找，链表等
• 使用方便，效率较高
• 需引用#include<alorithm>头文件

排序算法 sort：

• 用法一：对基本类型的数组从小到大排序
  sort(数组名+n1,数组名+n2)
  将数组中下标[n1,n2)进行从小到大排序
  
• 用法二：对基本类型的数组从大到小排序
  sort(数组名+n1,数组名+n2,greater<T>())
• 用法三：用自定义的排序规则，对任何类型T的数组排序
  sort(数组名+n1,数组名+n2,排序规则结构名())

排序规则结构的定义方式

struct 结构名
{
	bool operator()(ocnst T & a1,const T & a2) const {
			//若a1应该在a2前面，则返回true
			//否则返回false
		}
}
1
2
3
4
5
6
7

eg：
对数组进行sort

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct Rule1{//从大到小排序 a1应该在a2之前
	bool operator()(const int & a1, const int & a2) const {
		return a1 > a2; 
	}
};
struct Rule2 {//按个位数从小到大排序
	bool operator()(const int & a1, const int & a2) const {
		return a1 % 10 < a2 % 10;
	}
};
void Print(int a[], int size) {
	for (int i = 0; i < size; i++)
		cout << a[i] << ",";
	cout << endl;
}
int main() {
	int a[] = { 1,6,4.2,76,8,6,4,3,5,7 };
	sort(a, a + sizeof(a) / sizeof(int));//从小到大
	cout << "1)"; Print(a, sizeof(a) / sizeof(int));
	sort(a, a + sizeof(a) / sizeof(int), Rule1());//从大到小
	cout << "2)"; Print(a, sizeof(a) / sizeof(int));
	sort(a, a + sizeof(a) / sizeof(int), Rule2());//按个位数从小到大
	cout << "3)"; Print(a, sizeof(a) / sizeof(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

对结构体进行sort

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct Student {
	unsigned int ID;
	int Grade;
};
struct Rule3 {//按照成绩从大到小排序
	bool operator()(const Student & a1, const Student & a2) const {
		return a1.Grade > a2.Grade;
	}
};
void Print(Student a[], int size) {
	for (int i = 0; i < size; i++)
		cout << a[i].ID << " " << a[i].Grade << endl;
}
int mainr1112() {
	Student a[] = { {2020030901,50},{2020030902,70},{2020030903,10},{2020030904,100} };
	sort(a, a + sizeof(a) / sizeof(Student), Rule3());//按成绩从大到小
	Print(a, sizeof(a) / sizeof(Student));

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

11.2 STL二分查找算法

STL提供在排好序的数组上进行二分查找算法

• binary_search //二分查找
• lower_bound //下界
• upper_bound //上界

binary_search
用binary_search进行二分查找

• 从小到大排好序的基本类型数组上进行二分查找：
  binary_search(数组名+n1,数组名+n2,值); //用法一
  查找区间为下标范围为[n1,n2)的元素，返回值为true(找到)或false(没找到)
• 在自定义排序规则排好序的、元素为任意的T类型的数组中进行二分查找：
  binary_search(数组名+n1,数组名+n2,值,排序规则结构名()); //用法二
  查找时的排序规则，必须和排序时的规则一致。
  
  排序的规则和查找的规则不一致，可能会导致查找结果不正确，所以其结果无意义。排序和查找的规则应一致。
  因为排序时的规则时按个位数从小到大排，所以查找时按规则8和98的个位数匹配成功，所以查找成功。

lower_bound
用lower_bound二分查找下界

• 在对元素类型为T的从小到大排好序的基本类型数组上进行查找：
  T* lower_bound(数组名+n1,数组名+n2,值);
  返回一个指针 T * p
  *p是查找区间里下标最小的，大于等于“值”的元素。如果找不到，p指向下标为n2的元素
• 在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
  T* lower_bound(数组名+n1,数组名+n2,值,排序规则结构名());
  返回一个指针 T * p
  *p是查找区间里下标最小的，按自定义排序规则，可以(≥)排在“值”后面的元素。如果找不到，p指向下标为n2的元素

upper_bound
用lower_bound二分查找上界

• 在对元素类型为T的从小到大排好序的基本类型数组上进行查找：
  T* upper_bound(数组名+n1,数组名+n2,值);
  返回一个指针 T * p
  *p是查找区间里下标最小的，大于“值”的元素。如果找不到，p指向下标为n2的元素
• 在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
  T* upper_bound(数组名+n1,数组名+n2,值,排序规则结构名());
  返回一个指针 T * p
  *p是查找区间里下标最小的，按自定义排序规则，必须(>)排在“值”后面的元素。如果找不到，p指向下标为n2的元素

PS：*(p+n) - a=&a[n] - a = n;

部分题目

第一周

3 多选(3分)

有两个变量a和b，在执行了如下代码后： a = 32768; b = a; printf("%d %d\n", a, b); 输出两个数：32768 -32768。 请问a和b分别是以下哪种类型？（提示：b和a的二进制形式是一样的。无符号数用%d输出结果必然是非负的。b输出为负数，说明其符号位为1）

A. 其他三个选项都不对
B. unsigned short,short
C. int,short
D. unsigned int, int

32768=2¹⁵
int -2³¹ ~ 2³¹ -1
short -2¹⁵ ~2¹⁵ -1
unsigned short 0 ~ 2¹⁶ -1
unsigned int 0 ~ 2³² -1

输出时a值没变，所以32768在a的取值范围内；
输出时b值变为-32768，所以32768肯定在b的取值范围之外，且b的左右区间必定是-32768 ~ 32767 也就是b变量为short类型时。原因可以参考2.2里的溢出部分例子讲解。
所以选 B C

第二周

4 单选(2分)

写出下面程序的输出结果:
unsigned int x = 0xffffffff;
unsigned int b = x + 2;
int y = x;
printf("%x,%d,%x,%d",y,y,b,b);

A.其他三个选项都不对
B.ffffffff,4294967295,1,1
C.ffffffff,4294967295,100000001,4294967297
D.ffffffff,-1,1,1

0xffffffff = 2³²
unsigned int b = x+2; //b=2³² -1+2-(2³² -1)+0-1=1
int y = x; //y=2³² -1-(2³¹-1)+(-2³¹)-1= -1
所以后面三个是-1 1 1那为什么前面的是ffffffff呢？因为-1D=1000 0000 0000 0001B(原码)转为补码则是1111 1111 1111 1111B所以在计算机中十六进制的表示就是ffffffff
所以选D

第四周

026:雇佣兵

总时间限制: 1000ms 内存限制: 65536kB
描述
雇佣兵的体力最大值为M，初始体力值为0、战斗力为N、拥有X个能量元素。

当雇佣兵的体力值恰好为M时，才可以参加一个为期M天的战斗期，战斗期结束体力值将为0。在同一个战斗期内，雇佣兵每连续战斗n天，战斗力就会上升1点，n为当前战斗期开始时的战斗力。

一个战斗期结束后，雇佣兵需要用若干个能量元素使其体力恢复到最大值M，从而参加下一个战斗期。每个能量元素恢复的体力值不超过当前的战斗力。每个能量元素只能使用一次。

请问：雇佣兵的战斗力最大可以到达多少。

输入
一行包括三个整数M、N、X，相邻两个整数之间用单个空格隔开。M、N、X均为不超过10000的正整数。
输出
输出一个整数，为雇佣兵的最大战斗力。
样例输入
5 2 10
样例输出
6

#include<iostream>
#include<cstdio>
using namespace std;

int main() {
	int m, n, x;
	cin >> m >> n >> x;
	while (true) {
		x = x - m / n;
		if (m % n)
			x--;
		if (x < 0)
			break;
		n += m / n;
	}
	cout << n;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

仔细读题就没问题…没认真读，错了几次，就写在这里引以为戒。
其实也可以写的再简短些，利用&&的性质，来把x值的修改，整合成一条语句，然后放进while的表达式里。

#include<iostream>
#include<cstdio>
using namespace std;

int main() {
	int m, n, x;
	cin >> m >> n >> x;
	while ((x -= m / n + (m%n && 1)) >= 0) {
		n += m / n;
	}
	cout << n;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

第五周

033:图像模糊处理

描述
给定n行m列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：

1. 四周最外侧的像素点灰度值不变；

2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。

输入
第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。
接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。
输出
n行，每行m个整数，为模糊处理后的图像。相邻两个整数之间用单个空格隔开。
样例输入
4 5
100 0 100 0 50
50 100 200 0 0
50 50 100 100 200
100 100 50 50 100
样例输出
100 0 100 0 50
50 80 100 60 0
50 80 100 90 200
100 100 50 50 100

#include<iostream>
#include<cstdio>
using namespace std;
static int a[255][255];
static int b[255][255];
int mainR033()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 || i == n - 1 || j == 0 || j == m - 1)
				b[i][j] = a[i][j];
			else
				b[i][j] = (int)(1.0*(a[i - 1][j] + a[i + 1][j] + a[i][j + 1] + a[i][j - 1] + a[i][j]) / 5 + 0.5);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << b[i][j] << " ";
		cout << endl;
	}
	return 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
26
27

简单是挺简单的，但是四舍五入的方式，我觉得还是有记录的必要。
第一位小数的四舍五入，只需将其值*1.0+0.5随后转为int类型就行。
第二位小数的四舍五入，只需将其值*10.0+0.5随后转为int类型，随后除以10再转为double类型就行
由此可以推导出对小数点后第n位小数四舍五入，只需将其值*pow(10,n-1)*1.0+0.5随后转为int类型，随后除以pow(10,n-1)再转为double类型就行
PS：
因为小数部分≥0.5的话加上0.5就进1，＜0.5就不进1，再利用int类型舍去小数的特性就达到了四舍五入的效果。

第六周

035 Pell数列

描述
Pell数列a1, a2, a3, …的定义是这样的，a1 = 1, a2 = 2, … , an = 2 * an − 1 + an - 2 (n > 2)。
给出一个正整数k，要求Pell数列的第k项模上32767是多少。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个非负整数。
样例输入
2
1
8
样例输出
1
408

#include<iostream>
#include<cstdio>
using namespace std;
static long long a[1000001];//用来保存递归结果 避免重复调用
int pell(int);
int main()
{
	int n, t;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t;
		cout << pell(t) << endl;
	}
	return 0;
}
int pell(int n) {
	if (n<3)
		return n;
	if (!a[n])
		a[n] = (2 * pell(n - 1) + pell(n - 2)) % 100000;
	return a[n] % 32767;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

使用数组保存递归结果，避免了重复调用，所以略作记录。

037 编程填空：第i位替换

描述
写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位和m的第i位相同，其他位和n相同。

请使用【一行代码】补全bitManipulation1函数使得程序能达到上述的功能

#include <iostream>
using namespace std;

int bitManipulation1(int n, int m, int i) {
// 在此处补充你的代码
}

int main() {
	int n, m, i, t;
	cin >> t;
	while (t--) { 
		cin >> n >> m >> i;
		cout << bitManipulation1(n, m, i) << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入
第一行是整数 t，表示测试组数。
每组测试数据包含一行，是三个整数 n, m 和 i (0<=i<=31)
输出
对每组输入数据，每行输出整型变量n变化后的结果
样例输入
1
1 2 1
样例输出
3
提示
二进制的最右边是第0位

	return (1 << i & m) | (n & ~(1<<i));
1

思路：

1. 先获取到m的第i位，并将其余位置为0
   1 << i & m
2. 然后将n的第i位，置为0，其余位不变
   n & ~(1<<i)
3. 最后将两者按位或
   (1 << i & m) | (n & ~(1<<i))

PS：A | 0 = A；A & 0 = 0；A | 1 = 1；（A=0,1）

同理 如果将两者按位与的话

	return (~(1 << i) | m) & (n | (1 << i));
1

038 编程填空：第i位取反

描述
写出函数中缺失的部分，使得函数返回值为一个整数,该整数的第i位是n的第i位取反，其余位和n相同

请使用【一行代码】补全bitManipulation2函数使得程序能达到上述的功能

#include <iostream>
using namespace std;

int bitManipulation2(int n, int i) {
// 在此处补充你的代码
}

int main() {
	int t, n, i;
	cin >> t;
	while (t--) {
		cin >> n >> i;
		cout << bitManipulation2(n, i) << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入
第一行是整数 t，表示测试组数。
每组测试数据包含一行，是两个整数 n 和 i (0<=i<=31)。
输出
输出整型变量n中的第i位取反的结果
样例输入
1
1 0
样例输出
0
提示
二进制的最右边是第0位

	return (1 << i) ^ n;
1

思路：

1. 将1左移到第i位
   1 << i
2. 与n异或
   (1 << i) ^ n

PS：A ^ 1 = ~A；A ^ 0 = A；（A=0,1）

第七周

043 最长最短单词

描述
输入1行句子（不多于200个单词，每个单词长度不超过100），只包含字母、空格和逗号。单词由至少一个连续的字母构成，空格和逗号都是单词间的间隔。

试输出第1个最长的单词和第1个最短单词。

输入
一行句子。
输出
两行输出：
第1行，第一个最长的单词。
第2行，第一个最短的单词。
样例输入
I am studying Programming language C in Peking University
样例输出
Programming
I
提示
如果所有单词长度相同，那么第一个单词既是最长单词也是最短单词。

#include<iostream>
#include<cstring>
using namespace std;

int main() {
	char c[10000], maxs[1000], mins[100], t[1000];
	int max, min;
	max = min = -1;
	cin.getline(c, 1000000);
	int k = -1, len = strlen(c);
	for (int i = 0; i < len; i++) {
		k++;
		t[k] = c[i];
		if (c[i] == ' ' || len == i + 1) { //获取空格前面的单词||获取最后一个没有空格的单词
			if (max == -1) { //第一次赋值，将第一个单词的长度和字符串赋给max/min和maxs/mins
				max = k;
				min = k;
				strcpy(maxs, t);
				strcpy(mins, t);
				maxs[k + 1] = 0; //拷贝字符串后追加结尾字符'\0'
				mins[k + 1] = 0;
			}
			else if (k > max) {
				max = k;
				strcpy(maxs, t);
				maxs[k + 1] = 0;
			}
			else if (k < min) {
				min = k;
				strcpy(mins, t);
				mins[k + 1] = 0;
			}
			k = -1;//清空 因为会先k++，所以清为-1
			strcpy(t, ""); //将字符数组t清为空串
		}
	}
	cout << maxs << endl;
	cout << mins << endl;
	return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

难度一般但是strcpy不会把结尾字符也拷贝过去，所以需要自行追加。这点需要注意一下。

第八/九周

050 指针练习：Memcpy之二

描述
程序填空，使得程序按要求输出

#include <iostream>
using namespace std;
void Memcpy( void * src, void * dest, int size)
{
// 在此处补充你的代码
}

void Print(int * p,int size)
{
	for(int i = 0;i < size; ++i)
		cout << p[i] << ",";
	cout << endl;
}

int main()
{
	int a[10];
	int n;
	cin >> n;
	for(int i = 0;i < n; ++i)
		cin >> a[i];
	int b[10] = {0};
	Memcpy(a,b,sizeof(a));
	Print(b,n);
	
	int c[10] = {1,2,3,4,5,6,7,8,9,10};
	Memcpy(c,c+5,5*sizeof(int)); //将c的前一半拷贝到后一半 
	Print(c,10);

	char s[10] = "123456789";
	Memcpy(s+2,s+4,5); //将s[2]开始的5个字符拷贝到s[4]开始的地方 
	cout << s << endl;
	
	char s1[10] = "123456789";
	Memcpy(s1+5,s1+1,4); //将s1[5]开始的4个字符拷贝到s1[1]开始的地方 
	cout << s1 << endl;
	
	
	return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

输入
第一行是整数n (1<=n<=10)
第二行是 n个整数
输出
先原序输出输入数据中的n个整数
然后再输出:

1,2,3,4,5,1,2,3,4,5,
123434567
167896789
样例输入
10
15 25 35 45 55 65 75 85 95 105
样例输出
15,25,35,45,55,65,75,85,95,105,
1,2,3,4,5,1,2,3,4,5,
123434567
167896789

// 在此处补充你的代码
	char * pDest = (char *)dest;
	char * pSrc = (char *)src;
	char t[10000];
	for (int i = 0; i < size; i++) {
		t[i] = pSrc[i];
	}
	for (int i = 0; i < size; i++) {
		pDest[i] = t[i];
	}
1
2
3
4
5
6
7
8
9
10

解决了拷贝过程中有重叠的情况，只有用数组作为中转就行。

051 指针练习：MyMax

#include <iostream>
using namespace std;
// 在此处补充你的代码
int Compare1(void * n1,void * n2)
{
	int * p1 = (int * )n1;
	int * p2 = (int * )n2;
	return ((*p1)%10) - ((*p2)%10);
}
int Compare2(void * n1,void * n2)
{
	int * p1 = (int * )n1;
	int * p2 = (int * )n2;
	return *p1 - *p2;
}
#define eps 1e-6
int	Compare3(void * n1,void * n2)
{
	float * p1 = (float * )n1;
	float * p2 = (float * )n2;
	if( * p1 - * p2 > eps)
		return 1;
	else if(* p2 - * p1 > eps)
		return -1;
	else
		return 0; 
}

int main()
{
	int t;
	int a[10];
	float d[10];
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		for(int i = 0;i < n; ++i)
			cin >> a[i];
		for(int i = 0;i < n; ++i)
			cin >> d[i];
		int * p = (int *) MyMax(a,sizeof(int),n,Compare1);
		cout << * p << endl;
		p = (int *) MyMax(a,sizeof(int),n,Compare2);
		cout << * p << endl;
		float * pd = (float * )MyMax(d,sizeof(float),n,Compare3);
		cout << * pd << endl;
	}
	return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

输入
第一行是测试数据组数 t
对每组数据：
第一行是整数n (1<=n<=10)
第2行是 n个整数
第3行是n个浮点数
输出
对每组数据：

先输出n个整数中个位数最大的数(答案保证唯一）
再输出n个整数中最大的数
再输出n个浮点数中最大的数
样例输入
2
5
31 20 100 7 8
30.1 100.2 2.5 9.8 48.4
2
1 2
0.1 0.2
样例输出
8
100
100.2
2
2
0.2

// 在此处补充你的代码
void * MyMax(void * a, int size, int n, int(*f)(void * n1, void * n2)) {
	int * max = (int *)a;
	for (int i = 1; i < n; i++) {
		if (f(max, (int *)a + i) < 0) {
			max = (int *)a + i;
		}
	}
	return max;
}
1
2
3
4
5
6
7
8
9
10

1. void指针转为其他类型指针，再转回void，再转成其他类型指针，数据不会丢失。
   所以比较小数时float→void→int→void→float这个流程数据是不会丢失的。
2. 不同类型的指针因为类型的容量不同，所以进行±操作时，获得的内存地址也不同。
   因为p1 + n=p1 + n * sizeof(T)
   所以把int都替换成float也是正确的。

如果要替换成char，那么只需要在传参和赋值的时候让i乘4即可，代码如下：

void * MyMax(void * a, int size, int n, int(*f)(void * n1, void * n2)) {
	char * max = (char *)a;
	for (int i = 1; i < n; i++) {
		if (f(max, (char *)a + i*4) < 0) {
			max = (char *)a + i*4;
		}
	}
	return max;
}
1
2
3
4
5
6
7
8
9

053 指针练习：SwapMemory

描述
填写内存交换函数 SwapMemory，使得程序输出指定结果

#include <iostream>
using namespace std;
void SwapMemory(void * m1,void * m2, int size)
{
// 在此处补充你的代码
}

void PrintIntArray(int * a,int n)
{
	for(int i = 0;i < n; ++i)
		cout << a[i] << ",";
	cout << endl;
}

int main()
{
	int a[5] = {1,2,3,4,5};
	int b[5] = {10,20,30,40,50};
	SwapMemory(a,b,5 * sizeof(int));
	PrintIntArray(a,5);
	PrintIntArray(b,5);
	char s1[] = "12345";
	char s2[] = "abcde";
	SwapMemory(s1,s2,5);
	cout << s1 << endl;
	cout << s2 << endl;
	return 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
26
27
28

输入
无
输出
10,20,30,40,50,
1,2,3,4,5,
abcde
12345
样例输入
无
样例输出
10,20,30,40,50,
1,2,3,4,5,
abcde
12345

// 在此处补充你的代码
	char t[1];
	char * pM1 = (char *)m1;
	char * pM2 = (char *)m2;
	for (int i = 0; i < size; i++) {
		*t = *(pM1 + i);
		*(pM1 + i) = *(pM2 + i);
		*(pM2 + i) = *t;
	}
1
2
3
4
5
6
7
8
9

借用一个指针进行中转，然后进行内存交换就行。
为什么使用数组？
因为数组的话，它会在内存自动开辟对应容量大小的空间来存放数据。所以可以直接拿来中转。使用指针的话，还需要指向某个变量才能获得一个地址然后使用地址里的空间，比较繁琐，所以我使用了数组。

备注

头文件

1. #include<stdio.h>的头文件是C语言的头文件
   #include<iostream>的头文件是C++的头文件
   都是可以使用标准输入输出流的意思
   前者无法使用cin和cout来输入输出
2. <cstring>是C++的字符串头文件
   <string.h>是C的字符串头文件

运算符优先级(全)

优先级【高到低】：

第一级：圆括号【（）】、下标运算符【[]】、分量运算符的指向结构体成员运算符【->】、结构体成员运算符【.】。

第二级：逻辑非运算符【!】、按位取反运算符【~】、自增自减运算符【++ --】、负号运算符【-】、类型转换运算符【(类型)】、指针运算符和取地址运算符【*和&】、长度运算符【sizeof】。

第三级：乘法运算符【*】、除法运算符【/】、取余运算符【%】。

第四级：加法运算符【+】、减法运算符【-】。

第五级：左移动运算符【<<】、右移动运算符【>>】。

第六级：关系运算符【< > <= >= 】。

第七级：等于运算符【==】、不等于运算符【!=】。

第八级：按位与运算符【&】。

第九级：按位异或运算符【^】。

第十级：按位或运算符【|】。

第十一级：逻辑与运算符【&&】。

第十二级：逻辑或运算符【||】。

第十三级：条件运算符【?:】。

第十四级：赋值运算符【= += -= *= /= %= >>= <<.= &= |= ^=】。

第十五级：逗号运算符【,】。 //逗号表达式的值取逗号中最右表达式的值