Easy Maths
排列组合:
剩余法
对等法
R进制整数表示:
除以基数R,取余,逆序写下
R进制小数表示:
乘以基数R,向下取整,顺序写下
反码补码原码:
反码=绝对值 负数符号位不动,其余按位取反
补码:正数不变,负数为其反码加一得到
逻辑运算(区别于位运算):
v=或……
卡特兰数可以解决:
1.凸N边形三角划分的数量问题
2.给定N个节点,能构成不同的二叉树的数目问题
结果都为Catalan(N)
其前几项为(从第0项开始):1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,
16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790,
477638700, 1767263190, 6564120420, 24466267020, 91482563640......
Catalan图表:
132
42 132
14 42 90
5 14 28 48
2 5 9 14 20
1 2 3 4 5 6
A 1 1 1 1 1 1......
斯特林数:
1.第一类斯特林数
2.第二类斯特林数
Stiring(N)
...
数学期望:
定义:
在概率论和统计学中,数学期望(mathematic expectation)(或均值,亦简称期望)
是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。
需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。
期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。
大数定律表明,随着重复次数接近无穷大,数值的算术平均值几乎肯定地收敛于期望值。
哈夫曼树&哈夫曼编码:
Tips:
1.哈夫曼树是一颗特殊的二叉树
2.任意编码不是其他编码的前缀
STL:
1.集合(set) 顾名思义 有元素 满足集合性质(如互异性等) 支持一般的查询、插入、删除等正常操作
set<elementtype> elements;定义一个元素类型的集合,升序排列
set<elementtype,greater<elementtype>> elements;定义一个元素类型的集合,降序排列
elements.insert(x);插入元素x
elements.erase(x);删除元素x
elements.find(x);查找x,返回x的迭代器,x不存在则返回指向集合elements的尾部迭代器elements.end()
elements.clear();清空集合
elements.size();返回集合的大小(元素个数)
elements.lower_bound(x);返回一个迭代器,指向一个不小于x的元素
elements.upper_bound(x);返回一个迭代器,指向一个大于x的元素
elements.empty();判断集合是否为空集
elements.begin();返回指向集合elements的第一个元素的迭代器
elements.end();返回指向集合elements的最后一个元素的迭代器
set<elementtype>::iterator i; 迭代器名称定义
for(i=elements.begin();i!=elements.end();i++){ 迭代器遍历
int t=*i; 需要返回的值t为迭代器指针i所指向的元素,故为*i
(operations......)
}
2.映射(map) 顾名思义 有关键字 有关键字对应的映射元素
关键字的类型与键值由const限定,无法改变,故存入之后无法修改键值与关键字类型
map<keynodetype, keytype> mymap;定义映射
map<keynodetype, keytype> mymap{ {...} , {...} };
以下为基操:
mymap[keynode]=x;插入 tips:STL中对map的[]进行了重定义,比如keynode可以为一个字符串
mymap.erase(x);
mymap.erase(mymap.begin(),mymap.end());全部删除
for(map<keynodetype,keytype>::iterator i=mymap.begin();i!=mymap.end();i++){
cout<<i.first<<" "<<i.second<<endl;
}
康托展开: 求康托展开值(在n位的全排列中在该排列之前的排列数量)
康托展开
令A1,A2,A3,A4,A5,...,An为一种排列
那么对应的位置编号为n,n-1,n-2,n-3,n-4,...1
求值方式:将每一位 (所在位置的编号-1)! X (比该编号对应排列的数字小的且在之前未出现过的数的数量) 相加即可
那么对应的该排列在全排列中的位置即为 康托展开值+1
逆康托展开:
康托展开值 除以 (所在位置的编号-1)! ,取余数,再用余数除以,如此反复
商即为 在该位置时,剩下未用到的小于该位置对应的数字的数量,如此即刻推理得出该序列的每一位
指针*与取地址符&:
取地址符:
1.定义时类型后加& 表示给另一个变量x取一个别的名字x1,即在x1的位置存放x,两者相互链接
tips:定义格式example:int x=114514; int &x1=x;
2.&的类型必须与变量x一致,否则会 ERROR!!!
指针:
1.基本情况下指针类型都是要与指向的对象类型一致(但const指针可以指向非常量的地址)
2.不能用一个非常量指针指向一个常量类型的地址
3.指针指向对象的地址
tips: int a=114514; int *p=&a;
cout<<p;输出a的地址 cout<<*p;输出指针p所指的地址的值
4.*p++:等同于:*p; p += 1;
*++p:等同于 p += 1; *p;
(*p)++,使用()强制将*与p结合,只能先计算*p,然后对*p整体的值++
++(*p),先*p取值,再前置++,[该值+1后]作为整个表达式的值
++与*优先级相同
举例:
int a[5]={1,2,3,4,5};
int *p = a;
*p++ 先取指针p指向的值(数组第一个元素1),再将指针p自增1;
cout << *p++; // 结果为 1
cout <<(*p++); // 1
(*p)++ 先去指针p指向的值(数组第一个元素1),再将该值自增1(数组第一个元素变为2
cout << (*p)++; // 1
cout <<((*p)++) //2
*++p 先将指针p自增1(此时指向数组第二个元素),*操作再取出该值
cout << *++p; // 2
cout <<(*++p) //2
++*p 先取指针p指向的值(数组第一个元素1),再将该值自增1(数组第一个元素变为2)
cout <<++*p; // 2
cout <<(++*p) //2
标签:elements,指向,迭代,元素,笔记,集合,Easy,Maths,mymap
From: https://www.cnblogs.com/Diamondan/p/16895896.html