算法设计与分析复习代码（hnust）

//第8章·概率方法
//1.随机方法改写快排
template<class T>
int Partition(T X[],int low,int up){int key=rand()%(up-low)+low; swap(X[key],X[up-1]);key=up-1; for(int i=low;i<up;i++)if(X[i]<X[key])swap(X[i],X[low++]); swap(X[key],X[low]); return low; 
}template<class T>
void QuickSort(T X[],int low,int up){if(up-low<=1) return ; int m=Partition(X,low,up); QuickSort(X,low,m); QuickSort(X,m+1,up); 
}//2.随机化基于划分的线性时间选择程序
template<class T>
auto Select(T X[],int n,int k){int low=0,up=n; while(1){int m=(low+up)/2; if(m==k) return X[m]; else if(m>k) up=k; else low=m+1; }
}//3.随机洗牌
template<class T>
void Shuffle(T X[],int n){while(--n)swap(X[n],X[rand()%n]); 
}//4.旅行商的拉斯维加斯算法(是否存在费用不超过t的旅行)，单次O(n)
bool TSP(const Matrix<double>&G,double t,vector<int>&X){int n=G.rows(); iota(begin(X),end(X),0); random_shuffle(begin(x),end(x)); double s=0; for(int i=0;i<n;i++){s+=G(X[i],X[(i+1)%n]); if(s>t) return false; }return true; 
}//5.0/1背包问题（是否存在效益和不少于t的装包方式）的拉斯维加斯算法，要求一次执行的耗时为O(n)
bool Knap(const vector<double> &V, const vector<double> &W, double c, double t,vector<bool> &X){int n=min(size(W),size(V)); int fv=0,fw=0; for(int i=0;i<n;i++){X[i]=rand()%2; if(X[i]) fv+=V[i],fw+=W[i]; if(fw>c) return false; }return fv>=t;
}//6.请为团问题（是否存在顶点数不少于k的团）设计一个错误概率低于0.25的
//蒙特卡洛算法，要求一次执行的耗时为O(n^2)。该算法的C++函数原型规定为bool Clique(const Matrix<bool> &G, int k, vector<bool> &X){int n=G.rows(); vector<int>V(n); iota(begin(V),end(V),0); random_shuffle(begin(V),end(V)); for(auto t:V){if(Connected(G,X,t))X[t]=1; }return count(begin(X),end(X),1)>=k; 
}//7.请使用概率方法设计一个判断一个给定的整数函数f(x)是否恒等于0的蒙特
//卡洛算法，并使用一种程序设计语言描述该算法，其C/C++的函数原型为
bool iszero(int f(int), int m){for(int i=0;i<m;i++)if(f(rand())!=0) return false; return true; 
}//第7章·分支限界方法
//1.宽度优先方法生成含n个分量的所有排列的程序
struct Node{vector<int>X; int t; 
}
void Perm(int n){queue<Node>q; vector<int>X(n); iota(begin(X),end(X),0); q.push({X,0}); while(q.size()){auto [X,t]=q.front(),q.pop(); if(t>=n){cout<<X<<endl; continue; }for(int i=t;i<n;i++){swap(X[i],X[t]); q.push({X,t+1});}}
}//2.编写一个使用宽度优先方法生成n个元素的所有子集的程序。该程序的C++函数原型规定为
struct Node{vector<bool>X; int t; 
}
void SubSet(int n){queue<Node>q; vector<bool>X(n); q.push({X,0}); while(q.size()){auto [X,t]=q.front(),q.pop(); if(t>=n){cout<<X<<endl; continue; }X[t]=1; q.push({X,t+1}); X[t]=0; q.push({X,t+1}); }
}//3.旅行商问题（输出最优解）的分枝限界算法。该算法的C++函数原型规定为
struct Node{vector<int>X;int t; double s;  
}; bool operator<(const Node X,const Node Y){return X.s<Y.s; 
}
auto TSP(const Matrix<double> &G){int n=G.rows(); double fc=inf; vector<bool>X(n),BX; iota(begin(X),end(X),0); minheap<Node>q; q.push({X,1,0}); while(q.size()){auto [X,t,s]=q.top(); q.pop(); if(t>=n){if(c+G(X[n-1],0)<fc){fc=c+G(X[n-1],0); BX=X; }continue; }for(int i=t; i<n;i++){swap(X[t],X[i]); if(c+G(X[t-1],X[t])<fc)q.push(X,t+1,c+G(X[t-1],X[t])); }}return BX; 
}//4.述最大团问题（输出一个最大团）的分枝限界算法。该算法的C++函数原型规定为
struct Node{vector<bool>X; int t; int cn; 
}
bool operator<(const Node X,const Node Y){return X.cn<Y.cn;
}
auto Clique(const Matrix<bool> &G){int n=G.rows(); vector<bool>X(n),BX;int fn=0; maxheap<node>q; q.push({X,0,0});while(q.size()){auto [X,t,cn]=q.top(),q.pop(); if(t>=n){if(cn>fn){fn=cn,BX=X; }continue; }X[t]=1; if(Connected(G,X,t)) q.push({X,t+1,cn+1}); X[t]=0; if(cn+n-(t+1)>fn)q.push({X,t+1,cn}); }return BX; 
}//5.子集和问题（是否有和为t的子集）的分枝限界算法，要求输出一个满足条件的子集，或报告不存在满足条件的子集
struct Node{vector<bool>X; int t; int s,up; 
}
auto SetSum(const vector<int> &W, int M){int n=size(W); vector<bool>X(n,false); queue<Node>q; int sum=accumulate(begin(w),end(W),0); q.push({X,0,0,sum}); while(q.size()){auto [X,t,s,up]=q.front(),q.pop(); if(s==M){BY=X; BY.resize(t); }if(t>=n) continue; X[t]=1; if(s+W[t]<=M) q.push({X,t+1,s+W[t],up-W[t]}); X[t]=0; if(s+up-W[t]>=M) q.push({X,t+1,s,up-W[t]}); }return BX; 
}//第6章·回溯方法
//深度优先方法生成含n个分量的所有排列
void Perm(int n){vetor<int>X(n); iota(begin(X),end(X),0); function<void(int)> perm=[&](int t){if(t>=n){cout<<X<<endl; return; }for(int i=t;i<n;i++){swap(X[t],X[i]); perm(t+1); swap(X[t],X[i]); }};perm(0); 
}//深度优先方法生成n个元素的所有子集
void SubSet(int n){vector<bool>X(n,false); function<void(int)> subset = [&](int t){if(t>=n){cout<<X<<endl; return; }X[t]=1; subset(t+1); X[t]=0; subset(t+1); };subset(0); 
}//3.描述旅行商问题（输出最优解）的回溯算法auto TSP(const Matrix<double> &G){int n=G.rows(); vector<int>X(n),BX; iota(begin(X),end(X),0); double fc=inf; function<void<int,double>> TSP = [&](int t,double c){if(t>=n){if(c+G(X[n-1],0)<fc){fc=c+G(X[n-1],0),BX=X; }return ;}for(int i=t;i<n;i++){swap(X[t],X[i]); if(c+G(X[t-1],X[t])<fc)TSP(t+1,c+G(X[t-1],X[t]));swap(X[t],X[i]); }}; TSP(1,0); return BX; 
}//4.最大团问题（输出一个最大团）的回溯算法
bool Connected(const Matrix<bool>& G,vector<bool>X,int t){int n=G.rows(); for(int i=0;i<n;i++){if(i==t) continue; if(X[i]==1 and G(i,t)==0) return false; }return true; 
}auto Clique(const Matrix<bool> &G){int n=G.rows(); vector<bool>X(n),BX; int fn=0; function<void(int,int)> Clique=[&](int t,int cn){if(t>=n){if(cn>fn){fn=cn,BX=X; }return ; }X[t]=1; if(Connected(G,X,t))Clique(t+1,cn+1); X[t]=0; if(cn+n-(t+1)>fn)Clique(t+1,cn); }; Clique(0,0); return BX; 
}//5.子集和问题（是否有和为t的子集）的回溯算法
auto SetSum(const vector<int> &W, int M){int n=W.size(); int sum=accumulate(begin(W),end(W),0); vector<bool>X(n,false),BX; function<void<int,int,int>> SetSum=[&](int t,int s,int r){if(BX.size()>0) return ;if(s==M){BX=X; return; }if(t>=n) return; X[t]=1; if(s+W[t]<=M)SetSum(t+1,s+W[t],r-W[t]); X[t]=0; if(s+r-W[t]>=M)SetSum(t+1,s,r-W[t]); }; SetSum(0,0,sum); return BX; 
}//第5章·动态规划方法
//1.矩阵连乘最优次序的备忘录方法法（使用递归方法，只需获得最优值）
auto MatrixChain(int r[], int n){Matrix<int>c(n,n); function<int<int,int>>C=[&](int i,int j){if(j<=i) return 0; c(i,j)=(int)inf; for(int k=i;k<j;k++){auto t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1]; if(t<c(i,j)) c(i,j)=t; }return c(i,j); }; return C(0,n-1); 
}//2.矩阵连乘最优次序的动态规划算法（使用循环结构，只需获得最优值）
MatrixChain(int r[], int n){Matrix<int>c(n,n); for(int i=n-1;i>=0;i--){c(i,i)=0; for(int j=i+1;j<n;j++){c(i,j)=(int)inf; for(int k=i;k<j;k++){int t=c(i,k)+c(k+1,j)+r[i]*r[k+1]*r[j+1]; if(t<c(i,j)) c(i,j)=t; }}}return c(0,n-1); 
}//3.任意顶点间最短路径的动态规划算法（只需获得最优值）
auto Floyd(const Matrix<double> &G){auto A=G; int n=G.rows(); for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(A(i,k)+A(k,j)<A(i,j))A(i,j)=A(i,k)+A(k,j); return A; 
}//4.多段图的动态规划算法（只需获得最优值）
auto MultiGraph(const Matrix<double> &G){int n=G.rows(); vector<double>c(n,0); for(int i=n-1;i>=0;i--){int r=i+1; for(int k=r;k<n;k++)if(G(i,k)+c[k]<G(i,r)+c[r]) r=k; c[i]=G(i,r)+c[r]; }return c[0]; }//inf 无穷
//第5章·动态规划方法
//矩阵连乘·备忘录
auto MatrixChain(int r[],int n){function<int(int,int)> C=[&](int i,int j){if(j<=i) return 0;int u=(int)inf;for(int k=i;k<j;k++){int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];if(t<u) t=u;}return u;};return C(0,n-1);
}//矩阵连乘·动态规划
auto MatrixChain(int r[],int n){Matrix<int>C(n,n); for(int i=n-1;i>=0;i--){C(i,i)=0; for(int j=i+1;j<n;j++){C(i,j)=(int)inf; for(int k=i;k<j;k++){int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1]; if(t<C(i,j)) C(i,j)=t; }}}return C(0,n-1); 
}//Floyd算法·任意顶点最短路
auto Floyd(const Matrix<double>&G){int n=G.rows(); auto A=G; for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){auto t=A(i,k)+A(k,j); if(t<A(i,j)) A(i,j)=t; }return A; 
}//多段图   核心代码：C(j)=min{c(j,r)+C(r):j<r<n}
auto MultiGraph(const Matrix<double>&G){int n=G.rows(),t=n-1; vector<double>C(n);C[t]=0; for(int j=t-1;j>=0;j--){int r=j+1; for(int i=r;i<n;i++)if(G(j,i)+C[i]<G(j,r)+C[r]) r=i; C[j]=G(j,r)+C[r]; }return C; 
}//第4章·贪心算法
//装载问题 (在不超重的情况下尽可能地多装物品)
auto Load(vector<double>&W,double M){int n=W.size();sort(begin(W),end(W)); vector<bool>X(n,0); //解向量,初始化每个物品不装double rc=M; for(int i=0;i<n and M>=W[i];i++)X[i]=1,rc-=W[i]; return X; 
}//背包问题 (每个物品可以只装部分)
auto Knap(vector<double>&V,vetor<double>&W,double M){//效益数组,重量数组,背包容量int n=min(size(W),size(V)); Sort(V,W); //按单价升序排序vector<bool>X(n,0);//解向量,初始化全不选double rc=M; //背包剩余容量int t; for(t=0;t<n and W[t]<=rc; t++)X[t]=1,rc-=W[t]; if(t<n) X[t]=rc/W[t]; //还有物品就装部分return X; 
}//活动安排问题
auto Action(vector<double>&S,vector<double>&F){int n=min(size(S),size(F)); Sort(S,F); //按活动结束时间升序排序vector<bool>X(n,0); X[0]=1; for(int i=0,j=0;i<n;i++)if(S[i]>=F[j])X[i]=1,j=i; return X; 
}//Prim最小生成树
bool Prim(const Matrix<double>&G,int v,vector<int>&prev){int n=G.rows(); prev.assign(n,v); vector<bool>S(n,false); S[v]=true; for(int i=0;i<n-1;i++){double min=inf; for(int w=0;w<n;w++)if(!S[w] and G(prev[w],w)<min)min=G(prev[w],w),v=w; if(min==inf) return false; //图不连通S[v]=true; for(int w=0;w<n;w++)if(!S[w] and G(v,w)<G(prev[w],w))prev[w]=v; }return true; 
}//第3章·分治方法
//至少列出5种基于比较的排序算法，并说明每种算法的最好时间复杂性、最坏时间复杂性和平均时间复杂性。
//冒泡O(n^2),O(n^2),O(n^2) 插入O(n),O(n^2),O(n^2) 快排O(nlogn),O(n^2),O(nlogn) 归并O(nlogn),O(nlogn),O(nlogn) 堆O(nlogn),O(nlogn),O(nlogn)//折半搜索
template<class T,class T2>
int search(T X[],int n,const T2&v){int low=0,up=n;while(low<up){int m=(low+up)/2;if(v==X[m]) return m; else if(v<X[m]) up=m; else low=m+1; }return -1; 
}//归并排序
template<class T>void Merge(T X[],int low,int m,int up){int n=up-low; T W[n]; int i=low,j=m,k=0; while(i<m and j<up)if(X[i]<X[j])W[k++]=X[i++]; else if(X[j]<X[i])W[k++]=X[j++];else W[k++]=X[i++],W[k++]=X[j++]; copy(X+i,X+m,W+k); copy(X+j,X+up,W+k); copy(W,W+n,X+low); 
}void MergeSort(T X[],int low,int up){if(up-low<=1) return; int m=(low+up)/2; MergeSort(X,low,m); MergeSort(X,m,up); Merge(X,low,m,up); 
}//快排：
template<class T>
int Partition(T X[],int low,int up){int key=up-1; for(int i=low;i<up;i++)if(X[i]<X[key])swap(X[i],X[low++]); swap(X[low],X[key]);return low; 
}template<class T>
void QuickSort(T X[],int low,int up){if(up-low<=1) return; int m=Partition(X,low,up); QuickSort(X,low,m); QuickSort(X,m+1,up); 
}//线性时间选择算法
template<class T>
auto Select(T X[],int n,int k){int low=0,up=n; while(1){int m=partition(X,low,up); if(m==k) return X[m]; else if(m>k) up=m; else low=m+1; }
}//第2章·图的遍历
//二叉树的4种遍历方式
//前序遍历
template<class T>
struct BtNode{T data; BtNode *left=0,*right=0; 
}; 
template<class T>
void Visit(BtNode<T>* x){cout<<x->data<<' '; 
}
template<class T,class Func>
void PreOrder(BtNode<T>*x,Func Visit){if(x==0) return; Visit(x); PreOrder(x->left,Visit); PreOrder(x->right,Visit); 
}//中序遍历
template<class T>
struct BtNode{T data; BtNode *left=0,*right=0; 
}; 
template<class T>
void Visit(BtNode<T>* x){cout<<x->data<<' '; 
}
template<class T,class Func>
void PreOrder(BtNode<T>*x,Func Visit){if(x==0) return; PreOrder(x->left,Visit); Visit(x); PreOrder(x->right,Visit); 
}//后序遍历
template<class T>
struct BtNode{T data; BtNode *left=0,*right=0; 
}; 
template<class T>
void Visit(BtNode<T>* x){cout<<x->data<<' '; 
}
template<class T,class Func>
void PreOrder(BtNode<T>*x,Func Visit){if(x==0) return; PreOrder(x->left,Visit); PreOrder(x->right,Visit); Visit(x); 
}//层序遍历
template<class T,class Func>
void LevelOrder(BtNode<T>*x,Func Visit){queue<BtNode<T>*>q; if(x!=0) Visit(x),q.push(x); while(q.size()){x=q.front(),q.pop(); auto left=x->left,right=x->right; if(left!=0) Visit(left),q.push(left); if(right!=0) Visit(right),q.push(right); }
}//一般树的4中遍历方式
//前根
template<class T>
struct TreeNode{T data; TreeNode *first,*next; 
}; 
template<class T,class Func>
void PreOrder(TreeNode<T>*x,Func Visit){if(x==0) return; Visit(x); for(auto w=x->first;w!=0;w=w->next)PreOrder(w,Visit); 
}//后根
void PostOrder(TreeNode<T>*x,Func Visit){if(x==0) return; for(auto w=x->first;w!=0;w=w->next)PostOrder(w,Visit); Visit(x); 
}//中根
void InOrder(TreeNode<T>*x,Func Visit){if(x==0) return; auto w=x->first; InOrder(w,Visit); Visit(x); if(w==0) return; for(w=w->next;w!=0;w=w->next)InOrder(w,Visit); 
}//层序
void LevelOrder(TreeNode<T> *x, Func Visit){queue<TreeNode<T>*>q; if(x!=0) Visit(x),q.push(x); while(q.size()){x=q.front(),q.pop(); for(auto w=x->first;w!=0;w=w->next)Visit(w),q.push(w); }
}//连通图的宽度优先遍历
template<class Fun>
void BFS(Matrix<bool>&G,int v,vector<bool>&Visited,Fun Visit){int n=G.rows(); queue<int>q; Visited[v]=1,Visit(v),q.push(v); while(q.size()){auto u=q.front(),q.pop(); for(int w=0;w<n;w++)if(Visited[w]==0 and G(w,v)==1)Visited[w]=1,Visit(w),q.push(w); }
}//连通图的深度优先搜索
template<class Fun>
void DFS(Matrix<bool>&G,int v,vector<bool>&Visited,Fun Visit){int n=G.rows(); Visit(v),Visited[v]=1; for(auto w=0;w<n;w++)if(Visited[w]==0 and G(w,v)==1)DFS(G,w,Visited,Visit); 
}

以上为个人考前的复习时整理的代码，仅作为个人的学习记录。

25/5/9