网站建设项目甘特图好看的网页设计作品图片

当前位置： 首页 > news >正文

网站建设项目甘特图,好看的网页设计作品图片,php做网站用什么软件,网站备案号填写文章目录前言一、STL容器二、递归算法三、分治法四、蛮力法五、回溯法六、分支限界法七、贪心法八、动态规划前言 本篇共为8类算法(STL容器、递归算法、分治法、蛮力法、回溯法、分支限界法、贪心法、动态规划)#xff0c;则各取每类算法中的几例经典示例进行展示。 一、STL容… 文章目录前言一、STL容器二、递归算法三、分治法四、蛮力法五、回溯法六、分支限界法七、贪心法八、动态规划前言 本篇共为8类算法(STL容器、递归算法、分治法、蛮力法、回溯法、分支限界法、贪心法、动态规划)则各取每类算法中的几例经典示例进行展示。 一、STL容器 使用STL算法sort() 实现整型数组a的递增排序
#includeiostream #include algorithm using namespace std; int main()
{ int a[]{2,5,4,1,3};sort(a,a5);for (int i0;i5;i)printf(%d ,a[i]); //输出: 1 2 3 4 5printf(\n); }编写一个实验程序对于一个含n(n1)个元素的queue队列容器qu出队从队头到队尾的第k(1kn)个元素其他队列元素不变。
#includeiostream #includequeue using namespace std; char solve(queuechar qu,int k) {queuechar temp;char e;for(int i0;ik-1;i){temp.push(qu.front());qu.pop();}equ.front();qu.pop();while(!qu.empty()){temp.push(qu.front());qu.pop();}qutemp;return e; } int main() {queuechar qu;qu.push(a);qu.push(b);qu.push©;qu.push(d);int k3;char esolve(qu,k);cout出队元素是eendl;cout出队顺序是:;while(!qu.empty()){coutqu.front() ;qu.pop();}coutendl;return 0; }二、递归算法 递归实现简单选择排序
#includeiostream using namespace std; void SelectSort(int a[], int n, int i) { int j, k;if (in-1) return; //满足递归出口条件else{ki; //k记录a[i..n-1]中最小元素的下标for (ji1;jn;j) //在a[i..n-1]中找最小元素if (a[j]a[k])kj;if (k!i) //若最小元素不是a[i]swap(a[i],a[k]); //a[i]和a[k]交换SelectSort(a,n,i1);} } int main() {int a[10]{5,4,6,2,1,0,3,8,7,9};SelectSort(a,10,0);for(int i0;i10;i)couta[i] ;} 递归实现冒泡排序
#includeiostream using namespace std; void BubbleSort(int a[], int n,int i) { int j;bool exchange;if (in-1) return; //满足递归出口条件else{exchangefalse; //置exchange为falsefor(jn-1;ji;j–)if(a[j]a[j-1]) //当相邻元素反序时{swap(a[j],a[j-1]);exchangetrue; //发生交换置exchange为true}if(exchangefalse) //未发生交换时直接返回　return ;else //发生交换时继续递归调用BubbleSort(a,n,i1); } } int main() {int a[10]{5,4,6,2,1,0,3,8,7,9};BubbleSort(a,10,0);for(int i0;i10;i)couta[i] ;} 应用递归算法求解逆置单链表问题 【问题描述】对于不带头结点的单链表L设计一个递归算法逆置所有结点。编写完整的实验程序并采用相应数据进行测试。
#includeiostream #includelist #includemalloc.h using namespace std; typedef int ElemType; typedef struct Node { ElemType data;struct Node *next; } LinkNode; void CreateList(LinkNode *L,ElemType a[],int n) //由a[0..n-1]创建单链表L {LinkNode *p, *r;L(LinkNode *)malloc(sizeof(LinkNode));L-dataa[0];rL; //r指向当前尾结点for (int i1;in;i){p(LinkNode *)malloc(sizeof(LinkNode));p-dataa[i];r-nextp;rp;}r-nextNULL; //尾结点next域置为空 } void DispList(LinkNode *L) //输出单链表L {LinkNode *pL;while (p!NULL){coutp-data ;pp-next;}coutendl; } LinkNode *Reverse(LinkNode *L) //逆置不带头结点的单链表L { LinkNode *p;if (LNULL || L-nextNULL)return L;pReverse(L-next);L-next-nextL; //将L结点链接到L-next结点后面L-nextNULL; //将L结点作为整个逆置后的尾结点return p; } int main() {ElemType a[]{1,2,3,4,5,6};int nsizeof(a)/sizeof(a[0]);LinkNode *L;CreateList(L,a,n);cout实验结果:endl;cout 逆置前L: endl;DispList(L);cout 执行LReverse(L)endl;LReverse(L);cout 逆置后L: endl;DispList(L);return 0; }三、分治法 分治法进行快排
#includeiostream using namespace std; int Partition(int a[],int s,int t) //划分算法 { int is,jt;int tempa[s]; //用序列的第1个记录作为基准while(i!j){while(jia[j]temp)j–; //从右向左扫描找第1个关键字小于tmp的a[j]a[i]a[j]; //将a[j]前移到a[i]的位置while(ija[i]temp)i;//从左向右扫描找第1个关键字大于tmp的a[i]a[j]a[i]; //将a[i]后移到a[j]的位置}a[i]temp;return i; } void QuickSort(int a[],int s,int t) //对a[s..t]元素序列进行递增排序 { if (st) //序列内至少存在2个元素的情况{ int iPartition(a,s,t);QuickSort(a,s,i-1); //对左子序列递归排序QuickSort(a,i1,t); //对右子序列递归排序} } int main() {int a[10]{5,4,6,2,10,0,3,8,7,9};QuickSort(a,0,10);for(int i0;i10;i){couta[i] ;}coutendl;return 0; }分治法进行归并排序
#includeiostream #includealgorithm #includemalloc.h using namespace std; void Merge(int a[],int low,int mid,int high) {int *tmpa;int ilow,jmid1,k0;tmpa(int *)malloc((high-low1)*sizeof(int));while(imidjhigh)if(a[i]a[j]) //将第1子表中的元素放入tmpa中{tmpa[k]a[i]; i; k;}else //将第2子表中的元素放入tmpa中{tmpa[k]a[j];j;k;}while (imid) //将第1子表余下部分复制到tmpa{ tmpa[k]a[i]; i; k; }while (jhigh) //将第2子表余下部分复制到tmpa{ tmpa[k]a[j]; j; k; }for(k0,ilow;ihigh;k,i) //将tmpa复制回a中a[i]tmpa[k];free(tmpa); //释放tmpa所占内存空间 } //一趟二路归并排序 void MergePass(int a[],int length,int n) {int i;for(i0;i2*length-1n;ii2*length) //归并length长的两相邻子表Merge(a,i,ilength-1,i2*length-1);if(ilength-1n) //余下两个子表后者长度小于lengthMerge(a,i,ilength-1,n-1); //归并这两个子表 } void MergeSort(int a[],int n) //二路归并算法 { int length;for (length1;lengthn;length2*length)MergePass(a,length,n); } int main() {int a[]{2,5,1,7,10,6,9,4,3,8};MergeSort(a,10);for(int i0;i10;i){couta[i] ;}coutendl;return 0; }分治法进行折半查找
#includeiostream #includealgorithm using namespace std; int BinSearch(int a[],int low,int high,int k) //拆半查找算法 {int mid;if(lowhigh){mid(lowhigh)/2;if(a[mid]k)return mid;if(a[mid]k)return BinSearch(a,low,mid-1,k);elsereturn BinSearch(a,mid1,high,k);}return -1; } int main() {int i;int k2;int a[]{1,2,3,4,5,6,7,8,9,10};iBinSearch(a,0,9,k);if(i!-1){cout找到,位置是iendl;}else cout未找到endl;return 0; }应用递归和分治法求解众数问题 【问题描述】给定含有n个元素的多重集合S每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 例如S{122235}。 多重集S的众数是2其重数为3。 对于给定的由n 个自然数组成的多重集S编程计算S 的众数及其重数。
#include iostream #includealgorithm using namespace std; #define M 100 int a[M]; int num,val,n; //重数, 众数,个数 void find(int l,int r,int mid)//找中位数的最左最右边界位置 {l r mid;while(a[l]a[mid] l 0) –l;l; //还原while(a[r]a[mid] r n-1) r;r–; } void Fun(int low,int high) {if(low high) return; //左右边界交叉结束int mid (low high)/2; //中位数int i,j;find(i,j,mid);if(j-i1 num){ //更新num j-i1;val a[mid];}if(i-low num){//分治递归Fun(low,i-1);}if(high -j num){Fun(j1,high);} } int main() {int i;cout输入元素个数\n;cinn;cout输入元素\n;for(i0;in;i)cina[i];sort(a,an);for(i0;in;i)couta[i],;Fun(0,n-1);coutendl众数val 重数num;return 0; }四、蛮力法 蛮力法解决简单选择排序
#includeiostream using namespace std; void SelectSort(int a[],int n) //对a[0..n-1]元素进行递增简单选择排序 { int i,j,k;for (i0;in-1;i) //进行n-1趟排序{ ki; //用k记录每趟无序区中最小元素的位置for (ji1;jn;j) //在a[i1..n-1]中穷举找最小元素a[k]if (a[j]a[k]) kj; if (k!i) //若a[k]不是最小元素,将a[k]与a[i]交换swap(a[i],a[k]);} } int main() {int a[]{5,9,4,2,1};SelectSort(a,5);for(int i0;i5;i){couta[i] ;} }蛮力法解决冒泡排序
#includeiostream using namespace std; void BubbleSort(int a[],int n) //对a[0..n-1]按递增有序进行冒泡排序 { int i,j; int tmp;bool exchange;for (i0;in-1;i) //进行n-1趟排序{ exchangefalse; //本趟排序前置exchange为falsefor (jn-1;ji;j–) //无序区元素比较,找出最小元素if (a[j]a[j-1]) //当相邻元素反序时{ swap(a[j],a[j-1]); //a[j]与a[j-1]进行交换exchangetrue; //发生交换置exchange为true}if (exchangefalse) //本趟未发生交换时结束算法return;} } int main() {int a[]{5,9,4,2,1};BubbleSort(a,5);for(int i0;i5;i){couta[i] ;} }应用蛮力法求解钱币兑换问题 【问题描述】某个国家仅有1分、2分和5分硬币将钱n(n5)兑换成硬币有很多种兑法。编写一个实验程序计算出10分钱有多少种兑法并列出每种兑换方式。
#includeiostream using namespace std; int main()
{int n10;int x,y,z;int num0;for(z0;z2;z){for(y0;y5;y){for(x0;x10;x){if(z*5y*2x*110){cout兑换方式num; if(z!0) cout 5分的硬币有z个; if(y!0) cout 2分的硬币有y个; if(x!0) cout 1分的硬币有x个; coutendl;}}}}cout共有num种兑换方式endl; return 0; }五、回溯法 回溯法求解求解0/1背包问题
#include iostream using namespace std; #define MAXN 20//问题表示 int n4; //4种物品 int W6; //限制重量为6 int w[]{0,5,3,2,1}; //存放4个物品重量,不用下标0元素 int v[]{0,4,4,3,1}; //存放4个物品价值,不用下标0元素 //求解结果表示 int x[MAXN]; //存放最终解 int maxv; //存放最优解的总价值void dfs(int i,int tw,int tv,int rw,int op[]) { if (in) //找到一个叶子结点{ if (twW tvmaxv) //找到一个满足条件的更优解,保存{ maxvtv;for (int j1;jn;j)x[j]op[j];}}else //尚未找完所有物品{if ( tww[i]W ) //左孩子结点剪枝{ op[i]1; //选取第i个物品dfs(i1,tww[i],tvv[i],rw-w[i],op);}if ( twrw-w[i]W ) //右孩子结点剪枝{ op[i]0; //不选取第i个物品,回溯dfs(i1,tw,tv,rw-w[i],op);}} }int main() {int op[MAXN];dfs(1,0,0,11,op);cout最优值是maxvendl;for(int j1;jn;j)coutx[j] ; }应用回溯法求解组合问题 【问题描述】编写一个实验程序采用回溯法输出自然数1~n中任取r个数的所有组合。
#include iostream #include vector using namespace std; int n,r; void disp(vectorint path) {for(int j0;jpath.size();j)coutpath[j] ;coutendl; } void dfs(vectorint path,int i,int num) {if(numr)disp(path);for(int ji;jn;j){path.push_back(j);dfs(path,j1,num1);path.pop_back();} } int main() {cinnr;vectorint path;dfs(path,1,0);return 0; }六、分支限界法 应用分枝限界法求解n皇后问题 【问题描述】在n×n的方格棋盘上放置n个皇后要求每个皇后不同行、不同列、不同左右对角线。如图1所示是6皇后问题的一个解。要求采用队列式分枝限界法求解4皇后问题的一个解并分析对应程序运行中创建的队列结点的个数。 #include iostream #include vector #include queue using namespace std; int n4; int Count1; struct NodeType {int no;int row;vectorint cols; }; void dispnode(NodeType e) {if(e.row!-1)cout编号e.no对应位置是e.row,e.cols[e.row]endl;elsecout编号e.no对应位置是e.row,*endl; } bool Valid(vector int cols,int i,int j) {int k0;while(ki){if((cols[k]j)||(abs(cols[k]-j)abs(k-i))) return false;k;}return true; } void solve() {int i,j;NodeType e,el;queueNodeType qu;e.noCount;e.row-1;qu.push(e);cout进队:;dispnode(e);while(!qu.empty()){equ.front();qu.pop();cout出队;dispnode(e);if(e.rown-1){cout产生一个解:;for(int i0;in; i){couti1,e.cols[i]1 ;}coutendl;return ;}else{for(j0;jn;j){ie.row1;if(Valid(e.cols,i,j)){el.noCount;el.rowi;el.colse.cols;el.cols.push_back(j);qu.push(el);cout进队子结点:;dispnode(el);}}}} } int main() {solve();return 0; }七、贪心法 贪心算法求解活动安排问题
#include iostream #includestring.h #includealgorithm using namespace std; #define MAX 51 //问题表示 struct Action //活动的类型声明 { int b; //活动起始时间int e; //活动结束时间bool operator(const Action s) const //重载关系函数{return es.e; //用于按活动结束时间递增排序} }; int n11; Action A[]{{0},{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,15}}; //下标0不用 //求解结果表示 bool flag[MAX]; //标记选择的活动 int Count0; void solve() //求解最大兼容活动子集 { memset(flag,0,sizeof(flag)); //初始化为falsesort(A1,An1); //A[1..n]按活动结束时间递增排序int preend0; //前一个兼容活动的结束时间for (int i1;in;i) //扫描所有活动{ if (A[i].bpreend) //找到一个兼容活动{ flag[i]true; //选择A[i]活动preendA[i].e; //更新preend值}} } int main() {solve();cout求解结果,选取的活动:endl;for (int i1;in;i) //求v/wif(flag[i]){coutA[i].b,A[i].eendl;Count;}cout共有Count个活动;return 0; }应用贪心法求解删数问题 【问题描述】编写一个实验程序实现求解删数问题。给定共有n位的正整数d去掉其中任意,kn个数字后剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数d和正整数k找出剩下数字组成的新数最小的删数方案。
#include iostream #include string using namespace std; int main() {string N;int k,i;cin N k;while (k–){int lenN.length();for (i0;ilen-1;i)if (N[i]N[i1]){N.erase(N.begin()i);break;}if (ilen-1)N.erase(N.end()-1); //删除最后数字}while(N[0]0N.length()1)N.erase(N.begin());cout N endl;return 0; }八、动态规划 动态规划求解最大连续子序列和问题
#includeiostream using namespace std; int a[]{0,-2,11,-4,13,-5,-2}; int n6; int dp[20]; void maxsubsum() {dp[0]0;for(int j1;jn;j)dp[j]max(dp[j-1]a[j],a[j]); } void dispmaxsum() {int maxj1;for(int j1;jn;j)if(dp[j]dp[maxj]) maxjj;int k;for(kmaxj;k1;k–)if(dp[k]0) break;coutdp[maxj]endl;for(int ik1;imaxj;i)couta[i] ; } int main() {maxsubsum();dispmaxsum();return 0; }应用动态规划算法求解矩阵最小路径和问题 【问题描述】给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。编写一个实验程序求所有路径和中的最小路径和。例如,以下矩阵中的路径1→3→1→0→6→1→0是所有路径中路径和最小的返回结果是12 1 3 5 98 1 3 45 0 6 18 8 4 0#includeiostream #includevector #includestdio.h using namespace std; #define MAXM 100 #define MAXN 100 //问题表示 int a[MAXM][MAXN]{{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}}; int m4,n4; //求解结果表示 int ans; //最小路径长度 int dp[MAXM][MAXN]; int pre[MAXM][MAXN]; void Minpath() //求最小和路径ans { int i,j;dp[0][0]a[0][0];for(i1;im;i) //计算第一列的值{ dp[i][0]dp[i-1][0]a[i][0];pre[i][0]0; //垂直路径}for(j1;jn;j) //计算第一行的值{ dp[0][j]dp[0][j-1]a[0][j];pre[0][j]1; //水平路径}for(i1;im;i) //计算其他dp值for(j1;jn;j){ if (dp[i][j-1]dp[i-1][j]){ dp[i][j]dp[i][j-1]a[i][j];pre[i][j]1;}else{ dp[i][j]dp[i-1][j]a[i][j];pre[i][j]0;}}ansdp[m-1][n-1]; } void Disppath() //输出最小和路径 { int im-1,jn-1;vectorint path; //存放反向最小路径vectorint::reverse_iterator it;while (true){ path.push_back(a[i][j]);if (i0 j0) break;if (pre[i][j]1) j–; //同行else i–; //同列}printf( 最短路径: );for (itpath.rbegin();it!path.rend();it)printf(%d ,*it); //反向输出构成正向路径printf(\n 最短路径和:%d\n,ans); } int main() {Minpath(); //求最小路径和printf(求解结果\n);Disppath(); //输出求最小路径与最小路径和return 0; }