用棧模擬遞歸+集合劃分問題+眾數(shù)問題+數(shù)塔問題

一、2-24試用棧來模擬遞歸，消去算法QuickSort中的尾遞歸，并比較消去尾遞歸前后算法的效率。1、解題說明快速排序的遞歸算法思路是，將整個數(shù)組以軸值為界限劃分為兩部分，然后分別最兩部分進行快速排序。而用棧來模擬遞歸，其實就是用棧保存每一個待排序子串的首尾元素下表，下一次while循環(huán)的時候來，對這段子序列進行partition操作?？焖倥判虻乃惴ㄔ谏蠈W期的數(shù)據(jù)結(jié)構(gòu)中已經(jīng)學習過，只需對其中的qsort()函數(shù)中的遞歸部分進行修改即可。調(diào)用庫函數(shù)計算程序運行時間，并輸出，便于對比兩種算法的效率。2、代碼#include<iostream>#include<stack>#include<ctime>#include<cstdlib>#include<windows.h>usingnamespacestd;DWORDtake;int{findpivot(intA[],inti,intj)//找到軸值{srand(unsigned(time(0)));//取隨機數(shù)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〈〈"請輸入待排序的數(shù)據(jù)個數(shù)n:"〈〈endl;cin>>n;cout〈〈"輸入數(shù)據(jù)："〈〈endl;for(inti=0;i〈n;i++)cin>>task[i];qsort(task,0,n-1);//qsort2(task,0,n-1);cout〈〈"排序結(jié)果為："〈〈endl;for(intj=0;j〈n;j++)cout〈〈task[j]〈〈endl;cout〈〈"運行時間為："〈〈take〈〈endl;return0;3、運行截圖非遞歸算法：I?F:\我的匚++程序\算法設計與分析\：請輸人待排序的數(shù)據(jù)個數(shù)屮爲入數(shù)據(jù)：32451排序結(jié)果為:12345_匡行時間為=19514882Press耳ny tocontinue遞歸算法：可以看出，非遞歸算法的運算速度更快些，若數(shù)據(jù)個數(shù)增大，差距會更加明顯。4、遞歸與非遞歸效率對比理論來說，由于遞歸要層層調(diào)用，容易棧溢出，當算法比較復雜的時候，效率也非常低，運行起來等待結(jié)果時間很長。而用非遞歸，減少了函數(shù)調(diào)用開銷，可以解決溢出問題和效率低的問題。因為遞歸算法使用的棧由程序自動產(chǎn)生，棧中包含函數(shù)調(diào)用時的參數(shù)和函數(shù)中的局部變量。如果局部變量很多或者函數(shù)內(nèi)部又調(diào)用了其他函數(shù)，則棧會很大。每次遞歸調(diào)用都要操作很大的棧，效率自然會下降。而對于非遞歸算法，每次循環(huán)使用自己預先創(chuàng)建的棧，因此不管程序復雜度如何，都不會影響程序效率。二、2-2眾數(shù)問題問題描述：給定含有n個元素的多重集合S,每個元素在S中出現(xiàn)的次數(shù)稱為該元素的重數(shù)。例如，S={1,2,2,2,3,5}。多重集S的眾數(shù)是2,其重數(shù)為3。算法設計:對于給定的由n個自然數(shù)組成的多重集S,計算S的眾數(shù)及其重數(shù)。數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為input.txt的文本文件提供。文件的第1行為多重集S中元素個數(shù)n；在接下來的n行中，每行有一個自然數(shù)。結(jié)果輸出：將計算結(jié)果輸出到文件output.txt。輸出文件有2行，第1行是眾數(shù),第2行是重數(shù)。輸入文件示例 輸出文件示例input.txt output.txt6 232351、解題說明首先將文件中數(shù)據(jù)讀入到一個數(shù)組中，要想選擇眾數(shù)，最基本的方法就是寫一個雙重for循環(huán)，每一個元素跟數(shù)組中其他元素對比一遍，這樣時間復雜度是n的平方。改進方案是先調(diào)用庫函數(shù)sort，對數(shù)組進行排序，則只用一個for循環(huán)便可得到眾數(shù)和重數(shù)。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++){//從文件讀入元素個數(shù)//從文件讀入元素//對元素數(shù)組進行從小到大排序//循環(huán)記錄眾數(shù)下標和其重數(shù)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金數(shù)問題ipp翁金數(shù)問題討年眾數(shù)問題皿b金數(shù)問題Qg三、2-10集合劃分問題對于給定正整數(shù)n,計算出n個元素的集合{1,2,…，n}可以劃分為多少個不同的非空子集。數(shù)據(jù)輸入：由文件input.txt提供輸入數(shù)據(jù)。文件的第1行是元素個數(shù)n。結(jié)果輸出：將計算出的不同的非空子集數(shù)輸出到文件output.txt。輸入文件示例 輸出文件示例input.txt output.txt5521、解題說明將n個元素劃分為m個集合的遞歸思路如下：把n個元素編號，對于第n個元素，有兩種情況，第一種是自己單獨是一個集合，等價于把前n-1個元素分成m-1份；第二種是第n個元素和別的元素一起組成了一個集合，等價于把前n-1個元素分成m份，然后把n號元素放入這m個集合中的一個(即有m中放法)。所以總數(shù)是：F(n,m)=F(n-1，m-1)+F(n-1,m)*m因此要求所有的集合，只需再用一個for循環(huán)，將劃分大小從1循環(huán)到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四、數(shù)塔問題

輸入如下：第一行的數(shù)字代表數(shù)塔的層數(shù)，接下來的數(shù)字為數(shù)塔中各層的結(jié)點中保存的數(shù)字L■8102744452651、解題說明這個題是典型的動態(tài)規(guī)劃問題，考慮的時候自頂向下的分析，自底向上的計算。從頂點出發(fā)，向左走還是向右走取決于走哪邊最終總路徑和最大，只有兩條路徑的總長度最大值求出了才能做決策，一層一層推下去，直到倒數(shù)第二層，它選擇左還是右，只取決于哪個數(shù)更大些。所以實際求解的時候，可以從底層開始，層層往上推算，最后得到最大值。2、代碼#include<iostream>#include<fstream>usingnamespacestd;//求最大值函數(shù)intmax(inta,intb){//求最大值函數(shù)returna>b?a:b;}intmain(){inti,j,n,**a;ifstreamin("input.txt");ofstreamout("output.txt");in>>n;

a=newint*[n+1]; //創(chuàng)建二維數(shù)組存放數(shù)塔for(i=0;i<n+1;i++)a[i]=newint[n+1];for(i=1;i<n+1;i++) //從文件中讀取數(shù)塔中的數(shù)字，存放到二維數(shù)組中for(j=1;j<=i;j++)in>>a[i][j];for(i=n-1;i>=1;i--) //從倒數(shù)第二層開始，從下往上求最大值路徑for(j=1;j<=i;j++)a[i][j]