算法复习.docx
- 文档编号:7302151
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:98
- 大小:35.07KB
算法复习.docx
《算法复习.docx》由会员分享,可在线阅读,更多相关《算法复习.docx(98页珍藏版)》请在冰点文库上搜索。
算法复习
算法目录
1.进制枚举类完整版
1-1.n位m进制树扩展
1-2.n位m进制扩展
2.矩阵vector类
3.矩阵指针类
3-1.三维矩阵指针类
4.并查集
5.堆排序
6.选择排序改写
7.快排
8.合并排序
9.冒泡排序
10.农夫过河
10-1.农夫扩展树
11.17分钟过河
12.发牌器
13.火车进站
14.小母牛问题
15.幻方
16.三维幻方
17.整数拆分
18.摸底考试
19.链栈
20.队列
21-1.背包-枚举及贪心
21-2.背包-动态规划
21-3.背包-分支
22.矩阵连乘
23.王后车象
23.汉诺塔
1.进制枚举类完整版
#include
#include
usingnamespacestd;
ofstreamcout("out.txt");
classEnumation//枚举n位m进制
{
protected:
vector
intM,N;
voidprint()
{
for(inti=0;i cout< cout< } virtualboolvalid(intn) {returntrue;} public: Enumation(intn=0,intm=0) : N(n),M(m),A(n){} voidGenerate(intk)//k=0 { if(k { for(A[k]=0;A[k] if(valid(k)) Generate(k+1); } elseprint(); } }; classMultiPerm: publicEnumation//n位n进制 { public: MultiPerm(intn) : Enumation(n,n){} }; classPerm: publicMultiPerm//n位n进制不可重复全排列 { protected: virtualboolvalid(intk) { boolb=true; for(inti=0;b&&i b=A[i]! =A[k]; returnb; } public: Perm(intn): MultiPerm(n){} }; classNQueens: publicPerm//n皇后问题 { protected: virtualboolvalid(intk) { boolb=true; for(inti=0;b&&i b=A[i]! =A[k]&&abs(A[k]-A[i])! =(k-i); returnb; } public: NQueens(intn): Perm(n){} }; intmain() { NQueens(8).Generate(0); return0; } 1-1.n位m进制树扩展 #include #include #include #include usingnamespacestd; structNode { intkey,level,order; Node*parent; vector Node(intk=-1,intl=-1,intord=-1,Node*p=0) : key(k),level(l),order(ord),parent(p){} }; classTree { private: intN,M,cnt; Node*root; voidGen(Node*r,intk) { if(k { for(inti=0;i { Node*p=newNode(i,k,cnt++,r); r->children.push_back(p); Gen(p,k+1); } } } voidNonRecursionGen(Node*root) { Node*r=root; intk=0; while(k>=0) { intm=r->children.size(); if(m==M||k==N) { r=r->parent; k--; } else { Node*p=newNode(m,k,cnt++,r); r->children.push_back(p); r=p; k++; } } } voidGen_BFS(Node*root) { queue q.push(root); while(! q.empty()) { Node*p=q.front(); q.pop(); if(p->level { for(inti=0;i { Node*s=newNode(i,p->level+1,cnt++,p); p->children.push_back(s); q.push(s); } } elsebreak; } } voidprint(Node*p) { if(! p) return; stack while(p->parent) { s.push(p); p=p->parent; } while(! s.empty()) { cout< s.pop(); } cout< } voidBFS_Print() { queue q.push(root); while(! q.empty()) { Node*p=q.front(); q.pop(); intm=p->children.size(); if(m==0) print(p); else { for(inti=0;i q.push(p->children[i]); } } } voidDFS_Print() { stack s.push(root); while(! s.empty()) { Node*p=s.top(); s.pop(); intm=p->children.size(); if(! m) print(p); else for(inti=0;i s.push(p->children[i]); } } void_Print(Node*R) { if(R->level==N-1) print(R); else for(inti=0;i _Print(R->children[i]); } public: Tree(intn=0,intm=0) : N(n),M(m) { root=newNode(-1,-1,-1,0); cnt=1; } ~Tree() { } voidGen() { NonRecursionGen(root); BFS(); cout< DFS(); cout< BFS_Print(); cout< DFS_Print(); cout< _Print(root); cout< } voidBFS() { queue q.push(root); while(! q.empty()) { Node*p=q.front(); q.pop(); cout< //if(p->children.size()! =M) //cout<<"ERROR"< intm=p->children.size(); for(inti=0;i q.push(p->children[i]); } } voidDFS() { stack s.push(root); while(! s.empty()) { Node*p=s.top(); s.pop(); cout< intm=p->children.size(); //for(inti=0;i //s.push(p->children[i]); for(inti=m-1;i>=0;i--) s.push(p->children[i]); } } }; voidprint(intA[],intn) {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 复习