个人网站域名备案,wordpress 缓存在那,拼多多seo搜索优化,招标网站开发文档算法分析与设计考前冲刺
算法基础
算法是一系列解决问题的清晰指令#xff0c;代表着用系统的方法描述解决问题的策略机制。
程序是算法用某种程序设计语言的具体的 具体实现
算法特征#xff1a; 有穷性(有限步) 确定性 输入 输出 可行性(有限时间)
算法的复杂性#…算法分析与设计考前冲刺
算法基础
算法是一系列解决问题的清晰指令代表着用系统的方法描述解决问题的策略机制。
程序是算法用某种程序设计语言的具体的 具体实现
算法特征 有穷性(有限步) 确定性 输入 输出 可行性(有限时间)
算法的复杂性 时间复杂性 和空间复杂性(算法消耗的内存空间) 数据结构与STL
栈 先进后出
向量 动态数组可以随机存储
Map 有key和value 底层是红黑树按照key自动进行排序
list 线性链表
set 内部元素不允许重复
队列 先进先出
优先队列最大的元素位于队首 最大的元素优先出队 递归和分治
分治原问题可以拆分为多个子问题子问题之间相互独立且 与 原问题形式相同
分治步骤 分解 解决 合并
Fab数列
int fib(int n) //声明一个函数fib它接受一个整数参数n并返回一个整数。
{ if (n1) 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 i2; in; i)fib[i] fib[i-1]fib[i-2]; }二分:
int BinarySearch(Type a[],const Type x,int n)
{int left0; int rightn-1; while(leftright)//左闭右闭{int middle(leftright)1;if (xa[middle]) return middle; if (xa[middle]) leftmiddle1; else rightmiddle-1; }
return -1; //如果循环结束后仍然没有找到目标元素
}
二分
int BinarySearch(Type a[],const Type x,int n)
{int left0; int rightn; while(leftright)//左闭右开{int middle(leftright)1;if (xa[middle]) return middle; if (xa[middle]) leftmiddle1; //middle已经判断不是了else rightmiddle; //不-1 因为是左闭右开 }
return -1; //如果循环结束后仍然没有找到目标元素
}动态规划
场景通常用与求解具有某种 最优性质 的问题
思想是将待求解问题分解成若干个 不独立的子问题 先求解子问题将子问题的答案记录在表格
步骤
找出最优解的性质,并刻画其结构特征确定状态转移方程以自底向上的方式计算出最优值根据计算最优值时得到的信息构造一个最优解。
性质 最优子结构 重叠子问题
0-1背包
解法一
#includeiostream
#includealgorithm
using namespace std;
const int M1010;
int w[M],v[M];
int dp[M][M];
int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]w[i];}for(int i1;in;i){for(int j0;jm;j){ //两层循环都正序遍历 因为dp[i][j] 是由上面的元素和左上方得到的dp[i][j]dp[i-1][j];//表示不选择第i键物品if (jv[i]){//当背包容量大于物品体积的时候取最大值dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i]);}}}coutdp[n][m]endl;return 0;
}
解法二
#includeiostream
#includealgorithm
#include cstdio
using namespace std;
const int M1010;
const int N1e610;
int w[M],v[M];
int dp[M];int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]w[i];}for(int i1;in;i){for(int jm;jv[i];j--){//倒序遍历不然会存在覆盖的问题dp[j]max(dp[j],dp[j-v[i]]w[i]);}}coutdp[m]endl;return 0;}
贪心算法
场景只考虑当前最好的选择讲原问题化成一个更小的与原问题具有相同形式的子问题
特点只考虑局部最优不从整体最优考虑
最优解有的适合可能是很好的一个近似解
选硬币
现有面值分别为1角1分5分1分的硬币请给出找1角5分钱的最佳方案。
#include iostream
#include vectorstd::vectorint findChange(int amount) {std::vectorint coins {10, 5, 1}; // 按面值从大到小排序的硬币面值std::vectorint 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::vectorint 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].wcleft) //这里的a[i]是一个结构体数组 元素包括重量、价值即(v,w性价比){cleft - a[i].w;b a[i].v;i;}// 物品可拆分 a[i].v/a[i].w 是i物品的单位价值if (in) b 1.0*a[i].v*cleft/a[i].w;//凑满背包
return b;
} 总结背包问题贪心贪在你优先按照性价比降序排列每次优先考虑价值最高的物品
回溯算法
核心组织搜索 搜索一个问题的所有解
思想
用约束函数在扩展结点处减去不满足约束条件的子树用限界函数减去不能得到最优解的子树。
素数环问题
素数环从1到20这20个数摆成一个环要求相邻的两个数的和是一个素数。
//判断质数
bool pd(int x,int y){int k2,ixy;while (ksqrt(i)i%k!0) k; //if (ksqrt(i)) return true;//遍历半圈没有找到else return false;//前面能被整除
}void search(int t){ int i;for (i1;i20;i) if (pd(a[t-1],i)(!b[i])){ //判断当前数和前一位的和是不是素数同时 当前元素没有出现过a[t]i; //放入b[i]1; //出现一次if (t20) {
if (pd(a[20],a[1])) print(); }//注意边界 最后一个和第一个是连着的else
search(t1); //递归寻找下一个数字b[i]0;//回溯}
}int print(){total;couttotal;for (int j1;j20;j)couta[j] ;coutendl; }
