初赛杂碎知识点整理

# 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.哈密顿回路 哈密顿回路是指在无向图中，从某点出发，经过所有点恰好一次再回到原点的路径。