初赛3——数学

在幕布中查看（密码：LAN）

• 计算机数学
  • 数制
    • 转换
      • 整数
        • ->：除K取余，逆序
        • <-：加权求和
      • 小数
        • ->：乘二取整，顺序
        • <-：加权求和
    • 计算
  • 数据存储
    • 机器数
      • 真值
      • 原码
        • 最高位为符号位
      • 反码
        • 正数：=原码
        • 负数：=原码符号位不变，其余位取反
      • 补码
        • 正数：=原码
        • 负数：=反码+1
        • n位补码表示范围：[-2^(n-1),2(n-1)-1]
        • 原码+补码=模
        • 补码的补码=原码
    • 小数
      • 定点数
        • 小数点在符号位后
      • 浮点数
        • 阶码
        • 尾数
        • 规格化
    • ASCII码
    • BCD码
  • 逻辑运算
    • 创立
      • 乔治·布尔【英】
    • 基本运算
      • 与∧/·
      • 或∨/+
      • 非¬
      • 公式
        • 变量与常量关系
          • A+1=1
          • A+0=A
          • A·1=A
          • A·0=0
        • 重叠律
          • A+A=A
          • A·A=A
        • 互补律
          • A+(¬A)=1
          • A·(¬A)=0
        • 交换律
          • A+B=B+A
          • A·B=B·A
        • 结合律
          • A+(B+C)=(A+B)+C
          • A·(B·C)=(A·B)·C
        • 分配律
          • A·(B+C)=A·B+A·C
          • A+(B·C)=(A+B)·(A+C)
        • 反演律
          • ¬(A+B)=(¬A)·(¬B)
          • ¬(A·B)=(¬A)+(¬B)
        • 还原律
          • ¬(¬A)=A
        • 吸收律
          • A·(A+B)=A
          • A+(A·B)=A
    • 复合运算
      • 同或⊙
      • 异或⊕
      • 公式
        • 变量与常量关系
          • A⊙0=¬A
          • A⊙1=A
          • A⊕0=A
          • A⊕1=¬A
        • 互补律
          • A⊙(¬A)=0
          • A⊕(¬A)=1
        • 重叠律
          • A⊙A=1
          • A⊕A=0
        • 调换律
          • A⊙B=C <=> A⊙C=B <=> B⊙C=A
          • A⊕B=C <=> A⊕C=B <=> B⊕C=A
    • 表示方法
      • 真值表
      • 卡诺图
  • 排列组合
    • 圆周排列
      • Q(n,m)=A(n,m)/m=n!/[m(n-m)!]
      • n=m时：N=(n-1)!
    • 错排
      • D(n) = (n-1) [D(n-2) + D(n-1)]
      • D(1)=0,D(2)=1
      • D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].
      • D(n)=n*D(n-1)+(-1)^n
    • 可重组合
      • 在n个不同元素中取m个可以重复的组合
      • 无限
        • =C(n+m-1,m)
        • (x+y+z)^n的项数=C(n+3-1，n)
      • 有限
        • =n!/(a1!*a2!*…*ak!)
    • 不相邻组合
      • 从A={1，2，…n}取m个不相邻的数的组合
      • =C(n-m+1,m)
    • 卡特兰数Catalan
      • 式子
        • h(1)=1
        • h(n)=h(1)*h(n-1)+h(2)*h(n-2)+…+h(n-1)*h(1)
        • h(n)=h(n-1)*(4n-2)/(n+1)
        • h(n)=C(2n,n)/(n+1)=C(2n,n)-C(2n,n-1)
      • 直接应用
        • 括号化
        • 两排站队
        • 剧院买票找零（10/5）
        • 出栈次序
        • 多边形划分三角形
        • 给定顶点组成二叉树
        • 方格行走不穿越对角线
        • 二进制有n个1的方案数
    • 第二类斯特林数
      • 将n个不同的元素分成m个集合的方案数
      • S(n+1,m)=S(n,m-1)+m*S(n,m)
      • S(n,0)=0
      • S(n,1)=1
      • S(n,n)=1
    • 抽屉原理
  • 约瑟夫问题
    • N=2：
      • k=log2(N),x=2*(N-2^k)+1
    • N=n： 从0开始编号​f[1]=0;f[i]=(f[i-1]+m) mod i; (i>1）​
  • 表达式
    • 前缀表达式
    • 中缀表达式
    • 后缀表达式
    • 表达式转换
  • 千禧难题
    • P，NP，NPC
      • P：所有可以在多项式时间内求解的判定问题构成P类问题。判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。
      • NP：所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。
      • NPC：P=NP？ NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。
    • 霍奇猜想
    • 庞加莱猜想
    • 黎曼假设
    • 杨－米尔斯存在性和质量缺口
    • 纳维叶－斯托克斯方程的存在性与光滑性
    • 贝赫和斯维讷通－戴尔猜想