算法分析与设计考前冲刺 （算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法）

算法分析与设计考前冲刺

算法基础

算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。

程序是算法用某种程序设计语言的具体的 具体实现

算法特征： 有穷性(有限步) 确定性 输入 输出 可行性(有限时间)

算法的复杂性： 时间复杂性 和空间复杂性(算法消耗的内存空间)

---

数据结构与STL

栈： 先进后出

向量： 动态数组，可以随机存储

Map： 有key和value 底层是红黑树，按照key自动进行排序

list： 线性链表

set： 内部元素不允许重复

队列： 先进先出

优先队列：最大的元素位于队首 ，最大的元素优先出队

---

递归和分治

分治：原问题可以拆分为多个子问题，子问题之间相互独立且 与 原问题形式相同

分治步骤： 分解 解决 合并

Fab数列：

int fib(int n) //声明一个函数fib，它接受一个整数参数n，并返回一个整数。
{  if (n<=1) return 1;
		return fib(n-1)+fib(n-2); 
}
1
2
3
4

int fib[50];
void fibonacci(int n) //定义了一个名为 fibonacci 的函数，它接受一个整数参数 n
{
        fib[0] = 1;
        fib[1] = 1; 
        for (int i=2; i<=n; i++)
        fib[i] = fib[i-1]+fib[i-2]; 
        }
1
2
3
4
5
6
7
8

二分:

int BinarySearch(Type a[],const Type& x,int n)
{
    int left=0; 
    int right=n-1; 
    while(left<=right)//左闭右闭
        {
        int middle=(left+right)>>1;
        if (x==a[middle]) return middle; 
        if (x>a[middle]) left=middle+1; 
        else right=middle-1; 
        }
return -1; //如果循环结束后仍然没有找到目标元素
}	

1
2
3
4
5
6
7
8
9
10
11
12
13
14

二分：

int BinarySearch(Type a[],const Type& x,int n)
{
    int left=0; 
    int right=n; 
    while(left>1;
        if (x==a[middle]) return middle; 
        if (x>a[middle]) left=middle+1; //middle已经判断不是了
        else right=middle; //不-1 因为是左闭右开 
        }
return -1; //如果循环结束后仍然没有找到目标元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

动态规划：

场景：通常用与求解具有某种 最优性质 的问题

思想：是将待求解问题分解成若干个 不独立的子问题 ，先求解子问题，将子问题的答案记录在表格

步骤：

1. 找出最优解的性质,并刻画其结构特征；
2. 确定状态转移方程
3. 以自底向上的方式计算出最优值；
4. 根据计算最优值时得到的信息，构造一个最优解。

性质： 最优子结构 重叠子问题

0-1背包：

解法一：

#include
#include
using namespace std;
const int M=1010;
int w[M],v[M];
int dp[M][M];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){  //两层循环都正序遍历 因为dp[i][j] 是由上面的元素和左上方得到的
            dp[i][j]=dp[i-1][j];//表示不选择第i键物品
            if (j>=v[i]){//当背包容量大于物品体积的时候取最大值
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }
        }

    }
    cout<

#include
#include
#include 
using namespace std;
const int M=1010;
const int N=1e6+10;
int w[M],v[M];
int dp[M];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){//倒序遍历不然会存在覆盖的问题
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<