算法分析与设计考前冲刺 （算法基础、数据结构与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); 
}

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]; }

二分:

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; //如果循环结束后仍然没有找到目标元素
}	

二分：

int BinarySearch(Type a[],const Type& x,int n)
{int left=0; int right=n; while(left<right)//左闭右开{int middle=(left+right)>>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. 根据计算最优值时得到的信息，构造一个最优解。

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

0-1背包：

解法一：

#include<iostream>
#include<algorithm>
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<<dp[n][m]<<endl;return 0;
}

解法二：

#include<iostream>
#include<algorithm>
#include <cstdio>
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<<dp[m]<<endl;return 0;}

贪心算法

场景：只考虑当前最好的选择，讲原问题化成一个更小的与原问题具有相同形式的子问题

特点：只考虑局部最优，不从整体最优考虑

最优解有的适合可能是很好的一个近似解

选硬币：

现有面值分别为1角1分，5分，1分的硬币，请给出找1角5分钱的最佳方案。

#include <iostream>
#include <vector>std::vector<int> findChange(int amount) {std::vector<int> coins = {10, 5, 1}; // 按面值从大到小排序的硬币面值std::vector<int> result(coins.size(), 0); // 用于存储每种硬币的数量for (int i = 0; i < coins.size(); i++) {int numCoins = amount / coins[i]; // 计算当前硬币面值的数量result[i] = numCoins; // 存储数量amount -= numCoins * coins[i]; // 更新剩余金额}return result;
}int main() {int amount = 15; // 需要找零的金额，单位为分std::vector<int> change = findChange(amount);std::cout << "找零方案为：" << std::endl;std::cout << "1角1分硬币数量：" << change[0] << std::endl;std::cout << "5分硬币数量：" << change[1] << std::endl;std::cout << "1分硬币数量：" << change[2] << std::endl;return 0;
}

思路：不需要想的很清楚，想一下生活中的找钱，如果别人给你100元，花了15元，你应该是先找给他50元然后在其20 10 5，(这里默认每一种都有无数张)，这就是一个贪心，贪心贪在你每次都找给他最大的，可能这个还是不是很好理解，就是1元可以给任何钱找钱，而50元只有大于50元我才可以找找，很多时候无形之中就已经使用了贪心。

背包问题：

下面是贪心做法：

//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序
double knapsack(int n, bag a[], double c)
{double cleft = c; //背包的剩余容量int i = 0;//下标double b = 0; //获得的价值//当背包还能完全装入物品iwhile(i	<n && a[i].w<cleft) //这里的a[i]是一个结构体数组 元素包括重量、价值即(v,w，性价比){cleft -= a[i].w;b += a[i].v;i++;}// 物品可拆分   a[i].v/a[i].w 是i物品的单位价值if (i<n) b += 1.0*a[i].v*cleft/a[i].w;//凑满背包
return b;
} 

总结：背包问题贪心贪在，你优先按照性价比降序排列，每次优先考虑价值最高的物品

回溯算法

核心：组织搜索 搜索一个问题的所有解

思想：

1. 用约束函数在扩展结点处减去不满足约束条件的子树；
2. 用限界函数减去不能得到最优解的子树。

素数环问题：

素数环，从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

//判断质数
bool pd(int x,int y){int k=2,i=x+y;while (k<=sqrt(i)&&i%k!=0) k++; //if (k>sqrt(i)) return true;//遍历半圈没有找到else return false;//前面能被整除 
}

void search(int t){ int i;for (i=1;i<=20;i++) if (pd(a[t-1],i)&&(!b[i])){ //判断当前数和前一位的和是不是素数同时 当前元素没有出现过a[t]=i; //放入b[i]=1; //出现一次if (t==20) { 
if (pd(a[20],a[1])) print(); }//注意边界 最后一个和第一个是连着的else 
search(t+1); //递归寻找下一个数字b[i]=0;//回溯}
}

int print(){total++;cout<<"<"<<total<<">";for (int j=1;j<=20;j++)cout<<a[j]<<" ";cout<<endl; }