X03上课笔记
2024-08-06 13:56:44
发布于：上海
分治法：
对于一个规模为N的问题，若该问题可以容易地解决则直接解决，否则将其分解为M个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到得原问题的解。这种算法设计叫做分治法
分制的核心代码主要集中在分解和合并
分治法适用条件
-
该问题的规模缩小到一定的程度就可以容易地解决
-
该问题可以分解为若干个规模较小的相同问题
-
利用该问题分解出的子问题的解可以合并为该问题的解
-
该问题所分解出的各子问题是相互独立的
快排
引例：对一个长度为N的序列a[n]，按照从小到大排序
#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
void qs(int x,int y){
if(x>=y) return ;
int l=x,r=y,f=1;
while(l<r){
if(a[l]>a[r]){
swap(a[l],a[r]);
f=!f;
}
f?r--:l++;
}
qs(x,l-1);
qs(r+1,y);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
qs(1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
以上为从小到大排序
归并排序
将给定的包含n个元素的局部数组“分割”成两个局部数组，每个数组包含个
【归并排序】合并
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005],b[10005],c[10005];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
int l=0,r=0,lc=0;
while(l<n&&r<m){
c[lc++]=(a[l]<b[r]?a[l++]:b[r++]);
}
while(l<n) c[lc++]=a[l++];
while(r<m) c[lc++]=b[r++];
for(int i=0;i<lc;i++)cout<<c[i]<<" ";
return 0;
}
【归并排序】划分
#include<bits/stdc++.h>
using namespace std;
int n,a[101];
void ms(int l,int r){
if(l>=r) return ;
int x=(l+r)/2;
cout<<"[";
for(int i=l;i<=x;i++){
cout<<a[i]<<" ";
}
cout<<"],[";
for(int i=x+1;i<=r;i++){
cout<<a[i]<<" ";
}
cout<<"]"<<endl;
ms(l,x);
ms(x+1,r);
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
ms(0,n-1);
return 0;
}
【归并排序】升序
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010];
void ms(int l,int r){
if(l>=r) return ;
int s=(l+r)/2;
ms(l,s);
ms(s+1,r);
int x=l,y=s+1,lc=l;
while(x<=s&&y<=r){
b[lc++]=(a[x]<a[y]?a[x++]:a[y++]);
}
while(x<=s) b[lc++]=a[x++];
while(y<=r) b[lc++]=a[y++];
for(int i=l;i<=r;i++){
a[i]=b[i];
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
ms(0,n-1);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
希尔排序
这个我蹭的
传送门
哈夫曼树（最优二叉树）
带权路径长度最短的树称为哈夫曼树，又称为最优二叉树。哈夫曼树通常为二叉树。
哈夫曼树的定义
对于给定带有各自权值的 个结点，构造哈夫曼树：
在n个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树的左右孩子
删除使用过的两个权值，将新的权值加入到权值集合中。
重复 1 和 2 ，直到无法再选出两个权值，此时这个二叉树就是哈夫曼树。
哈夫曼编码
在数据传送时，信息表现为0和1的二进制形式。为了提高传输速度，可以采用变长的编码方式，寻找更优的编码方式。
二叉搜索树
若它的左子树不为空，则左子树上所有的结点的值都小于它的根节点
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值
拓扑排序
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
入度
在有向图中，一个顶点v的入度指与该条边向关联的入边的条数。
出度
在有向图中，一个顶点v的入度指与该条边向关联的出边的条数。
有帮助，赞一个