用栈模拟递归+集合划分问题+众数问题+数塔问题

一、2-24试用栈来模拟递归，消去算法QuickSort中的尾递归，并比较消去尾递归前后算法的效率。1、解题说明快速排序的递归算法思路是，将整个数组以轴值为界限划分为两部分，然后分别最两部分进行快速排序。而用栈来模拟递归，其实就是用栈保存每一个待排序子串的首尾元素下表，下一次while循环的时候来，对这段子序列进行partition操作。快速排序的算法在上学期的数据结构中已经学习过，只需对其中的qsort()函数中的递归部分进行修改即可。调用库函数计算程序运行时间，并输出，便于对比两种算法的效率。2、代码#include<iostream>#include<stack>#include<ctime>#include<cstdlib>#include<windows.h>usingnamespacestd;DWORDtake;int{findpivot(intA[],inti,intj)//找到轴值{srand(unsigned(time(0)));//取随机数intpivot1=rand()%(j-i+1)+i;//取轴值}returnpivot1;voidswap(intA[],inti,intj) //交换{inttemp=A[i];A[i]=A[j];A[j]=temp;}intpartition(intA[],intl,intr,int&pivot)//分组{do{while(A[++l]<pivot); //将l右移while((r!=0)&&(A[--r]>pivot));//将r左移swap(A,l,r); //交换//多交换1//多交换1次，交换回来}//递归算法voidqsort(intA[],inti,intj) //快速排序{if(j<=i)return; //只剩一个元素的时候停止分组intpivotindex=findpivot(A,i,j); //获取轴值swap(A,pivotindex,j); //将轴值放在最后intk=partition(A,i-1,j,A[j]); //右半部分的第一个值swap(A,k,j); //将轴值换回来qsort(A,i,k-1); //递归qsort(A,k+1,j);}//非递归算法voidqsort2(intA[],inti,intj){stack<int>st;if(j<=i)return; //只剩一个元素的时候停止分组intpivotindex二findpivot(A,i,j);//获取轴值swap(A,pivotindex,j);//将轴值放在最后intk=partition(A,iT,j,A[j]);//右半部分的第一个值swap(A,k,j); //将轴值换回来if(i<k-1) //用栈保存每个待排序子串的首尾元素下标{st.push(i);st.push(k-1);}if(k+1<j){st.push(k+1);st.push(j);}while(!st.empty()){intq=st.top();st.pop();intp=st.top();st.pop();intpivotindex=findpivot(A,p,q);swap(A,pivotindex,q);intk=partition(A,p-1,q,A[q]);swap(A,k,q);if(p<k-1){st.push(p);st.push(k-1);}if(k+1<q){st.push(k+1);st.push(q);}}}intmain(){take=GetTickCount();intn;inttask[100];cout〈〈"请输入待排序的数据个数n:"〈〈endl;cin>>n;cout〈〈"输入数据："〈〈endl;for(inti=0;i〈n;i++)cin>>task[i];qsort(task,0,n-1);//qsort2(task,0,n-1);cout〈〈"排序结果为："〈〈endl;for(intj=0;j〈n;j++)cout〈〈task[j]〈〈endl;cout〈〈"运行时间为："〈〈take〈〈endl;return0;3、运行截图非递归算法：I・F:\我的匚++程序\算法设计与分析\：请输人待排序的数据个数屮爲入数据：32451排序结果为:12345_匡行时间为=19514882Press耳ny tocontinue递归算法：可以看出，非递归算法的运算速度更快些，若数据个数增大，差距会更加明显。4、递归与非递归效率对比理论来说，由于递归要层层调用，容易栈溢出，当算法比较复杂的时候，效率也非常低，运行起来等待结果时间很长。而用非递归，减少了函数调用开销，可以解决溢出问题和效率低的问题。因为递归算法使用的栈由程序自动产生，栈中包含函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数，则栈会很大。每次递归调用都要操作很大的栈，效率自然会下降。而对于非递归算法，每次循环使用自己预先创建的栈，因此不管程序复杂度如何，都不会影响程序效率。二、2-2众数问题问题描述：给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。例如，S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。算法设计:对于给定的由n个自然数组成的多重集S,计算S的众数及其重数。数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行为多重集S中元素个数n；在接下来的n行中，每行有一个自然数。结果输出：将计算结果输出到文件output.txt。输出文件有2行，第1行是众数,第2行是重数。输入文件示例 输出文件示例input.txt output.txt6 232351、解题说明首先将文件中数据读入到一个数组中，要想选择众数，最基本的方法就是写一个双重for循环，每一个元素跟数组中其他元素对比一遍，这样时间复杂度是n的平方。改进方案是先调用库函数sort，对数组进行排序，则只用一个for循环便可得到众数和重数。2、代码#include<iostream>#include<algorithm>#include<fstream>usingnamespacestd;intmain(){intn,amount=1,maxamount=1,maxindex;ifstreamin("input.txt");ofstreamout("output.txt");in>>n;int*a=newint[n];for(inti=0;i<n;i++)ifstreamin("input.txt");ofstreamout("output.txt");in>>n;int*a=newint[n];for(inti=0;i<n;i++){in>>a[i];}sort(a,a+n);for(intj=1;j<n;j++){//从文件读入元素个数//从文件读入元素//对元素数组进行从小到大排序//循环记录众数下标和其重数if(a[j]==a[j-1])amount++;elseamount=1;if(amount>maxamount){maxamount=amount;maxindex=j;}//将输出写入文件中}out<<a[maxindex]<<endl<<maxamount<<endl;return0;//将输出写入文件中}3、程序运行截图input.txt:input.txt-本文聞窗日梧式output.txt:output.txt-记事本文件旧翱冏梧式必输入输出文件都在当前目录下:D曰buginput.txt一ou1tput.txteg金数问题ipp翁金数问题討年众数问题皿b金数问题Qg三、2-10集合划分问题对于给定正整数n,计算出n个元素的集合{1,2,…，n}可以划分为多少个不同的非空子集。数据输入：由文件input.txt提供输入数据。文件的第1行是元素个数n。结果输出：将计算出的不同的非空子集数输出到文件output.txt。输入文件示例 输出文件示例input.txt output.txt5521、解题说明将n个元素划分为m个集合的递归思路如下：把n个元素编号，对于第n个元素，有两种情况，第一种是自己单独是一个集合，等价于把前n-1个元素分成m-1份；第二种是第n个元素和别的元素一起组成了一个集合，等价于把前n-1个元素分成m份，然后把n号元素放入这m个集合中的一个(即有m中放法)。所以总数是：F(n,m)=F(n-1，m-1)+F(n-1,m)*m因此要求所有的集合，只需再用一个for循环，将划分大小从1循环到n即可。2、代码#include<iostream>#include<fstream>usingnamespacestd;intpartition(intn,intm){if(m==1||m==n)return1;elsereturnpartition(n-1,m-1)+partition(n-1,m)*m;}intmain(){intn,sum=0;ifstreamin("input.txt");ofstreamout("output.txt");in>>n;for(inti=1;i<=n;i++){sum+=partition(n,i);}out<<sum<<endl;return0;}3、运行截图input.txtoutput.txtoutput.txt-1BW本文件㈢輛E）格式莎输入输出文件都存储在当前目录下:Debug,,input.txt,,cutput.txteg集台分问题叩p甸宾餓11分问题•击p□集台划分问题.n比□集台划分问题Qpt□集台划分问题.pig四、数塔问题

输入如下：第一行的数字代表数塔的层数，接下来的数字为数塔中各层的结点中保存的数字L■8102744452651、解题说明这个题是典型的动态规划问题，考虑的时候自顶向下的分析，自底向上的计算。从顶点出发，向左走还是向右走取决于走哪边最终总路径和最大，只有两条路径的总长度最大值求出了才能做决策，一层一层推下去，直到倒数第二层，它选择左还是右，只取决于哪个数更大些。所以实际求解的时候，可以从底层开始，层层往上推算，最后得到最大值。2、代码#include<iostream>#include<fstream>usingnamespacestd;//求最大值函数intmax(inta,intb){//求最大值函数returna>b?a:b;}intmain(){inti,j,n,**a;ifstreamin("input.txt");ofstreamout("output.txt");in>>n;

a=newint*[n+1]; //创建二维数组存放数塔for(i=0;i<n+1;i++)a[i]=newint[n+1];for(i=1;i<n+1;i++) //从文件中读取数塔中的数字，存放到二维数组中for(j=1;j<=i;j++)in>>a[i][j];for(i=n-1;i>=1;i--) //从倒数第二层开始，从下往上求最大值路径for(j=1;j<=i;j++)a[i][j]