看什么看?卢娜姐姐永远是我的!

初赛杂碎知识点整理

2020-10-09 11:02:18


1.逻辑运算符

1.1. $\vee$

双目运算符,相当于or

$P$ $Q$ $P \vee Q$
1 1 1
1 0 1
0 1 1
0 0 0

1.2. $\wedge$

双目运算符,相当于and

$P$ $Q$ $P \vee Q$
1 1 1
1 0 0
0 1 0
0 0 0

1.3. $\lnot$

单目运算符,相当于not

$P$ $\lnot P$
1 0
0 1

1.4. $\to$

中文名称:蕴含, $P \to Q$只有P=1,Q=0时为0。

这个涉及到命题的一些知识。

如果P能推出Q,那么我们认为P是Q的充分条件,Q为P的必要条件。

如果P成立,Q成立, $P \to Q$自然成立

如果P不成立,无论Q成立与否,都是合理的, $P \to Q$也为真

但是如果P成立,Q却不成立, $P \to Q$自然无法成立, $P \to Q$为假

$P$ $Q$ $P \to Q$
1 1 1
1 0 0
0 1 1
0 0 1

1.5. $\leftrightarrow$

中文名称:等价, $P\leftrightarrow Q$相当于 $[P=Q]$

这个也涉及到命题的一些知识。

如果P能推出Q,Q也能推出P,那么我们认为P、Q互为对方充分必要条件。

所以只有同真同假才为真,否则为假。

$P$ $Q$ $P \leftrightarrow Q$
1 1 1
1 0 0
0 1 0
0 0 1

2.原码反码补码

2.1.原码

原码是最简单的机器数表示法,原则是第一个二进制位0为正数,1为负数;其余位则是普通二进制表示。

CSDN上搞的图片,侵权删除

2.2.反码

正数的反码等于原码,负数的反码是该数原码按位取反的结果(除符号位除外)。

CSDN上搞的图片,侵权删除

2.3.补码

正数的补码仍然等于原码,负数的补码等于该数的原码自低位向高位,尾数的第一个‘1’及其右边的‘0’保持不变,左边的各位按位取反,符号位不变。(或者可以简单理解为负数的补码等于该数的反码+1)

2.4.纯小数

纯小数则是小数点前为符号位,但是小数点后都按照无符号位的负数处理

N/A 原码 反码 补码
-13/64 1.001 1010 1.110 0101 1.110 0110
29/128 0.001 1101 0.110 0010 0.110 0011

3.主定理

如果有递推关系式 $T(n)=a\times T(\frac{n}{b})+f(n)$,其中 $n$为问题规模, $a$为递归子问题的数量, $\frac{n}{b}$为 每个子问题的规模, $f(n)$为除递归以外的计算工作。

如果 $a>=1,b>1$且均为常数, $f(n)$为函数, $T(n)$为非负整数,则有以下结论:

  • 若 $f(n)=O(n^{log_b a-\epsilon})$,且 $\epsilon>0$,那么 $T(n)=\Theta(n^{log_b a})$

  • 若 $f(n)=\Theta(n^{log_b a})$,那么 $T(n)=\Theta(n^{log_b a}log\ n)$

  • 若 $f(n)=\Omega(n^{log_b a+\epsilon})$,且 $\epsilon>0$,且对于某个常数 $c<1$以及所有充分大的n都有 $a\times f(\frac{n}{b})<=c\times f(n)$,那么 $T(n)=\Theta(f(n))$

4.哈密顿回路与欧拉回路

4.1.哈密顿回路

哈密顿回路是指在无向图中,从某点出发,经过所有点恰好一次再回到原点的路径。