Hehy's Blog

离散数学 Discrete Mathematics

part 3 Number Theory 数论

basic knowledge 基础知识

• Let $Z$ be the set of integers. Let $a,b\in Z$ and $a\neq 0$

  • a devides b (整除): there is an integer $c\in Z$ such that $b=ac$
    • a is a divisor（因子）of b;b is mutiple of a
    • $a \mid b$: a divides b ;$a\nmid b$: a does not divide b
  • $n \in {2,3,\ldots}$is a prime if the only positive divisors of n are 1 and n.
  • if n is not a prime , n is a composite（合数）（不讨论0,1）
  • 素数无穷多构造。N=最大素数以下所有数字素数只和加一，和所有已知素数互质，矛盾。

• The Well-Ordering Property良序公理：

  ​ every non-empty subset of $N(Z^+)$ has a least element .$//\forall S\in p(N) \backslash {\emptyset},\exists s_0\in S$ such that $s_0\leqslant s$ for all $s \in S$.

• Division Algorithm带余除法:

  ​ let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.

  prove:

  • existence:

    let $S=\{a-bx:x\in Z \ and\ a-bx\geqslant0\}.$Then$S\neq \emptyset \ and\ S \subseteq N$,$S$ has a least element , say $r=a-bq\geqslant0$

    ​ if $r\geqslant b$,then $r-b=a-b(q+1)\in S$ and $r-b<r$.The contradiction shows that $0\leqslant r<b.$

  • uniqueness:Suppose that $q’,r’\in Z，0\leqslant r’<b$ and $a=bq’+r’$

    ​ Recall that $a=bq+r,0\leqslant r<b$.Then $b(q-q’)=r’-r\in (-b,b)$. It must be the case that $q=q’$ and thus $r=r’$.

• mod: a mod b is defined as r(let $a,b\in Z$and b>0.Then there are unique integers q,r such that $0\leqslant r<b$ and $a=bq+r$.)

• $\lfloor \alpha \rfloor$:floor of $\alpha$,$\leqslant \alpha$

• $\lceil \alpha \rceil$:ceil of $\alpha$,$\geqslant \alpha$

• Greatest Common Divisor(GCD):

  • common divisor 公因子： a integer d such that $d|a,d|b$

  • greatest common divisor 最大公因子（GCD）,gcd(a,b) : the largest common divisor of a,b

  • relatively prime 互素：gcd(a,b)=1

  • $\exists s,t\in Z,st\ gcd(a,b)=as+bt.$

  • $d=gcd(a,b)=gcd(a/d,b/d)=1$

  • 计算gcd，辗转相除法，

  • properties :

    or 可兼有的或 \lor

• theorem(Congruence): Let $n\in Z^+$. For any $a\in Z$, there is a unique integer $r$, such that $0\leqslant r< n$ and $a\equiv r \pmod n$.

  prove:

  • Existence: by division algorithm,$\exists q,r\in Z$ such that $0\leqslant r<n,a=qn+r$

    ​ $a\equiv r\pmod n$

  • Uniqueness:Suppose that $0\leqslant r’ <n$ and $a\equiv r’\pmod n$

    ​ $|r-r’|<n$ and $r\equiv r’\pmod n$

    ​ $|r-r’|<n$ and $n|(r-r’)$

    ​ $r=r’$

• 加减乘除法时间复杂度

• Prime Number Theorem : for $x\in R^+,\pi(x)=\sum_{p\leqslant x }1$:the number of primes $\leqslant x$

  • 

  • 

    Fundamental Theorem of Arithmetic （算术学的基本定理）

• theorem: every intr=eger n>1 can be uniquely written as $n=p_1^{e_1}\cdots p_r^{e_r}$,where $p_1,\dots,p_r$ are distinct primes ,$p_1<\cdots <p_r$ and $e_1,\ldots,e_r \geqslant 1$.

• prove: 第二类数学归纳法 mathematical induction

  • existence:

    • 显然n=2,3,4,5满足

    • 假设n$\leqslant$k满足, Induction hypothesis: suppose true for integers $2\leqslant n \leqslant k$

    • Prove the statement for n=k+1

      • if(n=k+1 is a prime） $n=(k+1)^1$ QED

      • else n=k+1 is composite ,$n=n_1n_2$,by introduction hypothesis，

        $n1=p_1^{\alpha_1 }\cdots p_r^{\alpha_r},n2=q_1^{\beta_1 }\cdots q_s^{\beta_s}$

        $n=n_1n_2=p_1^{\alpha_1 }\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1 }\cdots q_s^{\beta_s}$has the expected form.

  • uniqueness:

    • Suppose that $n=p_1\cdots p_r=q_1\cdots q_s$,where $p_i,q_i$ are all primes.
    • $p_1|n \Rightarrow p_1|q_1\cdots q_s \Rightarrow p_1|q_j$ for some $j\Rightarrow p_1=q_j$
    • Without loss of generality, we suppose that j=1
    • Then $p_2\cdots p_r=q_2\cdots q_s$
    • The theorem is true by induction

Ideal 理想

• Definion:Let $\emptyset \neq I \subseteq Z$.I is called an ideal of Z if

  • $a,b\in I\Rightarrow a+b\in I$;and
  • $a\in I,r\in Z \Rightarrow ra\in I$

• example:$kZ={\ldots , -2k,-k,0,k,2k,\ldots}$is an ideal of Z for every $k\in Z$

  • theorem:Let I be an ideal of Z. Then $\exists d \in Z$ such that $I=dZ$
    • prove:

• Definion:Let $I_1,I_2$ be ideals of Z. Then the sum of $I_1$ and $I_2$ is define as $I_1+I_2={x+y:x\in I_1 ,y\in I_2}$

• theorem:$I_1+I_2$ is an ideal of Z

  • $$\forall a,b\in I_1+I_2,a+b\in I_1+I_2$$
    • $\exists x_1,x_2\in I_1,y_1,y_2\in I_2$ such that $a=x_1+y_1;b=x_2+y_2$
    • $$a+b=(x_1+x_2)+(y_1+y_2)\in I_1+I_2$$
  • $$\forall a \in I_1+I_2 ,r\in Z ,ra\in I_1+I_2 $$
    • $\exists x\in I_1,y\in I_2$ such that $a=x+y$
    • $ra=(rx)+(ry)\in I_1+I_2$

• example:$3Z+5Z=Z;4Z+6Z=2Z$

• $aZ+bZ=gcd(a,b)Z$

  prove:

  PS: w.l.o.g.:without loss of generality (不失一般性)

二元关系指，R是A$\times$B 的子集，具体我感觉怪怪的，不是很明白。

Congruence

• definition: Let $a\in Z ,n\in Z^+$

  $[a]_n=a+nZ={a+nx:x\in Z}$ is called the residue class 剩余类of $a$ mod $n$

  any element in this class is called a representative代表元.

• example: n=6,$[0]_6={\ldots,-12,-6,0,6,12,\ldots};[1]_6={\ldots,-11,-5,1,7,13,\ldots}$

• 

$Z_n,Z_n^*$

• $Z_n$:

  • Define: Letn be any positive integer. $Z_n$ is defined as the set of all residue classes modulo n.

  • $Z_n={[0]_n,[1]_n,\ldots,[n-1]_n}={[1]_n,[2]_n,\ldots,[n-1]_n,[n]_n}=\cdots$

  • • addition: $[a]_n+[b]_n=[a+b]_n$
    • subtraction:$[a]_n-[b]_n=[a-b]_n$
    • multiplication:$[a]_n\cdot [b]_n=[a\cdot b]_n$

  • Remark(well-defined):if $a\equiv a’\pmod n$ and $b\equiv b’\pmod n$,then$a\pm b\equiv a’\pm b’\pmod n$ and $ab=a’b’\pmod n$.

  • Hence,$[a]_n\pm [b]_n=[a’]_n+[b’]_n;[a]_n\cdot [b]_n=[a’]_n\cdot [b’]_n$

  • • $$
      a\equiv a’\pmod n\Rightarrow n|(a-a’) \Rightarrow \exists x \ such\ that\ a-a’=nx\
      b\equiv b’\pmod n\Rightarrow n|(b-b’) \Rightarrow \exists x \ such\ that\ b-b’=ny\
      (a+b)-(a’+b’)=nx+ny\
      (a-b)-(a’-b’)=nx-ny\
      ab-a’b’=a(b-b’)+b’(a-a’)=any+b’nx
      $$

• $Z_n^*$:

  • inverse:Let $n\in Z^+$ and let $[a]_n \in Z_n$.$[s]_n\in Z_n$ is called an inverse of $[a]_n$ if $[a]_n[s]_n=[1]_n$.
  • division:if $[a]_n$ has an inverse $[s]_n$,define $\frac{[b]_n}{[a]_n}=[b]_n\cdot [s]_n$
  • theorem: Let $n\in Z^+$.$[a]_n\in Z_n$ has an inverse if and only if $gcd(a,n)=1$
    • Only if: $\exists s\ s.t.[a]_n[s]_n\equiv [1];\exists t,as-1=nt;gcd(a,n)=1$
    • if:$\exists s,t\ s.t.as+nt=1;as\equiv 1\pmod n$
  • Let $n\in Z^+$.Define $Z_n^*={[a]_n\in Z_n:gcd(a,n)=1}$
    • if n is prime ,then $Z_n^*={1,2,\ldots,n-1}$
    • if n is composite ,then $Z_n^*\subset Z_n$
    • example:$Z_5^*={1,2,3,4};Z_6^*={1,5}$

      Euler’s Phi Function ($\phi (n)$)

• $\phi(n)=|Z_n^*|$ for every $n\in Z^+$ ($\phi (n)$ is the number of intergers $a\in [n]$ such that $gcd(a,n)=1$)

• property:

  • if p is a prime, then $\phi(p^e)=p^{e-1}(p-1)$ for any $e\in Z^+$
    • prove:let $x\in [p^e]$. Then $gcd(x,p^e)\neq 1$ iff$p|x$ iff$x=p,2p,\ldots,p^{e-1}\cdot p$
    • $\phi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)$
  • if n=pq for two different primes p and q ,then $\phi(n)=(p-1)(q-1)$.
    • prove容斥: $A={1,2,\ldots,pq},A_p={x\in A:p|x},A_q={x\in A:q|x}$
    • $Z_n^*=A-A_p\cup A_q$
    • $|Z_n^*|=|A-A_p\cup A_q|=|A|-|A_p\cup A_q|=|A|-|A_p|-|A_q|+|A_p\cap A_q|=(p-1)(q-1)$

• Euler’s Theorem:Let $n\geqslant1$ and $\alpha \in Z_n^*$. Then$\alpha^{\phi(n)}\equiv 1 \pmod n$

• 
  

• Fermat’s Little Theorem:if p is a prime and $\alpha \in Z_p$. Then $\alpha^p \equiv \alpha \pmod p$.

• • This is a corollary of Euler’s theorem for $n=p$

Cryptography_rsa

• 1. 凭空产生两个质数$p,q$
  2. 设$N=p \times q$
  3. 根据欧拉函数$r=\phi(N)=(p-1)(q-1)$
  4. 凭空产生一个小于r的整数$e$使得$e$和$r$互质​
  5. 求$d$使得$ed\equiv1\pmod r$
  6. 销毁$p,q$,没有人知道$p,q$是多少
     得出$(N,e)$是公钥,$(N,d)$是私钥
     参考链接

• Alice得到公钥和私钥，Alice把公钥告诉Bob，自己把私钥藏起来不告诉任何人。Bob给Alice发消息。

  • 加密：
    假设Bob的消息是$n$,密码是$c$,手上有公钥$(N,e)$
    $$
    c\equiv n^e \pmod N
    $$
    Bob将加密后的$c$发给Alice

  • 解密：

    Alice得到密码$c$,根据私钥$(N,d)$
    $$
    n \equiv c^d \pmod N
    $$
    解码得到$n$

  • 原理：
    $$
    c\equiv n^e \pmod N \
    c^d \equiv n^{e\cdot d} \pmod N
    $$
    因为$e\cdot d \equiv 1 \pmod r$,即$e\cdot d \equiv h \cdot r +1 \pmod N$,其中$h$是自然数
    $$
    c^d\equiv n^{h\cdot r+1}\pmod N\
    c^d\equiv n^{h\cdot \phi(n)+1}\pmod N\
    c^d\equiv n\cdot n^{h\cdot \phi(n)}\pmod N\
    c^d\equiv n\cdot (n^{\phi(n)})^h\pmod N\
    $$
    根据欧拉定理$a^{\phi(n)}\equiv 1 \pmod n$
    $$
    c^d \equiv n\times 1^h \pmod N\
    c^d \equiv n \pmod N
    $$

• 

• 

• 快速幂，取模Modulo Exponentiation（Square-and-Multiply Algorithm）

• 

• Euclidean Algorithm (EA)辗转相除算gcd

• Extended Euclidean Algorithm (EEA) 算as+bt的s和t
  

  

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

#gcd
def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)
#exgcd gcd(a,b)=as+bt
def EEA(a,b):
    if b==0:
        return (1,0)
    (s,t)=EEA(b,a%b)
    return (t,s-a//b*t)
#b=a^{-1} (mod n)
def inverse(a,n):
    b = EEA(a,n)[0]
    if(b<0):
        b+=n
    return b
#a^e mod n
def multiply_and_square(a,e,n):
    if(e==0):
        return 1
    res = multiply_and_square(a,e//2,n)
    if(e%2==1):
        return (res*res*a)%n
    else:
        return (res*res)%n
#rsa_enc
def RSA_enc(p,q,e,m):
    c = multiply_and_square(m,e,p*q)
    return c
#rsa_dec
def RSA_dec_given_pq(p,q,e,c):
    m = multiply_and_square(c,inverse(e,(p-1)*(q-1)),p*q)
    return m

图论 Graph

basis knowledge

• graph图 $G=(V,E)$ is defined by a non empty set V of vertices and aset of E of edges.

• vertices顶点 $|V|$ is called the order(阶数) of G.

• edges边

• endpoint端点

• Infinite Graph 无限图 $|V|=\infty$ or$|E|=\infty$

• Finite Graph 有限图 $|V|< \infty$ or $|E| < \infty$

• Types of Graphs

  • are edges of G directed ?
    • directed graph 有向图
    • undirected graph 无向图
  • multiple edges
    • simple graph 简单图
    • multigraph 多重图
  • loops自环
    • pseudograph伪图

• Special Simple Graph:

  • complete graph完全图:

    • $K_n:V={v_1,\ldots,v_n};E=\Large{$${v_i,v_j}$ $:i\neq j\leq n$ $\Large}$

    • 

  • cycle环，圈：

    • $C_n:V={v_1,\ldots,v_n};E=\Large{$${v_1,v_2},{v_2,v_3},\ldots,{v_n,v_1}$$\Large}$
    • 

  • wheel轮：

    • $W_n:V={v_0,v_1,v_2,\ldots,v_n};E=$$\Large{$${v_1,v_2},\ldots,{v_n,v_1}$$\Large}$$\bigcup$$\Large{$${v_0,v_1},\ldots,{v_0,v_n}$$\Large}$
    • 

  • n-Cubes方体：

    • $Q_n:V={0,1}^n;E={$${u,v}:d(u,v)=1}$即u，v二进制只有一位不一样
    • $d(u,v)=|{i\in [n] :u_i \neq v_i}|$即u，v二进制有几位不一样
    • 

• Adjacency List邻接表：
  Let $G = (V, E)$ be a graph with no multiple edges. The adjacency list of $G$ is a list the vertices of the graph and all adjacent vertices
  $v_i,v_j \in V$ are adjacent if ${v_i,v_j}$ or $(v_i,v_j)$ is an edge

  

  

• adjacency matrix邻接矩阵 :

  let $G=(V={v_1,\dots,v_n},E)$ be a simple graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where
  $$
  a_{ij}=\left{ \begin{array}\ 1 & {v_i,v_j}\in E \ 0 & {v_i,v_j}\notin E\end{array}\right.
  $$
  

• multiplicity重数:
  let $G=(V={v_1,\dots,v_n},E)$ be an undirected graph. The adjacency matrix of $G$ is an $n\times n$ matrix $A=(a_{ij})$, where:

  • $a_{ij}=$ multiplicity of ${v_i,v_j}$ when $i \neq j$
  • $a_{ii}=$ the number of loops from $v_i$ to itself.

• remark: the adjacentcy matrix of a simple graph is always symmetric.

• incidence matrix关联矩阵:
  let $G=(V={v_1,\dots,v_n},E={e_1,\ldots,e_m})$ be undirected.THe incidence matrix of $G$ is an $n\times m$ matrix $B=(b_{ij})$,where
  $$
  b_{ij}=\left{ \begin{array}\ 1 & if\ e_j\ is\ incident\ with\ v_i\ 0 & otherwise\end{array}\right.
  $$

  

• subgraph:

  

  

  edge or vertex operation

• remove/add an edge or vertex

  • edge：

    

    

  • vertex:

    

• edge contyractions

  

• union

  

• complement graph补图：

  

  $G\cup \overline{G}$ is a complete graph($K_n$).

degree and connection

• degree:

  • two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.

  • Neighbor:

    the set of adjacent vertices.

  • degree:

    the number of neighbors.

  

  • isolated: $degree = 0$
  • pendant: $degree = 1$
  • 对上面的图片，⑤ is pendant;⑥ is isolated

• Handshaking Theorem:

  • Let $G=(V,E)$ be an undirected graph with m edges. Then
    $$
    2m=\sum_{v \in V}deg(v)
    $$
    (Note: all undirected graph including simple graph,multigraph(multiple edges),pseudograph(loops))
  • An undirected graph has an even number of vertices of odd degree.
    sketch of pf:Let $V_1$ and $V_2$ be the set of vertices of even degree and theset of vertices of odd degree,respectively,in an undirected graph $G=(V,E)$ with m edges.Then
    $$2m=\sum_{v \in V}deg(v)=\sum_{v \in V_1}deg(v)+\sum_{v \in V_2}deg(v)$$

• degree for directed graph:
  Let $G=(V,E)$ be a directed graph. If $(u,v)\in E$, we say that $u$ is adjacent to $v$ and $v$ is adjacent from $u$.

  • $u$ is the initial vertex of $(u,v)$; $v$ is the terminal vertex of $(u,v)$.
  • in-degree
  • out-degree

  

• Handshaking Theorem for directed graph:

  • Let $G=(V,E)$ be a directed graph. Then
    $$
    \sum_{v \in V}deg^-(v)=\sum_{v \in V}deg^+(v)=|E|
    $$

Isomorphism

• Definition:The simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic同构 if there is a bijection $\sigma :V_1\rightarrow V_2$ such that ${u,v}\in E_1 \Leftrightarrow {\sigma(u),\sigma(v)}\in E_2$
  • $\sigma$ is called an isomorphism同构映射
  • nonisomorphic: not isomorphic

• Determine whether two graphs are isomorphic:
  Definition: Graph invariants are properties preserved by graph isomorphism. For example,
  • The number of vertices
  • The number of edges
  • The number of vertices of each number of degrees
  REAMRKS: The graph invariants can be used to determine if two graphs are isomorphic or not.

Bipartite Graph and Match

• Bipartite Graph二分图、二部图

  • V can be devided to two disjoint part,such that there are not any edges in each part and all edges are connect two parts.
  • 
  • Definition: $G=(V,E)$ is a bipartitie graph if $V$ has a partition ${V_1,V_2}$ such that $E\subseteq {$${u_1,u_2}:u_1\in V_1,u_2\in V_2}$.
    • $(V_1,V_2)$ is a bipartition of the vertex set $V$.
  • 

• Complete Bipartite Graph完全二部图:

  • A complete bipartite graph is a graph $K_{m,n}=(V,E)$ with $V={x_1,\ldots,x_m}\cup {y_1,\ldots,y_n}$ and $E={$${x_i,y_j}:i\in [m],j\in [n]}$
  • 
  • 
  • 

• Matching

  • Definition:
    A matching in a simple graph $G=(V,E)$ is a subset $M\subset E$ such that no two edges in M are incident with the same vertex.
    A maximum matching is a matching with the largestnumber of edges.
    A matching in a bipartite graph with $V=V_1\cup V_2$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is the endpoint of an edge in the matching.

  • Hall’s Marriage Theorem:
    A bipartitie graph $G=(X\cup Y,E)$ has a complete matching from $X$ to $Y$ iff $|N(A)|\geqslant |A|$ for any $A\subseteq X$

    

    

详细证明略去，这次不考

Path,connected, disconnected

• Path

  • Definition:
    

  • for directed path:
    

• Connectivity

  • Definition:
    An undirected graph $G$ is said to be connected if there is a path between any pair of distinct vertices.
    • Graph of order 1 is connected; the complete graph $K_n$ is connected
    • disconnected非连通的: not connected
    • disconnect G: remove vertices or edges to produce a disconnected subgraph
  • Theorem:Let $G=(V,E)$ be a connected undirected graph. Then there is a simple path between any pair of distinct vertices.
    证明同上略。
  • Connected Component：
    
  • • $v\in V$ is a cut vertex割点if $G-v$ has more connected components than G
    • $e\in E$ is a cut edge割边、bridge桥if $G-e$ has more connected components than G

• Find cut vertices and cut edge(s)

  • Vertex Connectivity

    • Definition:A connected undirected graph $G=(V,E)$ is said to be nonseparable不可分的if $G$ has no cut vertex.(one point)
    • Let $G=(V,E)$ be a connected simple graph.
      • vertex cut点割集: A subset $V’\subseteq V$ such that $G-V’$ is disconnected
      • vertex connectivity点连通度$\kappa(G)$ : the minimum number of vertices whose
      removal disconnect $G$ or results in $K_1$; equivalently,
      • if $G$ is disconnected, $\kappa(G)=0$; //additional definition
      • if $G=K_n$,$\kappa(G)=n-1$ //$K_n$ has no vertex cut
      • else,$\kappa(G)$ is the minimum size of a vertex cut of $G$

  • Theorem:
    ​

  • Property：

    

  • Edge connectivity

    • Definition:Let $G=(V,E)$ be a connected simple graph. $E’\subseteq E$ is an edge cut边割集of $G$ if $G-E’$ is disconnected.
    • Let $G=(V,E)$ be a connected simple graph.
      The edge connectivity边连通度($\lambda(G)$) of $G$ is defined as below:
      • $G$ disconnected: $\lambda(G)$ = 0
      • $G$ connected:
      • $|V|=1$: $\lambda(G)$ = 0
      • $|V|>1$: $\lambda(G)$ is the minimum size of edge cuts of $G$.

  • Theorem:
    

  • Let $G=(V,E)$ be a simple graph. Then $\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)$,where $\delta(G)=min_{v\in V} deg(v)$ is the least degree of $G’s$ vertices.
    prove(homework)

• Connected Directed Graphs

  • 

• 路径同构不变性

  Euler circuit, Euler path, Hamilton Circuits, Hamilton path

• Counting Paths Between Vertices

  证明详细分析见后，期末1/5

• Euler circuit and Euler path
  
  

  • Necessary and sufficient condition for Euler circuit
    证明后面详细分析，期末2/5
    

  • 欧拉循环算法
    

  • 欧拉路径

    

• Hamilton Paths and Circuits

  • Definition: Let $G=(V,E)$ be a graph.
    • Hamilton Path: A simple path that passes through every vertex
    exactly once.
    • Hamilton Circuit: A simple circuit that passes through every
    vertex exactly once.
    

  • Determine if there is a Hamilton circuit in a given graph 0?
    • This problem is NP-Complete. //that means very difficult

  • Necessary conditions on Hamilton circuit.
    • If 0 has a Hamilton circuit, then G doesn’t have a vertex of degree 1
    • If 0 has a Hamilton circuit and a vertex of degree 2, then a Hamilton circuit of 0 traverses both edges.

  • Sufficient conditions for existence

    

    

    

Planar Graph

• 

• $K_{3,3},K_5$ 都不是planar

• Regions:

  • DEFINITION: Let $G=(V,E)$ be a planar graph. Then the plane is divided into several regions面by the edges of $G$.
  • 

大括号无序点对，无向边；小括号有序点对，有向边。
已整理ppt：lec1,2,3,4(未举例);lec7,8,9,10,11,12

lec5,lec6（简要）

lec13,14,15,16,17

lec18,19,20,21,22,23,24,25,26

• Lecture 1: Intro/C program structure
• Lecture 2: Data types, operators and expressions
• Lecture 3: Simple input/output
• Lecture 4: Control flow
• Lecture 5: Functions
• Lecture 6: Pointers
• Lecture 7: Arrays
• Lecture 8: Character strings
• Lecture 9: Structures
• Lecture 10: Recursion

• Lecture 11: Algorithms and more advanced C
• Lecture 12: Revision of C
• Lecture 13: Object-Oriented Programming in C++
• Lecture 14: Inheritance
• Lecture 15: Polymorphism, STL templates
• Lecture 16: STL data structures
• Lecture 17: Memory management in C++
• Lecture 18: Structuring your code
• Lecture 19: Coding standards
• Lecture 20: CMake

lec1-20

mind!~ 头文件写没写

lec2:

Date Types:

• how many memory cells are reserved for it

  • Integers
    • short (2 bytes – 16 bits)
    • int (2 bytes?)，64位机中为4 bytes
    • long 32 bits (4 bytes)
    • unsigned (2 bytes)
    • unsigned short (2 bytes)
    • unsigned long 32 bits (4 bytes)
  • Floating Points
    • float (4 byte, or 32 bits)
    • double (8 bytes, or 64 bits)
  • Characters
    • 1 byte
    • （128 distinct characters in the ASCII character set.）
    • （Two C character types:
      • char (1 byte or 8 bits, range: [–128, 127]
      • unsigned char (1 byte or 8 bits, range: [0, 255]）

• < data type > < name >

• ASCII:

• 

• ++i 返回值是（i+1）；i++返回值是i （先加再返回和先返回再加）（返回指表达式值）

• const

• #define 替换

• Full List of Operators with Precedence优先级：
  

• 计算时不同类型升级

• printf()函数：

• scanf()取地址

  lec3:

example:

problem

网上冲浪发现一个巨佬学长，来自中科大

http://home.ustc.edu.cn/~qifan/answers/MathematicalAnalysis_B2_ans.pdf

离散数学 Discrete Mathematics

part 1 proposition and logic

命题 proposition

A proposition is a declarative sentence that is either true or false.

• 真值 truth value

• Simple Proposition:

​ cannot be broken into 2 or more propositions

• Compound Proposition:

  not simple

logic operation

• Negation (否定) $\neg$

• conjunction (合取) and $\wedge $

• Disjunction (析取) or $\vee$

• Implication (→)

• Bi-Implication (↔)：

​ A$\leftrightarrow$B $\Leftrightarrow$(A$\rightarrow$B)$\wedge $(B$\rightarrow$A)

• Precedence（优先级）：

​ $\neg$， $\wedge$ ，$\vee$，$\rightarrow$，$\leftrightarrow$

Well-Formed Formulas :

​ =propositional formulas=formulas

** Translation**:

• if A then B $\Leftrightarrow$ A$\rightarrow$B
• A only if B $\Leftrightarrow$ A$\rightarrow$B
• A is a sufficient condition for B $\Leftrightarrow$ A$\rightarrow$B
• A is a necessary condition for B $\Leftrightarrow$ B$\rightarrow$A
• A necessary condition for A is B$\Leftrightarrow$A$\rightarrow$B
• but $\wedge $
• A if B $\Leftrightarrow$ B$\rightarrow$A
• A provided that B $\Leftrightarrow$ B$\rightarrow$A
• A only if B $\Leftrightarrow$ A$\rightarrow$B

Types of WFFs:

• tautology always true
• contradition always false
• contingency neither tautology nor contradiction
• satisfiable:it is true for at least one truth assignment

Logically equivalent:

​ A and B always has the same truth table for every truth assignment(of p1,p2,…,p$_n$)

Tautological Implications $\Rightarrow$ :

​ How to prove A $\Rightarrow$B:

• A$^{-1}$(T)$\subseteq$B$^{-1}$(T);
• A$\rightarrow$B is a tautology;
• A$\land$$\neg$B is a contradiction

个体和谓词 Individual and Predicate

• universal quantifier $\forall$ and existential quantifier$\exists$

• Types of WFFs:

• logically valid : always true

• unsatisfiable : always false

• satisfiable : it is true for at least one truth assignment

• important:

  Prop:

• $$\forall x(A(x) \land B(x)) \equiv \forall xA(x) \land \forall xB(x)$$

• $$\exists x(A(x) \lor B(x)) \equiv \exists xA(x) \lor \exists xB(x)$$

(mid,2019)$\forall x(\forall y(N(x,y) \to \forall z(G(z,x) \land G(z, y) \lor D(z, x) \lor D(z,y))))$

Logic translation：mid

part 2 set theory

Principle of Inclusion-Exclusion

cover

partition is disjoint cover

proper:真子集

complement:补集

$p(A)={x|x\subseteq A}$:the power set of A

disjoint:$A\cap B\neq \emptyset$

XOR$\oplus$: $A\oplus B =(A-B)\cup(B-A)$: the symmetric difference of A and B.

时间原因，写的仓促，详见vixbob’s set theory

part 3 combinatorial mathematics

Combinations of set:

• Let $𝐴$ = {$a_1$, … , $a_𝑛$} be a finite set. Let $k$ $\in$ {0,1, … , 𝑛}. k-combination of $𝐴$ without repetition: an $k$-subset of $𝐴$.
• $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

Permutations of set:

• Let $𝐴$ be a finite set of 𝑛 elements. Let $k$ $\in$ [n].$k$-permutation of $𝐴$: a sequence $a_1$, $a_2$, ⋯ , $a_k$ of $k$ distinct elements of $𝐴$.
• $$A_{n}^{k} = \frac{n!}{(n-k)!}$$

Multiset:

​ A multiset is collection of elements which are not necessarily different from each other.

• An element 𝑥 $\in$ 𝐴 has multiplicity 𝑚 if it appears 𝑚 times in the multiset 𝐴.
• A multiset 𝐴 is called an 𝒏-multiset if it has 𝑛 elements.
• $A = {n_{1}\cdot a_{1},n_{2}\cdot a_{2},\ldots,n_{k}\cdot a_{k}}$ : an $(n_1 + n_2 +\cdots +n_k)$-multiset where the elements $a_1 , a_2 ,\dots ,a_k$ has multiplicities $n_1 , n_2 ,\dots ,n_k$, respectively.
• • $T = {t_1 \cdot a_1,t_2 \cdot a_2,\ldots,t_k \cdot a_k}$ is called an $r$-subset of $A$ if $0\leqslant t_i\leqslant n_i \ for \ every \ i \in[k],\ and$ $t_1 +t_2 +\ldots +t_k =r$.

Inverse Binomial Transform:

当an好列式，bn不好列式时，

​ if $$a_n = \sum_{k=s}^{n}\binom{n}{k}b_k$$ then $$b_n = \sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k$$ (n$\geqslant$s)

• prove for Inverse Binomial Transform:

• • lemma：

    这个引理显然，还可以用组合恒等式来整，时间原因先略。

  • lemma:

    $$ \sum_{i=0}^{n-r}(-1)^{(n-r)-i} \binom{n-r}{i} = (1-x)^{n-r} and \ x=1\ so \ it \equiv 0 $$
    by 二项式定理。

  • lemma:

  • prove:

  $$let \ {a_n},{b_n} \ be \ two \ sequences\ such\ that \ for\ all\ n\geqslant s,a_n=\sum_{k=s}^{n}\binom{n}{k}b_k.Then\ b_n=\sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k\ (n\geqslant s)$$

$$
\begin{aligned}
\sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}a_k & = \sum_{k=s}^{n}(-1)^{n-k}\binom{n}{k}\sum_{i=s}^{k}\binom{k}{i}b_i \& =\sum_{k=s}^{n}\sum_{i=s}^{k}(-1)^{n-k}\binom{n}{k}\binom{k}{i}b_i\&=\sum_{i=s}^n\sum_{k=i}^n(-1)^{n-k}\binom{n}{k}\binom{k}{i}b_i\&=b_n
\end{aligned}
$$

背下来

• example:
• • 染色:
    

generatng function

• let$$a_0,a_1,\ldots,a_r,\ldots$$ be a sequence of real number. The **generating functioon **of this sequence is defined as:

  $$G(x)=a_0+a_1x+\cdots+a_rx^r+\cdots=\sum_{r=0}^{\infty}a_rx^r.$$

• formal power series(FPS)形式幂级数

• Operations：let $$A(x)=\sum_{r=0}^{\infty}a_rx^r,B(x)=\sum_{r=0}^{\infty}b_rx^r$$

  • $$a(x) \cdot B(x) = \sum_{r=o}^{\infty}(\sum_{j=0}^{r}a_j b_{r-j})x^r$$

  pf:

  $$\sum_{m=0}^{\infty}a_{m}x^{m}\cdot \sum_{n=0}^{\infty}b_{n}x^{n} \ =\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}a_{m}b_{n}x^{m+n}\ =\sum_{r=0}^{\infty}\sum_{j=0}^{r}(a_{j}b_{r-j})x^r\quad[m+n=r]$$

  • inverse:

    we say that B(x) is an inverse of A(x) if A(x)B(x)=1.

  • • the inverse of A(x) : $A^{-1}(x)$
    • When a(x) has an inverse ,define $\frac{C(x)}{A(x)}=A^{-1}(x)\cdot C(x).$
    • example:let $A(x)=\sum_{r=0}^{\infty}x^r.\ then \ A^{-1}(x)=1-x.$

• extended binomal coefficient:

  ​ $$let u \in R \ and \ r \in N.$$

  ​ $$\binom{u}{r}= \left{ \begin{array}{}u(u-1)\cdots(u-r+1)/r! & (r>0) \1 & (r=0)\end{array}\right.$$

• $$let\ \alpha\in R\backslash{0}\ and\ u\in Q.\ (1+\alpha)^{u}=\sum_{r=0}^{\infty}\binom{u}{r}\alpha^rx^r=\sum_{r=0}^{\infty}\frac{u(u-1)\cdots(u-r+1)}{r!}\alpha^rx^r$$

• $$(1+\alpha)^{-n}=\sum_{r=0}^{\infty}\binom{-n}{r}\alpha^rx^r=\sum_{r=0}^{\infty}(-1)^r\binom{n+r-1}{r}\alpha^rx^r$$

• $$(1-\alpha)^{-n}=\sum_{r=0}^{\infty}\binom{-n}{r}(-\alpha)^rx^r=\sum_{r=0}^{\infty}\binom{n+r-1}{r}\alpha^rx^r$$

• counting combinations with GFs:

  • Let $$n>0,r\geqslant0,R_1,\ldots,R_n\subseteq N.$$Let $a_r$ be the number of r-combnination of [n] with repition where every i$\in$[n] appears $r_i$ ($r_i\in R_i$) times.

  • $$a_r = |{(r_1,\ldots,r_n):r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}|$$

  • $R_i$ means $r_i\leqslant|R_i|$.$R_i$表示了第i个元素出现的次数有限制。

  • This is also the number of ways of distributing r identical objects into n different boxes such that$r_i(r_i\in R_i)$ objects are sent to box i for all i$\in$[n].

  • in the following equation $\sum {r_i\in R_i} \ maens\ \sum{r_i=0}^{|R_i|}$，theorem:
    $$
    \sum_{r=o}^{\infty}a_rx^r = \prod_{i=1}^{n}\sum_{r_i\in R_i}x^{r_i}
    $$
    prove for it:

$$
\begin{aligned}
\prod_{i=1}^{n}\sum_{r_i \in R_i}x^{r_i} &=  \sum_{r_1\in R_1}x^{r_1} \cdot \sum_{r_2\in R_2}x^{r_2} \cdots \sum_{r_n\in R_n}x^{r_n}\\
&=\sum_{r=0}^{\infty}(\sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r})x^r\\&=\sum_{r=0}^{\infty}a_rx^r
\end{aligned}
$$

• example:
  

  

  

  and from homework we can know ,we can suppose $\alpha$ and let it be 0 in odd be 1 in even to do something.

• counting permutations with Gfs

  • Let $$n>0,r\geqslant0,R_1,\ldots,R_n\subseteq N.$$Let $a_r$ be the number of r-permutations of [n] with repition where every i$\in$[n] appears $r_i$ ($r_i\in R_i$) times.

  • $$a_r = \sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}\ \frac{r!}{r_1!r_2!\cdots r_n!}$$

  • This is also the number of ways of distributing r different objects into n different boxes such that $r_i(r_i\in R_i)$ objects are sent to box M for all $i\in [n]$.先随便排，任取一个序列，对每个序列，$r_i$个放入第i个box，这个box内部是无序的，所以除以ri！，i是任意的，遍历，除去每一项阶乘。

  • in the following equation $\sum {r_i\in R_i} \ maens\ \sum{r_i=0}^{|R_i|}$,theorem:

    $$
    \sum_{r=0}^{\infty}\frac{a_r}{r!}x^r =\prod {i=1}^{n}\sum{r_i\in R_i}\frac{x^{r_i}}{r_i!}
    $$

  • prove for it:

  • $$
    \begin{aligned}
    \prod_{i=1}^{n}\sum_{r_i \in R_i}\frac{x^{r_i}}{r!} &= \sum_{r_1 \in R_1}\frac{x^{r_1}}{r_1!} \cdot \sum_{r_2 \in R_2}\frac{x^{r_2}}{r_2!} \cdots \sum_{r_n \in R_n}\frac{x^{r_n}}{r_n!}\
    &=\sum_{r=0}^{\infty}(\sum_{r_1\in R_1,\ldots,r_n\in R_n,r_1+\cdots+r_n=r}\ \frac{r!}{r_1!r_2!\cdots r_n!})\frac{x^r}{r!}\&=\sum_{r=0}^{\infty}\frac{a_r}{r!}x^r
    \end{aligned}
    $$

  • example:

    

    

    

    

    the recursion of $S_2$ will be shown after (LNRR)

Pigeonhole Principle 鸽笼原理，又名抽屉原理

example:
prove :$let\ n\in Z^+.Let\ A \subseteq {1,2,\ldots,2n}\ have\ n+1\ elements.Then\ \exists x,y\in A \ such \ that\ x|y.$$

answer:

considering that $u\cdot 2^x$,$u\in[n]$ and $x\in N$.

$\forall t \in {1,2,\dots,2n}$ can be written in the formal of $u\cdot 2^x$.

we can consider the $u\in [n]$ as n boxes,and because A has (n+1) elements,so at least one boxes has two number which have the same u and they have the different x. 不妨设$X=u\cdot 2^x \ and\ Y=u\cdot 2^y$,

so if(x<y) X|Y;else if(x>y) Y|X.

QED.

linear homogeneous recurrence relation (LNRR)

Examples for combinatorial mathematics:

• $\binom{n+r-1}{r}$插板法一列“1”，插加号，两个加号之间“1”的数量为一个值

• combinatorial equation:

  $$\binom{m+n}{r}=\sum_{k=0}^{r}\binom{m}{r-k}\cdot \binom{n}{k}\\binom{n+1}{r}=\binom{n}{r-1}+\binom{n}{r}\\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2\\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$

• • combinations of Multiset:

    ​ $\binom{n+r-1}{r}$

  • permutations of Multiset:

    ​ $r!/r_1!\cdots r_n! \quad\ (\sum_{r_i}=r)$

• Principle of Inclusion-Exclusion: 注意反刨几次

  

• $S_2(n,r)$ : the stirling number of the second kind ,is defined as the number of different ways of distributing n distinguishable objects into j indistinguishable boxes so that no box is empty.(n different balls into r indistinguishable boxes and no empty boxes)

  • $$S_2(n,k) = S_2(n-1,k-1)+S_2(n-1.k)$$

  • 边界：$$S_2(n,0)=0;S_2(0,0)=1;S_2(n,n)=1(n\neq0)$$

  • • 将新元素单独放入一个子集，有$S_2(n-1,k-1)$种方案；
    • 将新元素放入一个现有的非空子集，有$kS_2(n-1,k)$种方案。

  • 通项：$$S_2(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$

  • Principle of Inclusion-Exclusion:

    使用容斥原理证明该公式。设将n个两两不同的元素，划分到k个两两不同的集合（允许空集）的方案数为$G_i$，将n个两两不同的元素，划分到k个两两不同的非空集合（不允许空集）的方案数为$F_i$。

    Obviously,
    $$
    G_i=k^n\ G_i=\sum_{j=0}^i\binom{i}{j}F_j
    $$
    by 二项式反演:
    $$
    \begin{aligned} F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\ &=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\ &=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \end{aligned}
    $$
    considering that the difference bewteen $F_i$ and $S_2(n,i)$.the boxes in $S_2$ is not distinguishable .so $F_i$ is $i!$ times as much as $S_2$

• $P_j[n]$Partitions of Integers:$n=a_1+a_2+\cdots+a_j$ is called an n-partition with exactly j parts if $a_1 \geqslant a_2 \geqslant \cdots \geqslant a_j$ are all positive integers.

  • $$p_j(n)=|{ (a_1,a_2,\ldots,a_j):a_1+\cdots+a_j =n,a_1\geqslant a_2 \geqslant \cdots \geqslant a_j \geqslant 1 \ are\ integers}|$$

  • $p_j(n)$ is the number of ways of writing n as the sum of $j$ positive integers.

  • 递推：$p_k[n]$表示n分k份。

    • p_1(n)=1,p_n(n)=1
    • if k > n ,p_k(n)=0
    • else if k < n, $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$

  
  

  • generating function:

  • • $$
      \sum_{n=0}^{\infty}((\sum_{r=1}^{n} p_r(n)) \cdot x^n)=\prod_{k=1}^{\infty}(\frac{1}{1-x^k})
      $$

    • 对于具体n分成r份时：
      $$
      \sum_{n=0}^{\infty}p_r(n)x^n =x^r \prod_{j=1}^r\frac{1}{1-x^j}
      $$

• easy combination and permutation application:

• • shortest path:

    • A $p\times q-grid$ is a collection of $pq$ squares of side length 1, organized as a rectangle of side length p and q.
    • 
    • the number of the shortest paths is $\frac{(p+q)!}{p!q!}$
    • multiset A= ${p\times \rightarrow,q\times \uparrow}$ , permutation of mulitiset.
    • # of shortest paths = # of permutations of A.

  • T-path:

    • from (x,y) to (x+1,y+1) or (x+1,y-1)

    • T-condition: from A(a,$\alpha$) to B(b,$\beta$) only if

      • $b > a$
      • $b-a \geqslant|\beta -\alpha |$
      • $2|(b+\beta -a-\alpha)$

    • solve permutation of multiset.

a so easy example about generating function:例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。

该问题可以看成n拆分成1,2,3,4之和且不允许重复的拆分数，利用母函数计算如下：

$$
(1+x)(1+x^2)(1+x^3)(1+x^4)=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}
$$

$2x^4$ 表示称出4克有2种方案，是1+3和2+2，以此类推，超出10克便无法称出。

加括号是第二类斯特林数

已整理ppt：lec1,2,3,4(未举例);lec7,8,9,10,11,12

lec5,lec6（简要）

word list for cet6

熟词生义

A

act n.法令;(一)幕

administer v.给与

air n. 样子；v. 晾干，使通风，使公开

arch n.拱形，拱门，v.使成拱形 a.淘气的

article n.条款

B

bear vt.生育，运输 vt.写（刻，印）有 n.（证券交易中）卖空者

belt n.区

browse vi.（牛、羊）吃草

C

cheap a. 卑鄙的

coin vt.创造（新词）

collect a./ad.打由对方付费的电话

concert n.一致

couch vt.表达

crop n.一批；vt.剪短，修剪

D

deed n.契约，证书

deliver vt.给（产妇）接生；给与（打击）；解救，拯救

description n.种类

dividend n.红利，股息；会报，效益

E

edge n.优势 v.侧着移动

employ vt.使忙于

even a.均匀的，平的 v.（使）相等

express ad.用快递方式，乘直达快车 n.快车，快递 a.特快的，明确的

F

fair n.定期集市，博览会

familiar a.冒昧的，放肆的

film n.胶卷 v.拍摄

fine a.精致的，颗粒微小的

firm a.结实的，坚固的 n.商行，商号，公司

G

garage n.车库，汽车修理行

general n.将军

H

hail n.雹；一阵 vi.下雹 vt.招呼，高呼，为···喝彩

hand n. 指针

handsome a. 相当大的

harp n.竖琴 vi.喋喋不休的说

hear vt.审讯

house n.商号，议院 vt.给···房子住

I

immediate a.直接的

industry n.勤劳

iron vt.烫（衣），烫平

K

kill vt.消磨（时间）

L

last vi.持续

lead n.铅，铅制品

letter n.证书

library n.藏书

lot n.（抽的）签，（抓的）阄

M

mark n.斑点

master vt.掌握，征服 n.原版；硕士 a.主要的，优秀的

might n.力量，威力，权势

mine n.矿，矿山；地雷

minute a.微细的，极小的 n.会议记录

mirror vt.反映，反射

moon n.卫星

N

nurse vt.看护

P

paper vt.用墙纸糊墙

part v.分开，n. 角色，器官

peanut n.花生，很少的钱

period n.学时，句号

permit n.执照

piece vt.拼合

pipe n.烟斗；管乐器；vt.用管道输送

plain a.清楚的

plant n.工厂，间谍

plate n.板，片，盘， 金属牌 vt.电镀

pool vt.公用，n.公用物

post n.柱，桩，杆 vt.贴出，宣布，公告

pound vt.捣碎，猛击

power vt.使开动

present vt.介绍，提出

press n.新闻界，舆论界；出版社，印刷机

pride vt.自夸

prize vt.珍视

pronounce vt.宣布，宣判

pupil n.瞳孔

R

rapid n.急流

reason v.推理，分析

rest n.支座 v.靠，停留

revolution n.旋转，绕转

row v.划（船等）

rush v.催促，仓促完成 n.需求的激增；身体的一阵感觉

S

safe n.保险箱

sandwich vt.夹入

satisfaction n.赔偿（物）

save prep.除···之外

school n.学派；上课（时间）

sentence n.判决 vt.宣判

share n.份额 n. 股份

shoot vt.疾驰 n. 嫩枝，打猎

shoulder vt. 肩负，承担

skirt n.边缘，郊区 vt.绕开，位于···边缘

society n.上流社会

soil v.弄脏

sort vt.整理

sound a.健康的，完好的；精湛的，正确的，彻底的 ad.充分地，酣畅的

spare a.多余的，备用的 vt.节约，饶恕，免去

stamp n.戳子；跺脚 v.踩踏，在···上面盖印

stomach n.胃，肚子，食欲 v.忍受

succeed v.继承，继···之后

suit n.起诉，诉讼

sunny a.快活的

T

tablet n.药片，碑，牌，（木，竹）间

tank n.大容器，槽，池塘

tap vt.开发，窃听

U

uniform a.一致的

W

wage vt.开展（运动）

Word list

Word list1 (A)

accessory n.附件，零件，配件；装饰品；同谋，帮凶

accord n.一致，符合;谅解，协议 v.相符合，一致；授予，赠予

ac + cord(心)
with one accord 一致地
in accord with 按照，根据，与···一致

accordance n.一致，和谐，符合

in accordance with 按照，根据，与···一致

account vi.说明···的原因

account for 解释，说明，占有

on account of 由于，为了

on no account 绝不可以，无论如何也不

accuse vt.指责，归咎于

ac(加强) + cuse(理由)

accuse sb. of doing sth. 指控某人···

accustomed to sth. / doing sth.

acquaint vt.使认识，使熟悉，使了解

ac + quaint(知道)

acquaint with 使认识，使熟悉，使了解

acquaintance n.认识，了解，熟人

acute a. 严重的；急性的；灵敏的，敏锐的；精明的

adequate a. 足够的，可以胜任的

ad(加强) + equ(平等)+ ate(···的) $\rightarrow$ 比平等多的 $\rightarrow$ 足够的

adhere vi.粘附，附着；遵守，坚持；追随，支持

ad(加强) + her(粘附) + e

adhere to 粘附，附着；遵守，坚持

adjacent a.邻近的，毗邻的

adjacent to

adjoin vt.贴近，与···毗连

ad(附近，向) + join(连接) $\rightarrow$ 贴近

adolescent n.青少年 ad.青春期的，青少年的

adore vt.崇拜，敬慕，爱慕；非常喜欢

adverse a.不利的，有害的

ad(坏) + vers(转) + e

aerial a. 飞机的，航空的；空中的，架空的 n. 天线

aer(空气) + ial(···的)

aesthetic a. 美学的，审美的；悦目的，雅致的

a + esthet(感觉)+ ic(···的)

affection n. 感情；爱慕

affiliate vt.使隶属于 n.附属机构，分公司

affirm vt. 断言，坚持声称；证实，确认

afflict vt.使苦恼，折磨

aggravate vt.加重，加剧，使恶化；激怒，使恼火

Word list2 (A)

aggregate n.总数，合计 a.总计的，合计的 vt.总计达，合计

in the aggregate 总共

agony n.(极度的)痛苦，苦恼

aisle n.过道，通道

alcohol n.酒精，乙醇

alien a.外国的，外国人的；陌生的；性质不同的，不相容的 n.外国人，外侨，外星人

alleviate vt.减轻，缓解，缓和

alliance n.结盟，联盟

alloy n.合金，vt. 将···铸成合金

alter vt.改变，变更，变动

alternate a.交替的，轮流的，间隔的 v.（使）轮流，（使）交替

amend vt.修改，修订，改进 n.赔罪，赔偿

a(加强)+mend(修理)$\rightarrow$ 修改，修订

ammunition n. 弹药，军火

amplify vt.放大（声音等），增强；扩大，详述，进一步阐述

analogy n.比拟，类比，类推

ana(分开)+log(说)+$\rightarrow$将事物分成类来说

by analogy 用类比的方式

anonymous a.无名的，不具名的；匿名的；无特色的，无个体特征的

an(无)+onym(名字)+ous(···的)

anticipate vt.预料，预期，期望；先于···行动，提前使用

anti(先)+cip(拿)+ate(做)

apparatus n.器械，器具，仪器；机构，组织

appease vt.平息，抚慰，姑息

appendix n.阑尾

applaud vi.鼓掌，喝彩 vt.向···鼓掌，向···喝彩；称赞，赞许

appliance n.用具，器具，器械

appraisal n.估计，估量，评价

Word list3 (A)

apt a.易于···的，有··倾向的；恰当的，适宜的；聪明的

arbitrary a.随心所欲的，专断的

arc n. 弧形

arena n.表演场地，竞技场；活动场所

armor n.盔甲，装甲，保护物

int 128＝（2^64）*a+b，（式中a，b为unsigned long long）

fgets=读入会包含最后的换行而gets不会，但是这是在Linux/Unix之下，windows下换行是\r\n，而Linux下是\n，所以gets会把\r读入\n舍弃

~(-1) $\iff$True

!(0) $\iff$True

gets(str) 读取一行至str，读入换行并舍弃

fgets(str,n,stdin) stdin表示从标准输入读入，可改为从指定文件读入，fgets读到（n-1）个字符或者换行为止，将换行符存在str中。

gets_s(str,n)若读到（n-1）个字符前读到换行符，读入并舍弃换行符；若读到（n-1）个字符时未读到换行符，将str首字符设置为0，读入并舍弃该行剩余所有。然后调用依赖实现的“处理函数”，可能中止或退出程序。

int 128＝（2^64）*a+b，（式中a，b为unsigned long long）

fgets=读入会包含最后的换行而gets不会，但是这是在Linux/Unix之下，windows下换行是\r\n，而Linux下是\n，所以gets会把\r读入\n舍弃

~(-1) $\iff$True

!(0) $\iff$True

gets(str) 读取一行至str，读入换行并舍弃

fgets(str,n,stdin) stdin表示从标准输入读入，可改为从指定文件读入，fgets读到（n-1）个字符或者换行为止，将换行符存在str中。

gets_s(str,n)若读到（n-1）个字符前读到换行符，读入并舍弃换行符；若读到（n-1）个字符时未读到换行符，将str首字符设置为0，读入并舍弃该行剩余所有。然后调用依赖实现的“处理函数”，可能中止或退出程序。

logic Operators

&& and

|| or

! not

Logical Expressions:
expression1 && expression2 is true if and only if both expressions are true. expression1 || expression2 is true if either one or both expressions are true. !expression is true if the expression is false, and vice versa.

if #include<ios646.h>,then you can use and as &&,or as || not as ! .

?

x = (y < 0) ? -y : y; equal

1
2
3
4

if(y < 0)
    x = -y;
else:
	x = y;

max = (a > b) ? a : b; equal

1
2
3
4

if(a > b)
    max = a;
else:
	max = b;

continue and break

continue

When encountered, it causes the rest of an iteration to be skipped and the next iteration to be started. If the continue statement is inside nested structures, it affects only the innermost structure containing it.

break

A break statement in a loop causes the program to break free of the loop that encloses it and to proceed to the next stage of the program. If the break statement is inside nested loops, it affects only the innermost loop containing it.

switch

1
2
3
4
5
6
7
8
9
10

switch (ch)
{
    case 'a':
        printf("argali, a wild sheep of Asia\n");
        printf("argali, a wild sheep of Asia\n");
    case 'b':
        printf("babirusa, a wild pig of Malay\n");
    default:
        printf("That's a stumper!\n");
}

equal

1
2
3
4
5
6
7
8
9

if(ch == a)
    {
        printf("argali, a wild sheep of Asia\n");
        printf("argali, a wild sheep of Asia\n");
	}
else if(ch == b)
    printf("babirusa, a wild pig of Malay\n");
else:
	printf("That's a stumper!\n");    

while

for

do while

A typical while loop design looks like this:

​ get first value
​ while (value meets test)
​ {

​ process the value

​ get next value

​ }

A for loop doing the same thing would look like this:

​ for (get first value; value meets test; get next value)

​ process the value;

if(expression)

statement;

getchar()

putchar()

ctype.h

else if in C like elif in python

Before you run this program ,you need to start the game and change it to “冒险—挑战—最后一关—下一步”like this picture.

and run this program .It can replace you to finish “闯关”.Its principle depends on PyUserInput.And you can input int to set the cycle index.