算法與數據結構5

算法與數據結構任課教師：戴韡枚舉算法一根針掉地上了中國人：管他的，再買一根。英國人：請人偵破這根針的下落。美國人：找個磁鐵，在地上滾，把針吸起來。俄國人：根據力學原理，計算出那根針落地后最大可能彈到的范圍。德國人：在地上畫方格子，一個一個挨著找；枚舉算法的特點最簡單算法的描述就是問題本身的描述。最粗暴對所有情況作檢驗。效率最低沒有比它更低的了。這是沒有方法的方法不管連續(xù)或離散模型，對計算機而言一定是有窮的，換而言之，枚舉算法理論上一定是有解的〔但可能會一直算到宇宙終結〕。枚舉算法的構成逐一列舉可能的解的范圍。

這個過程用循環(huán)結構實現

并對每一個列舉可能的解進行檢驗，判斷是否為真正的解。

這個過程用判斷語句實現枚舉算法=循環(huán)結構+判斷語句枚舉算法

例1.判斷m是否素數。算法思想:讓m被2到除，如果m能被2～之中任何一個整數整除，那么提前結束循環(huán)，此時i必然小于或等于k(即)；如果m不能被2～k(即)之間的任一整數整除，那么在完成最后一次循環(huán)后，i還要加1，因此i=k+1，然后才終止循環(huán)。在循環(huán)之后判別i的值是否大于或等于k+1，假設是，那么說明未曾被2～k之間任一整數整除過，因此輸出“是素數〞。如下圖:例1.判斷m是否素數。

#include<stdio.h>

#include<math.h>

voidmain()

{

intm，i，k;

scanf(″%d″，&m);k=sqrt(m);

for(i=2;i<=k;i++)

if(m%i==0)break;

if(i>k)

printf("%disaprimenumber＼n″，m);

else

printf("%disnotaprimenumber＼n″，m);

}

運行結果：

17↙17isaprimenumber

例2.求100～200間的全部素數。

#include<stdio.h>

#include<math.h>

voidmain()

{

intm，k，i，n=0;

for(m=101;m<=200;m=m+2)

{

k=sqrt(m);

for(i=2;i<=k;i++)

if(m%i==0)break;

if(i>=k+1){printf(“%d″，m);n=n+1;}

if(n%10==0)printf(″\n″);

}

printf(“\n");}運行結果：

101103107109113127131137139149151157163167173179181191193197199課堂練習用10元和50元兩種紙幣組成240元，共有幾種組合方式？算法流程分析假設用a張10元和b張50元能夠組成240元設計雙重循環(huán)，循環(huán)變量為a和b判斷是否達成條件，打印結果。課堂練習在一個三角形中，三條邊a、b、c的長度都是整數，假設一條邊a的長度，邊c的長度不超過給定的整數值maxc，試設計算法，找出滿足條件的所有直角三角形。算法流程分析輸入a和maxcc作為循環(huán)變量,跑遍0到maxc之間的所有數。在循環(huán)中判斷能否構成直角三角形〔提示：b是整數〕課堂練習運發(fā)動A、B、C、E、D、E、F共6個人參加長跑決賽，觀眾甲、乙、