NOIP思维导图

NOIP思维导图，c++是一种计算机高级程序设计语言， 由C语言扩展升级而产生 ， 最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。是一种编译型高级语言

信息学

• c++简介
  • 是一种计算机高级程序设计语言， 由C语言扩展升级而产生 ， 最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 是一种编译型高级语言
  • 计算机存储空间大小 1PB=>1024TB 1TB=>1024GB 1GB=>1024MB 1MB=>1024KB 1KB=>1024B 1B=> 8bit Btye字节 bit 二进制
• c++基础
  • 基本框架结构
    • #include <iostream> using namespace std; int main() { cout << “Hello World!”; return 0; }
      • #include <iostream> // include 引入 包含 以 # 标志开始的句子是预处理器的指示语句。它们不是可执行代码，只是对编译器作出指示。 在本例中这个句子# include < iostream > 告诉编译器的预处理器将输入输出流的标准头文件(iostream)包括在本程序中。 这个头文件包括了C++中定义的基本标准输入-输出程序库的声明。此处它被包括进来是因为在本程序的后面部分中将用到它的功能。
    • 基础结构介绍
      • #include <iostream> // #预处理 include 包含 i=>input 输入 o=> output 输出 stream 溪流
      • using namespace std; // 所有库预处理 变量都创建在 std标准名空间内
      • int main(){ // 主函数 程序入口
        • //变量: 值可以发生改变的量 常量:值不可以发生改变的量 比如 Π 圆周率
        • //变量的命名规则: 1禁止数字或数字开头 2 严格区分大写 3 禁止符号除 _下划线以外 4避开关键字
        • // cin>> 输入数据 c++ input >> 指 流向为 流入
        • // cout<< 输出数据 c++ output << 指 流向为 流出
        • return 0; // 返回值
  • 基本数据类型
    • 整型 浮点型 布尔型 字符型
      • 整数类型分为 short 短整型 int 整型 long long 长整型
        • short 短整型 2字节 -2^15 - 2^15-1
        • int 整型 4字节 -2^31 - 2^31-1
        • long long 长整型 8字节 -2^63 - 2^63 -1
      • float单精度浮点数 double 双精度浮点数
        • float 单精度浮点数 4字节 有效位 7位
        • double 双精度浮点数 8字节 有效位 15位
      • bool 布尔类型
        • bool 布尔类型 取值 true或false 1字节 0代表false 非0 代表 true
      • char 字符
        • char 字符类型 取值单个字或符号 1字节
  • 基本运算
    • +加法 -减法 *乘法 /除法 %取余数
      • + 加法运算 a+b
      • - 减法运算 a-b
      • *乘法运算 a*b
      • /除法运算 a/b 10/3=> 3 取商
      • %取模运算 a%b 10%3 =>1 取余数 用途： 判断 奇偶关系 倍数关系 数字进行剥离 反转
        • 剥离法 // 逆序输出 380 => 83 1234 => 4321 int n,m=0; cin>>n; // 1234 while(n){ // 剥离法 m=m*10+ n%10; //取 n的末位 拼接到 m 4321 n/=10; // 减位 123 12 1 0 } cout<<m;
    • 关系运算 > 大于 >= 大于或等于 < 小于 <= 小于或等于 == 等不等于 != 不等于
      • 关系运算表达式： 用途：二个数据之间的关系判断 结果值为布尔类型 关系满足成立，结果值为 true 关系不满足成立，结果值为false
    • 逻辑运算符 & 逻辑与 | 逻辑或 ! 逻辑非
      • && 逻辑与 左右二边都满足，则逻辑成立为true ,否则为 fasle | | 逻辑或 左右二边最少有一边满足，则逻辑成立为true, 否则为false ! 非 非真即假 非假即真
  • <cmath>数学头文件 abs() 获取绝对值 sqrt() 获取平方根 pow(a,b) 幂函数 ceil() 向上取整
    • abs() 获取绝对值 abs(5)=> 5 正数的绝对值就是本身 ， abs(-5)=> 5 负数绝对值是 正数
    • sqrt(n) 获取n的平方根 例如: sqrt(4) =>2 sqrt(9) =>3 sqrt(81)=> 9
    • pow(a,b) 获取 a的b次方 即 有b个a进行相乘
    • ceil(3.14) => 4 向上取整 即 超过 3 就取 4
  • 分支结构
    • if else 分支结构
    • if else if 多条件分支结构
    • switch case 分支结构
• Dynamic programming 动态规划
  • 动态规划问题 满足三个条件
    • 最优子结构性质
      • 原问题分解为相对简单的子问题，通过子问题求解最优从而获取原问题最优解
    • 无后效性
      • 已经求解的子问题，不会再受到后续子问题决策时的影响
    • 子问题重叠
      • 有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率
  • 动态规划解题基本思路 (1)划分阶段： (2)确定状态和状态变量 (3)确定决策并写出状态转移方程 (4)寻找边界条件
    • (1)划分阶段： 按照问题的时间或空间特征，把问题分为若干个阶段。 在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
    • (2)确定状态和状态变量： 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。 当然，状态的选择要满足无后效性。
    • (3)确定决策并写出状态转移方程： 因为决策和状态转移有着天然的联系， 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 所以如果确定了决策，状态转移方程也就可写出。 但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
    • (4)寻找边界条件： 给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了， 就可以写出状态转移方程（包括边界条件）。
  • 动态规划解题基本思路 动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化搜索，自底向上就是递推。
  • 动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化搜索，自底向上就是递推。
  • 背包问题
    • 问题集合
      • 爬楼梯
        • 一个人每次只能走1层楼梯或者2层楼梯，问走到第n层楼梯一共有多少种方法。
          • 递推边界 f[0] = 1, f[1] = 1 递推动态方程 f[i] = f[i-1]+f[i-2]
      • 疯狂的爬楼梯问题题
        • 一个人每次只能走2层楼梯，22层楼梯，222层楼梯，问走到第n层楼梯一共有多少种方法
          • 递推边界 f[0] = 1, f[1] = 1 递推动态方程 f[i] = f[i-2] + f[i-22] + f[i-222]
      • 超级疯狂的爬楼梯问题
        • 一个人每次最少走1层楼梯，最多t层楼梯。 问走到第n层楼梯一共有多少种方法。
          • 递推边界 f[0] = 1 递推动态方程 f[i] = f[i-1] + f[i-2] + f[i-t]
        • 其中有许多层楼梯上会有石头，求最少经过多少石头到达n层。 比如第1层有2个石头，第2层有10个石头，第3层有2个石头，每次最多走两层。
          • 如果i处没有有石头 f[i] = min(f[i – 1], f[i – 2] … f[i-k]) 如果i处有石头 f[i] = min(f[i-k]) + a[i]
      • 棋盘路径
        • 【问题描述】 已知棋盘上一共有64个点，如下图所示。现在想要从棋盘的起点A开始，完成向终点B的移动，并且规定只能经由棋盘上的各点水平左移或垂直下移，走过的路不允许重复，那么请问，完成A点向B点的移动，共有几种可 能的路线呢?
          • 第一行 或 第一列 只有 1种走法 动态转移方程 a[i][j] = a[i-1][j] +a[i][j-1]
      • 0/1背包问题
      • 完全背包问题
      • 多维背包问题
  • 子主题
• 主题
• 双击编辑文本
• 主题