时间复杂度

探讨一个算法的实现以及其性能，表示程序运行答题时间。
f(n)指的是一般数据下运行时间的上界，并非一定是最坏情况，所以要注意：

• 数据用例不同时时间复杂度不同。
• 时间复杂度不同时，不同输入数据规模下性能也会有差异（就是函数问题）；O是数据量级非常大的情况下表现出的时间复杂度，所以经常会忽略常数项，所以说决定算法并不是只考虑复杂度越低越好还要综合数据规模
• 化简：只保留最高次（考虑n很大况）
• 注意考虑全面’每次操作’的内涵 eg.字符串比较，有字符串自身长度m，排序后比较比直接比较更优
• 递归的时间复杂度：递归次数*递归中的操作次数；[tips]在递归中要少调用自身函数，建议单独把要调用的函数抽取出来，可以减少时间复杂度(下例时间复杂度n/2)

  1 2 3 4 5 6 7 8 9

  int function4(int x, int n) { if (n == 0) return 1; if (n == 1) return x; int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来 if (n % 2 == 1) { return t * t * x; } return t * t; }

  补充：空间复杂度
  空间复杂度是程序运行时占用内存的大小，不是exe文件本身大小

排序

二分法

快速排序

内置函数：sort(pbegin,pend);

qsort函数compare

qsort(a,n,bytes(type),compare);

• 是相应的数据类型单个变量所占的字节数

Sort double array

1
2
3
4
5
6
7
8
9
10
11

int n;
double a[N];
int compare(const void *e1, const void *e2)
{
    double v1 = *((double *)e1);
    double v2 = *((double *)e2);
	if(v1 > v2) return 1;
	if(v1 < v2) return -1;
	return 0;
}
qsort(a, n, sizeof(double), compare);

Sort long long array

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

int n;
long long a[N];

int compare(const void *e1, const void *e2)
{
    long long v1 = *((const long long *)e1);
    long long v2 = *((const long long *)e2);
	if(v1 > v2) return 1;
	if(v1 < v2) return -1;
	return 0;
}

qsort(a, n, sizeof(long long), compare);

Sort array of char array

1
2
3
4

char buf[100][105];
int n;

qsort(buf, n, sizeof(buf[0]), strcmp);

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

// Sort char* array
char *lines[100];
int n;

int compare(const void *p1, const void *p2)
{
    char *a = *(char **)p1;
    char *b = *(char **)p2;
    return strcmp(a, b);
}

qsort(lines, n, sizeof(char *), compare);

Sort array of int array

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

int data[100][3];
int n;

int compare(const void *e1, const void *e2)
{
    int *p1 = (int *)e1;
    int *p2 = (int *)e2;
	if(p1[0] > p2[0]) return 1;
	if(p1[0] < p2[0]) return -1;
	// You can use p[1], p[2] as well
	return 0;
}
qsort(buf, n, sizeof(data[0]), compare);

数组

哈希表

1. 哈希算法/哈希函数：将任意长度的二进制值串映射为固定长度的二进制值串的映射规则；
   • 其中所依据的目录称为“键”
   • 存放记录的数组称作散列表(Hash Table)
2. 哈希表是根据关键码的值而直接进行访问的数据结构
   • 比方说通过下标(key)访问数组的值时，数组可以视为哈希表,下标与数组存储的值可以成为一个键值对key-value,在jdk中被称为Entry
3. 常用于快速判断一个元素是否出现在集合中（提速）
4. 空间换时间

哈希碰撞

不同数据映射后成为相同的值

解决

拉链法

将冲突的值储存在同一列表当中，再在链表中检索

• 适当选择哈希表大小，减小哈希表可以降内存，缩短链表可以减少时间

线性探测法

要求:tableSize>dataSize

• 寻找空位存放多余数据

常见的三种哈希结构

数组、几何、映射

集合（set）

vscode使用

1. c语言程序窗口执行到scanf函数出现闪退

可在头文件加上#include，main函数里return上面加上system(“pause”); 可防止程序窗口闪退

2. c++直接加system(“pause”);

数据处理

数的编码

原码：最高位为符号位（0为正数 1为负数） 其余各位表示数本身的绝对值
反码：正数的反码与源码相同 若为负数 其绝对值的原码的各位取反
补码：正数的原码、反码和补码都相同 若为负数 则用模数加上该负数 也就是对其反码加1（若有进位则进位舍弃）

5
2003.24.04 11:11
2339.02.29 11:11
2400.02.29 11:11
2339.02.29 11:11
8561.12.90 24:00

恼

1. 符号字符可以直接用hhd输入 无符号u unsigned long long llu
2. int转化为long long（尤其是在加和乘中会经常遇到）时要
3. 一些常见的超大数字
   long long c=0x7fffffff;
   unsigned int d=2147483748;
   int占用4字节，32比特，数据范围为-21474836482147483647 -2^ 312^31-1 10
4. 有除法先讨论0 以及是整数吗 如果发现就是浮点数的运算非必要一定不要出现整除的nt行为（）
   • 但是在比较大小的时候，可以出现除以0，认为是“无穷”即可
5. math函数返回double类型 不要强制转换
6. 存在整形相乘时，注意及时修改中间变量类型，避免数据溢出（二分法找x的平方根）
7. 输出百分号是 %% -如何输出%%? That's imp0ssib1e百分号输出有两个！两个！
8. unsigned int不要用int!一定要全用这个类型！范围不一样！
9. c语言中没有布尔型运算 要输入头文件#include<stdbool.h>
10. 好好扫描他的输出，看看是不是输入坐标也有br的cd空格
12. 浮点数判断大小
13. 注意数据类型 尤其是题给函数 加乘开大 除法看是否浮点数
14. 整除问题标记是否为0（eg连分数）
15. 开数组之前可以思考一下 比方说矩阵的加法 其实不一定非得要开两个数组 或许可以直接计算出结果
16. 余子式新矩阵的下标错了捏
17. 四舍五入输出 加0.5后强制整数阶段转换

基础知识&语句

输出

cout

• 可以智慧地识别出数据类型，不需要人为指定。

  1	cout << carrots;

printf用法小全

%[标志][最小宽度][.精度][类型长度]type
%S可以打印宽字符串 以两个’\0’为结尾
%e``%E输出科学计数法

-结果左对齐 右边填空格 默认右对齐 左边填空格
+输出符号
0输出前补0直到占满给定列宽
#对八进制和十六进制加前缀 对ef强制输出小数点

printf("%*d",m,1000)可以指定输出最小宽度m
printf("%.*f",m,1000)可以指定输出精度m 整数会自动补0 字符串超过指定长度截断
判断一个数是否为整数并依此保留精度不同printf(“%.*lf\n”,(fabs(ave-(int)ave))<1e-6?0:2,ave);

一些细碎的知识点

数据处理

1. 常用数据类型以及存储范围(单位：字节，一个字节是8位即$2^8$)
   char 1
   short int 2
   (unsigned)int 4 -21474836482147483647 -2^ 312^31-1
   long logn 8 2^ 63
   float 4
   double 8
2. C++提供了一种灵活的标准，确保最小长度

• short不短于16
• int不短于short
• long不短于int，至少32位
• long long不短于long，至少64位
• float至少32位，都变了至少48位（double通常位64位）

3. const限定，在建立变量的同时要对其赋值，否则该常量值不定且无法修改

• 常量存储小数默认使用double类型，如果想得到浮点加后缀f/F，想得到long double加后缀l/L

4. 浮点数表示的范围大于整数，但是运算速度和精度会有所降低

• eg.float类型的数字1.23e+23，对其加1输出不变，因为float只能表示前七位，因而第23位变化对这个值不会有任何影响

基础语句

2. 逻辑语句

• &&优先级大于||
• a<b<c中 关系运算符是左结合的 实质是只要c大于1 该式恒成立

3. 条件运算符

   z=(a>b)?A:B

一个复杂的嵌套举例：根据变量的值输出ab大小关系的陈述语句

printf(“a is %s b”, (a>b) ? “greater than” : (a<b) ? “less than” : “equal to”)

4. switch语句

   1 2 3 4

   switch (n){ case0: ;break; case1: ;break;.... }

   不同的case可以共享同一组语句序列和打印结果 可以写在同一行

5. 函数

6. 格式

   类型名 函数名（参数列表）
   {
   函数体
   }

7. 声明（函数本体可写于程序最后）去掉函数体后加分号

8. 赋值语句：可以连续使用，从右到左赋值

复合类型

数组基础

1. 数组是存放在连续内存空间上的相同类型数据的集合
2. 只能覆盖，无法删除
3. 对于一维数组，内存空间的地址是连续的
4. 对于二维数组，地址并非连续的矩阵，而是row个连续的内存条
5. sizeof()表整个数组所占字节数（字节数/类型长度=数组元素数），如果作用于数组元素，得到以字节为单位的长度
6. int a[10]={1,2,3,4,5},i其中i为偏移量，部分初始化时其余元素为0；只有{}时全设为0；初始化时=可省略
   数组访问中数组名作为表达式的值等于该数组的首地址

一维数组

二分法

1. 有序数组
2. 元素唯一
3. 关键是确定区间两端的开闭
4. 时间复杂度O(log n)；空间复杂度O(n);
   eg. 左闭右闭

   1 2 3

   while(l<=r) r=mid-1; l=mid+1;

字符串

• 需要以空字符\0标记结尾
• 一种简练初始化的方法,

  1	char tag[] = "I'm Gamer";

基本操作

1. 拼接：cout会把两个用空格、换行符、制表符分隔的字符串直接合并为一个
2. strlen返回字符串长度，只计算可见字符，忽略空字符

• 因而数组长度的长度要加1

3. .size()可以获取vector类型的长度

string类

1. 可以将字符串声明为简单变量
2. 最初创建的是一个长度为0的string对象，读入之后，可以自动调整该对象的长度，但是最后不会加空格

   1 2 3 4 5

   #include<string> string str1; string str2 = "panther"; //创造一个初始化过的string对象 //类似数组初始化： string str2 = {"panther"}; cin >> str1; //会自动调整大小

3. 可以将一个string对象赋给另一个string对象（数组不能）
4. 可以使用“+”拼接字符串到末尾
5. string变量要在主函数中建立
6. .length()获取字符串长度
7. 简单遍历对比

输入

cin输入

* 使用空白（空格、制表符、换行符）确定字符串结束的位置
* 输入之后，cin把字符放到数组中，自动在结尾添加空字符

面向行的输入

getline()

1. 回车键输入的换行符来确定输入结尾
2. cin.getline(name,length+1)两个参数调用
3. 不保存换行符，更换为空字符

get()

1. 保留换行符，存储队列
2. 把输入中连续的两航存储在两个数组中:

   1	cin.getline(name1, length).getlinie(name2, length);

3. 可以根据get()的输出来检查错误，是数组溢出还是正常换行

对比~

%c输入要注意前边加一个空格把所有空格吃掉

scanf("%[^\n]",str);读入一行不包括行尾换行符的字符串作为带查找的字串

getchar()只在回车处停
putchar()输出字符的速度更快,输出的是字符,所以括号里有数字时会自动转换ASCII值
putchar(10)换行

n均可省略

输入数组就不要加&和[i]

存储日期 定义并竖着初始化日期名 列保证大于最长字符串长度

询问操作

比较字典序 实际上指针指向的是该地址以后的字符串
比较strcmp(str1,str2,num)相等返回0 小于返回负数 大于返回正数 均视为无符号字符

复制memcpy(destination, source,num)返回destination 只负责赋值num个字节全部复制建议用sizeof(source) 不会检查NULL指针
此函数为内存复制函数

查找memchr(str,s,num)在str的前num位中寻找s 返回一个unsigned字符 表示下标（%d）输出即可 找不到返回NULL

strchr(char *str,int c) 在str中查找c首次出现的位置的指针
strrchr(char *str,int c) 在str中查找c最后一次出现的位置的指针

strstr(char *str,char *s1) 在str中查找s1首次出现的位置的指针

查找子串出现的次数

1
2

for(char *p=strstr(str,s);p!=NULL;p=strstr(p+1,s))
    sum++;

输出子串区间

1
2
3
4
5
6
7
8

char *p=str;
int len=strlen(s);
while((p=strstr(p,b))!=NULL)
{
    int idx=p-a;
    int r=idx+len-1;
    p+=len;
}

修改操作

s+i表示的就是字符串s的第i个字符 也表示自第i个字符向后（包括第i个）

删除第i个字符以后的内容

实现指定位置字符串截断 将截断第一位换成’0’后面就不会输出啦

1

str[i]='\0';

使用\0相当于截断

删除一个字符串的第i位到第j位

1

strcpy(str+i,str+j+1);

将s插入到str的第i位之前，后边的字符向后顺移

1
2

strcat(s,str+i);
strcpy(str+i,s);

从 str 的第i位开始用s覆盖

覆盖指从第i位开始，将str的字符依次替换为s的字符，如果str长度不够，则向后延长直到s结束，如果长度不到str结尾，则后续字符保留str原字符

1
2
3

int len=strlen(s);
if(len<strlen(str)-i)  memcpy(str+i,s); 
else strcpy(str+i,s);

char strcpy(char dest, const char *src);
功能：把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间
用法：strcpy(s,t);
strcpy会复制\0而memcpy不会
拷贝函数源地址和目标地址不能有任何重叠

char *strcat(char *dest,char *src);
功能：把src所指字符串添加到dest结尾处(覆盖dest结尾处的’\0’)并添加’\0’
用法：strcat(s,t);
strcpy(char *dst,const char *src) 将src复制到dst中
strncpy(char *dst,const char *src,size_t n)

strcat(char *dst,const *src) 将字符串src追加到字符串dst后
strncat(char *dst,const *src，size_t n)

容器

map

普通map

1. 头文件

   1	include <map>

2. 定义&初始化

   1 2 3 4 5 6 7 8

   map<keytype,valuetype> name; //假设存在map名为m map<keytype,valuetype> m2(m); //创建了m的副本m2 map<keytype,valuetype> m3(m.begin(),m.end()); //创建了map的对象m3，存储迭代器内指定范围的Entry（此处是整个m） std::map<std::string, int> mymap = { {"alpha", 0}, {"beta", 0}, {"gamma", 0}};//初始化

元素访问

• 下标[]和at()操作只能用于非const的map和unordered_map
• []访问不会做下标检查，对于不存在的key会设定value为默认值（一般为空/False）
• at()访问会做下标检查，不存在key时报错

  1 2	mymap[key] = value; mymap.at(key) = value;

元素修改

1. 下标[]

• 用下标访问不存在的元素会自动添加，用下标访问存在的元素时会覆盖原元素

2. insert()

   1 2 3 4 5 6 7 8 9 10 11

   //插入单个值 map.insert(pair<keytype,valuetype>(key,value)); map.insert(make_pair(key,value)); //指定位置插入，不同位置的效率不同，涉及到重排 std::map<char, int>::iterator it = mymap.begin(); mymap.insert(it,std::pair<keytype,valuetype>('b',300)); //范围内多值插入 std::map<keytype,valuetype>map2; map2.insert(mymap.begin(),mymap.end()); //列表形式插入 map2.insert()({{'d',100},{'e',200}});

   注意，insert插入位置已经存在值时，插入失败，value保持原值。
3. erase()

   1 2	mymap.erase(0);//删除key为0的元素 mymap.erase(mymap.begin());//删除迭代器指向的位置元素

4. count(k)
   查找关键字k出现的次数
5. find(k)
   查找元素，存在时返回指向该key的迭代器；不存在时返回迭代器的尾指针，即mymap.end()/-1;

unordered_map

• 所有元素都是pair（对组）
• pair中第一个元素为key，做索引；第二个元素为value;
• 不允许有重复元素，自动开链法储存
• 底层结构是哈希表

修改操作

访问操作

循环map，获取每个键值对的key和val

1
2
3
4
5

actor<vector<string>> ans; //建立一个容器，用于储存结果
for(unordered_map<string,vector<string>>::iterator it=mp.begin();it!=mp.end();it++)
//unordered_map<string,vector<string>>::iterator 等价于auto
ans.push_back(it->first);//获取key
ans.push_back(it->second);//获取val

vector(向量类型)

一个很好的入门教程

• 是一种容器，可以容纳许多类型的数据
• 动态数组，封装好的类
• 头文件#include<vector>

初始化

尖括号内可以是任何合法的数据类型

结构体

基本操作

1. 定义

   1 2 3 4

   typedef struct sentence{ int l,x; char s[10005]; }sen;

2. 初始化
   {}来初始化，空括号可以将每个元素置为0；
3. 不允许缩窄转换

排序

其中sen为类型名 x为比较量

只是用于整数大小比较

int compare(const void *e1, const void *e2)
{
return ((sen *)e1)->x - ((sen *)e2)->x;
}
qsort(name, n, sizeof(type), compare);

浮点型+字符串比较

1
2
3
4
5
6
7
8

int compare(const void *e1, const void *e2)
{
	if((((star *)e1)->d - ((star *)e2)->d)>eps)
		return 1;
	else if((((star *)e1)->d - ((star *)e2)->d)<-eps)
		return -1;
	else return strcmp(((star *)e1)->s,((star *)e2)->s);
}

共用体(Union)

与结构体的区别：共用体只能存储其中一个，在给其中一个变量赋值之后，其余变量的值自动丢失。

• 数据使用多种格式，但不同时使用时，可以节省空间。比如说商品ID中有字符串有数字。
• 主要用途就是节省空间，嵌入式系统里用的多

1. 变量建立

   1 2 3 4 5 6

   union one4all { int int_val; long long_val; double double_val; }

2. 赋值语法与调用与结构体相同

位运算

整型中不会发生数据溢出
对于十六进制 一个f相当于二进制中一个字节1111 如果要批量处理数据的话用十六进制会更简单 一样的东西 把操作的数字变成0x····

正负数判断 看最左侧的一位 0为正 1为负

n&=(n-1)消去最低位的1 用于统计一个二进制数中1的个数

&

1. 对整数x的特定位清0 ：取操作数a使其特定位为0 其余位为1 然后&

   1 2	a=((1<<m)|(1<<n)....) x=x&(~a)

2. 判断奇偶性 ： 看最后一位是1还是0
   在看某一位是1还是0的时候直接用操作&计算 看等不等于0 让他进入循环就可以

   1	if((a&1)==1) 奇数

|

1. 将一个数的特定位设为1

   1 2	a=a=((1<<m)|(1<<n)....) x=x|a

^

对一个数的特定位数进行取反

~

3=4
`x&1将一个数x的最低位置0 其他位不变 ~n+1`对一个整数取相反数
· 这是一个对数字的操作 优先级最高

1. 输出二进制数表达

   1 2 3 4 5 6 7 8

   printf("0B")#或者0b while(x!=0) { printf("%lld",~(x%2)); x=x/2; } if(x%2==0) printf("1"); else printf("0");

   八进制前要加0 十六进制前要加0X或0x
2. 一个数的某些位设为0

   1	x=x&~(1<<m)

< >

将一个数的二进制左右移动 多者溢出
· 在不溢出的情况下 左移一位*2 右移一位/2
左移是很有效的乘二运算
· 对有符号数 左补符号位（算数位移：负数情况下补1）

1. 求平均值(x+y)>>1
2. 求2的n次方（很快而且不会超界）1<<n

综合实例

常用(x>>i)&1获得一个数的补码各位 i从0开始由低到高获得
注意操作对象是补码还是二进制数 如果是二进制数要手动转 不过如果是unsigned int就没事了 但是在相加运算时必须要使用同种类型 否则会超界
注意超界 如果要用longlong应当加后缀1ll

1. 特定位设置
   将二进制的某一位置1

   1	num|=1<<i;

   置0

   1	num&=-(1<<i);

   构造一个前i位均为1的数

   1	int num=(1<<i-1);

把一个无符号整数a的七至十七位赋值为937 21至25位赋值为17

1
2
3
4
5
6

unsigned int a = 0XC305BAD3
a & =~(((1<<11)-1)<<7)//transform 7~17 to 0 and save others
a|=937<<7//赋值
a&=~(((1<<5)-1)<<21)
a|17<<21
printf("a = 0X%X",a)

2. 交换一个数的高位与低位

   1 2 3 4

   unsigned int n; cin>>n; cout<<(n>>16)+(n<<16); # or cout<<((n&0xffff0000)>>16)+((n&0x0000ffff)<<16);

3. 利用按位运算的性质处理数据(一个也不能少)
4. 得到一个数的补码(可补前导0版 以八位为例)
   计算机本身存储的就是补码 所以直接对二进制的存储进行检查就可以！ 所有对二进制的按位操作都是对补码操作！

   1 2	for(int i=7;i>=0;i--) printf("%d",(x>>i)&1);#自左向右检查每一位是否为0

   补码翻转得到新的数

   1 2 3

   for(int i=0;i<=7;i++) ans|=((x>>i)&1)<<(7-i); printf("%hhd",ans);

5. 反码计算机
   正负数分离
   化归思想 把所有负的都转成正的
   如果是正数，本身就是反码，如果是负数，直接对对应正数取反就能得到反码
   重点是“得到一个数的反码” 对数本身操作

   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

   int n,a,b; void print(int k) { if(k>=0) printf("%d\n",k); else { printf("-%d\n",~k); } } int main() { if(scanf(" -%d",&a)) a=~a; else scanf("%d",&a); if(scanf(" -%d",&b)) b=~b; else scanf("%d",&b); print(a&b); print(a|b); print(a^b); return 0; }

数的编码

原码：最高位为符号位（0为正数 1为负数） 其余各位表示数本身的绝对值
反码：正数的反码与源码相同 若为负数 其绝对值的原码的各位取反
补码：正数的原码、反码和补码都相同 若为负数 对其反码加1（若有进位则进位舍弃）

指针

注意

指针运算时要加括号 保证先运算再解引用
指针计算注意不要越界！
指针相减：计算偏移量
指针相加无意义 指针二分mid=low+(high-low)/2
前排指针小

错过的结构设计

2. 在立flag以及数据初始化的时候改变操作要放在判断操作以后
   （eg.驼峰命名法转换 先确定flag是1否 后判定下划线 判断完后要恢复）
3. 异或运算规律：只看1的个数 奇数个1异或是1 偶数个1异或是0 0异或结果都是0

一些规则

循环不变量

二分查找：区间定义

递归、搜索与回溯算法

框架一

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

int search(int x)
{
  for(int i=1;i<=算符种数n；i++)
   if(satisfy)
   {
      secure the result(include 'x')
      if(x==n-1)
       print the result
      else search(x+1) //继续进行这个元素后的排列
      recover(satisfy to enter the if) 
   }
}

框架二

1
2
3
4
5
6
7
8
9

if(reach the goal print)
else
 for(int i=1;i<=n;i++)
 if(satisfy)
  {
    secure the result 
    search(x+1)
    recover
  }

Examples

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

   char s[10],ch[10]; int n; bool p[10]; void search(int x) { for(int i=0;i<n;i++) if(p[i]==0) //该字符未参与排列 { p[i]=1; //标记该位置的字符已经参与排列 ch[x]=s[i]; //存储字符 if(x+1==n) //字符串是从0开始记 此时所有位置的字符已经排列完毕 cout<<ch<<endl; else search(x+1); //让下一个字符作为后一个排列的第一个进行全排列 p[i]=0; //只有本排列中参与的字符才会标记为已参与 } } int main() { cin>>s; n=strlen(s); search(0); return 0; }

2. 最大公因数gcd

   1 2	int gdc(int m,int n) //前提：n＞m 条件-真-假 {return n%m==0?m:gdc(m,n%m)} //n与m和m与n%m公因数相同捏

3. 爬楼梯
   法一 找出基础方法 每层递归一直计数到底层
   实际上仍带有p[x]判定

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

   int n,p[x]; int t(int x) { if(p[x]) return p[x]; //如果本层走法数已算出 直接返回走法 if(x==1) return p[x]=1; if(x==2) return p[x]=2; return p[x]=t(x-1)+t(x-2); //每一层走法数=少一层全走法数+少两层全走法数 } int main() { scanf("%d",&n) //在一直有输入的情况下持续循环 cout<<t(n)<<endl; return 0; }

   法二 实际上是直接累加

   1 2 3 4 5 6

   void t(int x) { if(x==1) ans++; if(x==2) ans+=2; else t(x-1),t(x-2); }

4. 汉诺塔问题

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

   int n,f[25],ans,x; char a,b,c; char t(int n,char a,char b,char c) { if(n>1) t(n-1,a,c,b); cout<<a<<"->"<<n<<"->"<<b<<endl; if(n>1) t(n-1,c,b,a); } int main() { cin>>n>>a>>b>>c; t(n,a,b,c); return 0; }

5. c数简单递归 但是记忆

   1 2 3 4 5 6 7 8 9 10 11

   long long ans,x[20]; long long c(int n) { long long sum=0; if(n==0 || n==1) return 1; if(x[n]) return x[n]; for(int i=0;i<n;i++) sum+=1ll*c(i)*c(n-i-1); x[n]=sum; return sum; }

肖老师说

局部视角在于数数 整体视角在于坐标
注意分解问题
数学问题建议下标与平时习惯一致

常量重在表达 变量重在类型
整型重在范围 浮型重在精度
函数重在接口 递归重在调用
内存重在管理 区分数组指针

int sprintf(charbuf,charformat[,argument]…);
例：
int m;
double x;
char buf[32];
scanf(“%lf%d”,&x,&m);
sprintf(buf,”%%.%df\n”,m);
printf(buf,sin(x));
printf是按格式把输出送到屏幕上
sprintf是按格式把输出送到buf对应的字符数组中
sprintf常用于需要动态生成字符串的场合

int sscanf(const char *buf, char *format [, arg]…);
例：
int day, year, h, m, s;
char mon[4], zone[6];
char buf[] = “12/Nov/2020:12:15:00 +0800”;
sscanf(buf, “%d/%3c/%d:%d:%d:%d %s”, &day, mon, &year, &h, &m, &s, zone);
mon[3] = ‘\0’; // 什么作用？
printf(“%d\n%s\n%d\n%d\n%d\n%d\n%s”, year, mon, day, h, m, s, zone);
scanf 是按要求的格式从键盘输入数据到对应的地址（变量地址或数组）
sscanf 是按要求的格式从 buf 读入数据（也是在<stdio.h>里定义）
返回值也是成功读入的字段数，一般弃之不用