算法設(shè)計(jì)：第九講ppt課件-閱讀頁
2025-05-18 01:31本頁面
【正文】 number divided by 7 has a remainder of? 5 your number is 40 公倍數(shù)的應(yīng)用 【 問題分析 】 算法設(shè)計(jì)的關(guān)鍵： 找出余數(shù)與求解數(shù)之間的關(guān)系 ， 建立問題的數(shù)學(xué)模型 。 2） 對(duì) s=cu+3*v+3*w， 當(dāng) c是 除以 3余 1的數(shù)時(shí) , s除以 3的 余數(shù)與 u除以 3的余數(shù)也是一樣的 。 main( ) { int a,b,c,d。/*除 3后的余數(shù) */ input(b)。/*除 7后的余數(shù) */ d=70*a+21*b+15*c。/*105為 3,5,7的最小公倍數(shù) */ print( “your number is ”, d)。 【 例 】 樓梯上有 n階臺(tái)階，上樓可以一步上 1階，也可以一步上 2階，編寫算法計(jì)算共有多少種不同的上樓梯方法。 斐波那契數(shù)列的應(yīng)用 反向分析法 記 n階臺(tái)階的走法數(shù)為 f(n)，則 f(n)= 1 n=1 f(n)= 2 n=2 f(n)=f(n1)+f(n2) n2 斐波那契數(shù)列的應(yīng)用 （ 2）倒推法：是對(duì)某些特殊問題所采用的從后向前推解問題的方法。吉普車的總裝油量為 500加侖，耗油率為 1加侖 /公里。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫，以及各處的貯油量。 【 例 】 核反應(yīng)堆中有 α 和 β 兩種粒子，每秒鐘內(nèi)一個(gè) α 粒子可以反應(yīng)產(chǎn)生 3個(gè) β 粒子，而一個(gè) β 粒子可以反應(yīng)產(chǎn)生 1個(gè) α粒子和 2個(gè) β 粒子。 【 分析 】 特征根求解遞歸方程 時(shí)刻 α β 0 1 0 1 0 3 2 3 6 3 6 3*3+2*6 …… i β i1 3*ai1+2*bi1 【 數(shù)學(xué)模型 1】 本題中共涉及兩個(gè)變量， i時(shí)刻 α 粒子數(shù)為 ni， β 粒子數(shù)為 mi，則有： n0=1,m0=0,ni=mi1， mi=3ni1+2mi1 特征根求解遞歸方程 main（） { int n[100],m[100],t,i。 n[0]=1。 for (i=1。i++) //進(jìn)行 t次遞推 { n[i]=m[i1]。 } print(n[t]， m[t])。 input(t)。 /*n代表 a粒子數(shù)量 */ m=pow(3,t+1)。 m=m+3。 m=m3。 m=int(m/4)。 } 特征根求解遞歸方程 算法分析：在數(shù)學(xué)模型 2中，運(yùn)用數(shù)學(xué)的方法建立了遞歸函數(shù)并轉(zhuǎn)化為非遞歸函數(shù)。針對(duì)某一具體數(shù)據(jù)，問題的規(guī)模對(duì)時(shí)間的影響微乎其微。 窮舉法 【 例 2】 解數(shù)字迷： A B C A B A D D D D D D 算法設(shè)計(jì) 2：按除法枚舉 ? 將算式變形為除法： DDDDDD/A=ABCAB。 窮舉法 ?本節(jié)將通過蠻力策略，用算法模擬問題中所描述的全部過程和全部狀態(tài)，來找出問題的解，并與經(jīng)過數(shù)學(xué)建模后的算法進(jìn)行效率上的比較。 轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動(dòng)每一把門鎖，即把全部鎖打開；第二次通過牢房時(shí)，從第二間開始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；第 k次通過牢房，從第 k間開始轉(zhuǎn)動(dòng)，每隔 k1 間轉(zhuǎn)動(dòng)一次；問通過 n次后，那些牢房的鎖仍然是打開的？ 其他范例 方法一：窮舉法 for (i=1。i++) for (j=i。j=j+i) a[i]=1a[i]。i=n。 for(j=2。j=j++) if(i%j==0） s=s+1。 } } 其他范例 方法三：完全平方數(shù)的因數(shù)個(gè)數(shù)為奇數(shù)。 。 else bre
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1