窮舉算法思想：

一句話：就是從所有可能的情況，搜索出正確的答案。 步驟： 1.對于一種可能的情況，計算其結果。 2.判斷結果是否滿足，YES計算下一個，no繼續步驟1，然后判斷下個可能的情況。 實例： 孫子算經--雞兔同籠：頭35，腳94，幾雞幾兔？
#include <iostream> //頭文件 using namespace std; int qiongju(int head, int foot , int *chicken,int *rabbit) //窮舉算法 { int re,i,j;re=0;for(i=0;i<=head;i++) //循環 {j=head-i;if(i*2+j*4==foot) //判斷，找到答案{re=1;*chicken=i;*rabbit=j;} } return re; } int main() //主函數 {int chicken,rabbit,head,foot;int re;cout<<"雞兔同籠問題："<<endl;cout<<"輸入頭數：";cin >>head;cout<<"輸入腳數：";cin >>foot;re =qiongju(head,foot,&chicken,&rabbit); //& 跟 qiongju（）里面的 * 是不是表示 引用？？if(re==1){cout<<"雞有："<<chicken<<"只, 兔有"<<rabbit<<"只。" <<endl;}else{cout<<"無法求解！"<<endl;} }

?

遞推思想： 1.根據已知的結果和關系，求解中間的結果。 2.判斷是否達到要求，如果沒有達到，則繼續根據已知的結果和關系求解中間結果。如果有的話，則表示尋找到一個正確的結果。 實例：斐波那契數列———兔子產子
#include <iostream> using namespace std; int fibonacci(int n) {if(n==1 || n==2){return 1;}else{return fibonacci(n-1)+fibonacci(n-2);//遞歸調用} } int main() {int n,num;cout<<"斐波那契數列——兔子產子："<<endl;cout<<"請輸入時間：";cin >> n;num=fibonacci(n);cout<<"經過"<<n<<"年，可以產子"<<num<<"對"<<endl; }

?

遞歸思想： 遞歸算法，就是在程序中不斷反復調用他自身的函數調用方式，這種函數也稱為遞歸函數。 函數的遞歸調用用分兩種情況：直接遞歸和間接遞歸。 直接遞歸：即在函數中調用函數本身。 間接遞歸：即間接地調用一個函數，如func_a調用了func_b，func_b又調用了func_a；間接遞歸用的不多。 優點:代碼間接清晰，可讀性更好。用遞歸比循環表死簡潔精煉。特別人工智能，八皇后問題，漢諾塔等適合用遞歸 缺點:沒有明顯的減少代碼規模和節省內存空間。 遞歸比非遞歸運行速度要慢一些。附加函數增加了時間的開銷（要執行一系列的壓棧出棧）。二者遞歸層次太深還可能導致堆棧溢出。 實例：經典的階乘
#include <iostream> using namespace std; long fact(int n); //函數的聲明 int main() {int i;cout<<"請輸入要求階乘的一個整數：";cin >>i;cout<<i<<"的階乘結果為"<<fact(i)<<endl; } long fact(int n) {if(n<=1)return 1;elsereturn n*fact(n-1); } 分治算法思想： 基本思路：將一個計算復雜的問題分為規模較小，計算簡單的小問題求解，然后綜合各個小問題，得到最終問題的答案。 基本過程： 1.對于一個規模為N的問題若該問題可以容易的解決，那就直接解決。否則執行下面的步驟。 2.將該問題分解為M個規模較小的子問題，這些子問題五項多里，并且與原問題形式相同。 3.遞歸的解子問題。 4.然后，將各子問題的解合并得到原問題的解。 例子: 問題：一個袋子30個硬幣，一個假的，假的較輕。如何分辨假幣？ 步驟： 1.首先為每個幣編號，分成兩份，放在天平上。 2.因為假幣在輕的一方，繼續將輕的重復上面的做法。 3.直到剩下2個，直接用天平找出。
#include <iostream> using namespace std; #define MAXNUM 4 int FalseCoin(int coin[],int low,int high) {int i,sum1,sum2,sum3;int re;sum1=sum2=sum3=0;if(low+1==high)//最后一堆是兩個的時候{if(coin[low]<coin[high]){re=low+1;return re; }else{re=high+1;return re;} }if((high-low+1)%2==0)//n為偶數{for(i=low;i<=low+(high-low)/2;i++){sum1+=coin[i];//前半段和 }for(i=low+(high-low)/2+1;i<=high;i++){sum2+=coin[i];//后半段和 }if(sum1>sum2){re=FalseCoin(coin,low+(high-low)/2+1,high);return re;}else if(sum1<sum2){re=FalseCoin(coin,low,low+(high-low)/2); return re;}else{} }else //n為奇數{for(i=low;i<=low+(high-low)/2-1;i++){sum1+=coin[i];//前半段和}for(i=low+(high-low)/2+1;i<=high;i++){sum2+=coin[i];//后半段和 }sum3=coin[low+(high-low)/2];if(sum1>sum2){re=FalseCoin(coin,low+(high-low)/2+1,high);return re;}else if(sum1<sum2){re=FalseCoin(coin,low,low+(high-low)/2-1); return re;}else{}if(sum1+sum3==sum2+sum3){re=low+(high-low)/2+1;return re;}} } int main() {int coin[MAXNUM];int i,n;int place;cout<<"分治法求假幣問題！"<<endl;cout<<"請輸入幣的個數:";cin >>n;cout<<"請輸入幣真假的重量:";for(i=0;i<n;i++){cin >> coin[i];//scanf("%d",&coin[i]);}place =FalseCoin(coin,0,n-1);cout<<"位子實在上述的第"<<place<<"個是假的"<<endl; } 概率算法思想： 1.將問題轉化為相應的幾何圖形S，S的面積是容易計算的。問題往往是對應的集合圖形的S1的面積， 2.然后向幾何隨機撒點。 3.統計S S1的點數，根據關系得出結果。 4.判斷是否達到精度，否執行2步驟，是 結束 4種形式：數值概率算法，蒙特卡羅算法 ，拉斯維加斯算法，舍伍德算法。 蒙特卡羅概率算法 計算PI:
#include <iostream> #include <time.h> using namespace std; double MontePI(int n) {double PI;double x,y;int i , sum;sum = 0;srand(time(NULL));for(i=1;i<n;i++){x=(double)rand()/RAND_MAX;y=(double)rand()/RAND_MAX;if(x*x+y*y<=1)sum++; }PI=4.0*sum/n;return PI; } int main() {int n;double PI;cout<<"蒙特卡羅概率算法 計算PI"<<endl;cout<<"輸入撒點的數量：";cin >> n;PI=MontePI(n);cout<<PI<<endl; }

總結

以上是生活随笔為你收集整理的ACM学习二的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。