网站设计中 查询怎么做,在登录某些网站时输入完账号密码后网页跳转后竟然又回到了登陆界面,做电子商务网站的总结,兰州建设算法
查找算法#xff1a;
顺序查找#xff1a;
基本思想#xff1a;
顺序查找也称为线形查找#xff0c;属于无序查找算法。从数据结构线形表的一端开始#xff0c;顺序扫描#xff0c;依次将扫描到的结点关键字与给定值k相比较#xff0c;若相等则表示查找成功
顺序查找
基本思想
顺序查找也称为线形查找属于无序查找算法。从数据结构线形表的一端开始顺序扫描依次将扫描到的结点关键字与给定值k相比较若相等则表示查找成功若扫描结束仍没有找到关键字等于k的结点表示查找失败(-1)
时间复杂度
查找成功时的平均查找长度为假设每个数据元素的概率相等 ASL 1/n(123…n) (n1)/2 ;当查找不成功时需要n1次比较时间复杂度为O(n);
所以顺序查找的时间复杂度为O(n)。
基本程序
int SequenceSearch(int a[], int value, int n){
for(int i0; in; i){if(a[i] value){return i;}
}
return -1;
}二分查找
前提条件
元素必须是有序的如果是无序的则要先进行排序操作
基本思想
二分查找也称为是折半查找属于有序查找算法。用给定值k先与中间结点的关键字比较中间结点把线形表分成两个子表若相等则查找成功若不相等再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表这样递归进行直到查找到或查找结束发现表中没有这样的结点
时间复杂度
最坏情况下关键词比较次数为log2(n1)且期望时间复杂度为O(log2n)
基本程序
int BinarySearch1(int a[], int value, int n){int low, high, mid;low 0;high n-1;while(lowhigh){mid (lowhigh)/2;if(a[mid]value){return mid;}else if(a[mid]value){high mid-1;}else if(a[mid]value){low mid1;}}return -1;
}注折半查找的前提条件是需要有序表顺序存储对于静态查找表一次排序后不再变化折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说维护有序的排序会带来不小的工作量那就不建议用 ——《大话数据结构》
排序算法
比较排序
冒泡排序
简介
冒泡排序英语Bubble Sort又称为泡式排序是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
时间/空间复杂度
时间复杂度最坏情况下为O(n2)最坏情况下为O(n)平均下来约为O(n2)
空间复杂度为O(1)
稳定性
因排序后相同数字的顺序不变所以为稳定
代码
基础法
void bubblesort(int a[],int n){for (int i n - 1; i 0; i--) {for (int j 0; j i; j) {if (a[j] a[j 1])swap (a[j], a[j 1]);}}
}提速法
void bubble_sort(int a[],int n){bool flagtrue;while (flag){flagfalse;for (int i1;in;i){//检查一遍if (a[i]a[i-1]){//如果当前数大于前一个falgtrue;swap(a[i],a[i-1]);//调换位置}else {//如果不是就将falg设为false然后就会跳出循环falgfalse;}}}
}选择排序
简介
选择排序 Selection sort是一种简单直观的排序算法。一般是初学者接触的第一个排序算法简称为选排。它的工作原理是每一趟从待排序的数据元素中选出最小或最大的一个元素顺序放在已排好序的数列的最后直到全部待排序的数据元素排完
时间/空间复杂度
时间复杂度在最好的情况下为O(n2)在最坏得到情况下也是O(n2)所以平均时间复杂度也是O(n^2)
空间复杂度为O(1)
稳定性
因为排序完成后两个相同数字的数的顺序变了所以为不稳定
代码
void selection_sort(int a[],int n){int k;for (int i0;in;i){ki;for (int ji;jn;j){if (a[j]a[k]){//在未排序区域找最小值kj;//并将k设为当前的编号}}swap(a[i],a[k]);}
}插入排序
简介
直接插入排序是将无序序列中的数据插入到有序的序列中在遍历无序序列时首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置一直到无序序列中的所有元素插完为止即每一步将一个待排序的数据插入到前面已经排好序的有序序列中直到插完所有元素为止
时间/空间复杂度
在最好的情况下时间复杂度为O(n)最坏情况下为O(n2)所以平均时间复杂度为O(n2)
空间复杂度为O(1)
稳定性
因为排序后相同的数字的位置不变所以为稳定
代码
void insertsort(int a[],int n){for (int i1;in;i){int keya[i];int ji-1;while (j0a[j]key){//寻找位置并挪移a[j1]a[j];j--;}a[j1]key;//储存}
}非比较排序
计数排序
简介
对于每一个输入元素 x确定小于 x 的元素个数利用这一信息就可以直接把 x 放到它在输出数组中的位置上了。例如如果有 17 个元素小于 x 则 x就应该在第 18 个输出位置上。当有几个元素相同时这一方案要略做修改因为不能把他们放在同一个输出位置上
时间/空间复杂度
时间复杂度在最好情况和最坏情况下都为O(nk)所以平均时间复杂度也为O(nk)
空间复杂度为o(k)
稳定性
因为排序完成后相同数字的位置不变所以为稳定
代码
void counting_sort(int a[],n){int b[100000],cnt[100000];//b为顺序for (int i 0; i n; i) {b[a[i]];//存储每一个数比他小的数的个数}for (int i1;in;i){b[i]b[i-1];}//计算前缀和for (int in-1;i0;i--){cnt[b[a[i]]--]a[i];//放入对应的位置}
}贪心算法
本质
利用贪心算法对问题求解时考虑的并不是对于整体最好的策略而是总是做出当前看来最好的选择即贪心算法所作出的选择仅仅是在某种情况下的局部最优解
思路
1.建立数学模型来解决问题
2.把求解的问题分解成多个子问题类似于递归
3.对每个子问题进行求解局部最优解
4.将数据归纳合并成原来问题的一个解
实现框架
while/* 或 for */(/*所写内容向给定的总目标前进一步*/){//利用可行的策略求解出一个可行的元素并保存}
//由所有可行的元素合成一个可行的解注意事项
贪心算法并不能一定得到最优解它只是局部的最优解所以使用贪心算法有一个大前提就是局部的最优策略可以产生全局的最优解除此之外任何情况都不能完全的使用贪心算法但有些时候可以利用贪心算法的部分思想
例题分析
简单贪心算法
小明去购物想要买的食品如下当前小明能拎回的重量不超过15斤那么小明能拎回的食品的数量最多为
食物牛奶面包方便面苹果饼干榴莲西瓜重量/斤4.5123.32.86.28.4
分析思路
想要得到最多的食品那么利用贪心算法的策略就应该是每次都选择当前最轻的这样最后拿到的总数才最多
实现过程
首先对当前食品按照重量从小到大的顺序进行排序排序结果如下
i0123456食物面包方便面饼干苹果牛奶榴莲西瓜重量/斤122.83.34.56.28.4
然后按照贪心策略进行选择过程如下
i0放入后当前重量为1不超过15可以现在的总数量加1
i1放入后当前重量为3不超过15可以现在的总数量加1
i2放入后当前重量为5.8不超过15可以现在的总数量加1
i3放入后当前重量为9.1不超过15可以现在的总数量加1
i4放入后当前重量为13.6不超过15可以现在的总数量加1
i5放入后当前重量为19.8超过15不可以现在的总数量不变
i6放入后当前重量为22超过15不可以现在的总数量不变
综上可以得知最多可以带回去的数量为5
样例代码
double w;//能拎动的的食品的总重量
int n,sum0,tmp0;//n为想买的总数量sum为能拎回去的总数量tmp为当前准备拎回去的食品的重量
double wg[10];//想买的每件食品的重量
sort(wg,wgn);//按照从小到大的顺序进行排序
for (int i0;in;i){//贪心算法tmpwg[i];if (tmptw){//如果当前重量小于或等于能拎动的总数量sum;//就将能拎回去的总数量加1}else{break;//否则就跳出循环}
}复杂贪心算法
如果这时小明想要让拎回去的价值最高那么这个价格又是多少呢其他条件与上题一样
食物牛奶面包方便面苹果饼干榴莲西瓜价格/元1837.815.8899.220.2重量/斤4.5123.32.86.28.4
分析思路
根据贪心算法现在每一次所选择的食品的价格必须是最高的但是价格高的食物也有可能很重所以这时我们就要考虑一个新的东西——性价比或单价即价格/重量那么由此就可以按照性价比从大到小进行排序然后按照贪心算法进行选择每一次性价比最高的食品并进行比较看看重量增加后是否还能拎回去
实验过程
首先按照性价比由大到小进行排序结果如下
食物榴莲苹果牛奶方便面饼干面包西瓜价格/元99.215.8187.88320.2重量/斤6.23.34.522.518.4性价比164.843.93.232.4i0123456
然后按照贪心策略进行选择过程如下
i0放入后重量为6.2不超过15可以此时总价值为99.2
i1放入后重量为9.5不超过15可以此时总价值为115
i2放入后重量为14不超过15可以此时总价值为133
i3放入后重量为16超过15不可以此时总价值为133
i4放入后重量为16.5超过15不可以此时总价值为133
i5放入后重量为15不超过15可以此时总价值为136
i6放入后重量为23.4超过15不可以此时总价值为136
综上可知小明能够带回去的食品的最大价值为136元
样例代码
struct food{double w,p,j;//w为重量p为价格j为性价比
}wg[10];
double k,tmp;//k能拎动的的食品的总重量tmp为当前准备拎回去的食品的重量
int n,sum;//n为想买的总数量sum为能拎回去的总资产
sort (wg,wgn,cmp);//按照性价比从大到小进行排序
for (int i0;in;i){//贪心算法tmpw[i].w;if (tmpk){//如果可以拎动sumw[i].p;//就将总资产加上当前这个食品的价格}else {tmp-w[i].w;//否则就从准备拎回去的食品的重量里删除当前食品的重量}
}洛谷例题【深基12.例1】部分背包问题
题目描述
阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N 100)堆金币第 i 堆金币的总重量和总价值分别是 mi,vi(1mi,vi 100)。阿里巴巴有一个承重量为 T(T 1000)的背包但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割分割完的金币重量价值比也就是单位价格不变。请问阿里巴巴最多可以拿走多少价值的金币
输入格式
第一行两个整数 N,T。
接下来 N行每行两个整数 mi,vi。
输出格式
一个实数表示答案输出两位小数
样例输入 #1
4 50
10 60
20 100
30 120
15 45样例输出 #1
240.00分析思路
因为金币可以分割所以可以用性价比来排序从大到小从而获得结果
样例代码
#include bits/stdc.h
using namespace std;double value;
struct gold{double m,v,o;
}a[120];bool cmp(gold a1,gold a2){return a1.oa2.o;
}int main() {int n,t;cinnt;for (int i0;in;i){cina[i].ma[i].v;a[i].oa[i].v/a[i].m;}sort(a,an,cmp);for (int i0;in;i){if (a[i].mt){t-a[i].m;valuea[i].v;}else if (t0ta[i].m){valuet*a[i].o;break;}}printf(%.2lf,value);return 0;
}
分治算法
本质
分治算法如同字面上说的一样就是把一个大问题分解成多个小问题再把每个小问题再分解成更小的问题直到每一个问题都能够简单的求解为止向上归纳就可以得出原问题的答案为所有小问题的解的合并
思路
1建立二叉树模型
2将求解的问题分解成多个子问题然后继续分解直到能简单求解为止
3从最后一层开始向上递推直到求出原问题的解
实现框架
int que(int q){//建立函数if (){//如果条件成立即可以简单求解return ;//就返回求解答案}return ;//如果不可以就继续分解
}注意事项
如果遇到数据集较小的题目建议不要使用分治算法这样不仅浪费时间还会浪费空间很容易错失良机
例题分析
已知有n个数10000a[i]放在数组a中请用分治算法求解这n个数中的最大值
分析思路
想要解决这个问题第一步就是要“分”顾名思义就是按照二分法将原问题分解成简单的子问题第二步就是“治”了即从最下一层开始向上反推逐步和解最终得出答案
实现过程
分
将{4355623452332592495511214223407436467}
分成{43556234523325924955}与{11214223407436467}
继续分为{4355623452}与{3325924955}与{112142234074}与{36467}
现在已经可以比较了所以进行“治”
治
{4355623452}中得出大者为43556{3325924955}中得出大者为33259{112142234074}中得出大者为234074{36467}中得出大者为36467
归纳上去可得到{4355633259}与{23407436467}
继续比较可从{4355633259}中得出大者为43556{23407436467}中得出大者为234074
再次归纳可得到{43556234074}
再次比较可从{43556234074}得出最大者为234074
至此算法结束可得到最大者为234074
样例代码
int max(inr a[],int i,int j){//i为左边界j为右边界int num10;num20;//为下处比较使用if (ij)return a[i];//如果左右边界相等即此时只有一个数据就直接返回这个数据else if (ij-1){//如果左边界等于右边界-1即此时有两个数据就返回大的那个数据if (a[i]a[j)return a[i];else return a[j];}else {//如果不是就按照二分法再次进行分段int mid(ij)/2;//取中点//利用递归进行寻找num1max(a,i,mid);num2max(a,mid,j);if (num1num2)return num1;//比较大小返回大值else return num2;}
}回溯算法
本质
即在搜索的尝试过程中当发已经满足不了求解条件是利用**“回溯”返回**到上一步重新选择路线
思路
1正常进行寻找和判断
2将一条路探索完
3返回到上一次选择方向的地点
实现框架
模式一
int search(int k){for (int i0;in/*n为算法总数*/;i){if(/*满足条件*/){//保存结果}if(/*到达目标*/){//输出结果}else {search(k1);}//恢复到保存结果之前的状态即回溯一步}
}模式二
int search(int k){if (/*到达目标*/){//输出结果}else {for (int i0;in/*n为算法总数*/;i){if ((/*满足条件*/){//保存结果search(k1);//恢复到保存结果之前的状态即回溯一步}}}
}注意事项
回溯算法利用的是深度优先搜索的思想这种算法会很容易超时容易崩端所以在使用的时候一定要留足时间
例题分析
已知一个迷宫以及迷宫的入口和出口现从迷宫的入口进入看看是否存在一条路通往出口如果存在输出“YES”如果不存在就输出“NO”
迷宫造型如下灰色代表墙壁
分析思路
我们利用“搜索与回溯”的方法进行寻找即从入口开始顺着某一方向进行探索如果能走通就继续往下走如果不行就原路返回换一个方向继续探索直到所有的路都探索完位置如果全部都探索完了仍然没有路可以通往出口就说明没有通往出口的道路
实验过程 上图解释
从入口开始探索先向右探索探索两个后碰壁a调整方向b、c、d最后发现无路可走回溯到上一步。
方向调为向下到下一格向右探索e碰壁向下探索一步在此基础上向右探索成功继续直到碰壁g调整方向向下到达出口成功探索结束输出YES
样例代码
int dx[4]{1,0,-1,0};
int dy[4]{0,-1,0,1};
//初始化前下后上
int x,y,x1,y1,nx,ny,n;
bool visited[100][100],flagfalse;
int dfs(int x,int y){if (xx1yy1){//到达coutYESendl;flagtrue;return 1;}for (int i0;i4;i){//搜索四个方向nxxdx[i];nyydy[i];if (nx0||nxn||ny0||nyn){//判断是否越界continue;}if (visited[nx][ny]false){visited[nx][ny]true;//标记为走过dfe(nx,ny);//然后在此基础上继续往下探索visited[nx][ny]false;//回溯即标记为未走过}}return 0;
}
