天天看點

6數學模型和數學模組化

很簡單的例子:

           已知有五個數,求前四個數與第五個數分    别相乘後的最大當數。給出兩個算法分别如下:

  

6數學模型和數學模組化

  以上兩個算法基于的數學模型是不同的,一個算法先積再求最大值,另一個算法先求最大值再求積,求從上表可以看出,後一個算法的效率明顯要高于前一個算法。

    數學模組化就是把現實世界中的實際問題加以提煉,抽象為數學模型,求出模型的解,驗證模型的合理性,并用該數學模型所提供的解答來解釋現實問題,我們把數學知識的這一應用過程稱為數學模組化。   

數學模組化的基本方法

  從分析問題的幾種簡單的、特殊的情況中,發現一般規律或作出某種猜想,進而找到解決問題的途徑。這種研究問題方法叫做歸納法。即歸納法是從簡單到複雜,由個别到一般的一種研究方法。

楊輝三角形的應用

【例】求n次二項式各項的系數:已知二項式的展 開式為:

6數學模型和數學模組化

問題分析:若隻用的數學組合數學的知識,直接模組化

6數學模型和數學模組化

 k=0,1,2,3……n。

用這個公式去計算,n+1個系數,即使你考慮到了前後系數之間的數值關系:算法中也要有大量的乘法和除法運算,效率是很低的。

數學知識是各階多項式的系數呈楊輝三角形的規律

(a+b)0                        1  

(a+b)1                  1       1

(a+b)2          1      2      1

(a+b)3         1     3        3       1

(a+b)4     1      4        6        4       1

(a+b)5    ……

     則求n次二項式的系數的數學模型就是求n階楊輝三角形。

算法設計要點:   除了首尾兩項系數為1外,當n>1時,(a+b)n的中間各項系數是(a+b)n-1的相應兩項系數之和,如果把(a+b)n的n+1的系數列為數組c,則除了c(1)、c(n+1)恒為1外,設(a+b)n的系數為c(i),(a+b)n-1 的系數設為c’(i)。則有:

        c(i)=c’(i)+c’(i-1)

   而當n=1時,隻有兩個系數 c(1) 和 c(2) (值都為1)。不難看出,對任何n,  (a+b)n的二項式系數可由(a+b)n-1的系數求得,直到n=1時,兩個系數有确定值,故可寫成遞歸子算法。

最大公約數的應用

【例】數組中有n個資料,要将它們順序循環向後移k位,即前面的元素向後移k位,後面的元素則循環向前移k位,例:1、2、3、4、5循環移3位後為:3、4、5、1、2。考慮到n會很大,不允許用2*n以上個空間來完成此題。

    問題分析1:若題目中沒有關于存儲空間的限制,我們可以友善地開辟兩個一維數組,一個存儲原始資料,另一個存儲移動後的資料。

這個算法的時間效率是n次移動(指派)。

有可能k>n,這樣移動會出現重複操作,可以在輸入資料後,執行k = k mod n;   以保證不出現重複移動的問題。這個算法的移動(指派)次數為k*n。當n較大時不是一個好的算法。

問題分析2:

● 将最後一個存儲空間的資料,存儲在臨時存儲空間中;

● 其餘資料逐個向後移動一位。

這樣操作共k次就能完成問題的要求。

算法2如下:

問題分析3 利用一個臨時存儲空間,把每一個資料一次移動到位:

1) 一組循環移動的情況:

        通過計算我們可以确定某個元素移動後的具體位置,如n=5, k=3時:

          0、1、2、3、4循環移3位後為2、3、4、0、1。

可通過計算得出0移到3的位置,3移到1的位置,1移到4的位置,4移到2的位置,2移到0的位置;一組移動(0-3-1-4-2-0)正好将全部資料按要求進行了移動。這樣隻需要一個輔助變量,每個資料隻需一次移動就可完成整個移動過程。

如果算法就這樣按一組移動去解決問題,就錯了。因為還有其它情況。

2)多組循環移動的情況:算法不能按一組移動去解決問題。

   看下一個例子,當n=6,k=3時,1、2、3、4、5、6經移動 的結果是4、5、6、1、2、3. 并不象上一個例子,一組循環 移動沒有将全部資料移動到位。還需要(2-5-2)(3-6-3)兩組移動,共要進行三組循環移動(1-4,2-5,3-6)才能将全部資料操作完畢。

             循環移動的組數,與k、n的是怎麼樣的關系呢?

           我們再看一個例子,當N=6,K=2時,     1、2、3、4、5、6經移動的結果是5、6、1、2、3、4.     1移到3的位置,3移到5的位置,5移到1的位置,一組移動完成了3個資料的移動,接下來,還有一組2-4-6-2。共進行二組循環移動,就能将全部資料移動完畢。

數學模型:循環移動的組數等于N與K的最大公約數。

算法設計:

1)編寫函數,完成求n , k最大公約數m的功能

2)進行m組循環移動。

3)每組移動,和算法2一樣,通過計算可以确定某個

     元素移動後的具體位置。在移動之前,用臨時變量

     存儲需要被覆寫的資料。

算法3如下:

算法分析:每組循環移動都是從前向後進行的,一次移動需要兩次指派,總體大約需要指派2n次。

    能不能繼續提高效率為指派n次呢?請考慮改進每組循環移動的方式為從後開始移動,以提高運作效率。以例子說明:

n=6,k=2時,第一組循環移動0-2-4,在算法3中是這樣實作的:

a[0]=>b0,

a[2]=>b1, b0(a[0])=>a[2],b1=> b0;

a[4]=>b1, b0(a[2])=> a[4],b1=> b0;

a[0]=>b1, b0(a[4])=> a[0] ,b1=> b0;

改進後(和算法2類似):

a[4]=>b ;a[2]=>a[4],a[0]=>a[2], b=>a[0]。

将每組最後一個資料元素存儲在輔助存儲空間,以後就可以安全地覆寫後面的數組元素了(注意覆寫順序)。這樣,一組循環移動隻需一次将資料存入輔助存儲空間,其後一次移動隻需一次指派,全部工作大約需要指派n次就可完成。

公倍數的應用

【例】程式設計完成下面給“餘”猜數的遊戲:

你心裡先想好一個1~100之間的整數x,将它分别除以3、5和7并得到三個餘數。你把這三個餘數告訴計算機,計算機能馬上猜出你心中的這個數。遊戲過程如下:

please  think  of  a  number  between  1  and  100

your  number  divided  by  3  has  a  remainder  of?  1

your  number  divided  by  5  has  a  remainder  of?  0

your  number  divided  by  7  has  a  remainder  of?  5

let  me  think  a  moment…

your  number  was  40

問題分析:算法的關鍵是:找出餘數與求解數之間的關系,

也就是建立問題的數學模型。

數學模型:

 1)不難了解當s=u+3*v+3*w時,s除以3的餘數與u除以3的

餘數是一樣的。

 2)對s=cu+3*v+3*w,當c除以3餘數為1的數時, s除以3的

餘數與u除以3的餘數也是一樣的。證明如下:

    c 除以 3餘數為1,記c=3*k+1,則s=u+3*k*u+3*v+3*w,由1)的結論,上述結論正确。

   記a,b,c分别為所猜資料d除以3,5,7後的餘數,則

   d=70*a+21*b+15*c。

   為問題的數學模型,其中70稱作a的系數,21稱作b的系數,15稱作c的系數。

由以上數學常識,a、b、c的系數必須滿足:

1) b、c的系數能被3整除,且a的系數被3整除餘1;這樣d除以3的餘數與a相同。

2) a、c的系數能被5整除,且b的系數被5整除餘1;這樣d除以5的餘數與b相同。

3)   a、b的系數能被7整除,且c的系數被7整除餘1;這樣d除以7的餘數與c相同。

由此可見:

   c的系數是3和5的最公倍數且被7整除餘1,正好是15;

   a的系數是7和5的最公倍數且被3整除餘1,最小隻能是70;

   b的系數是7和3的最公倍數且被5整除餘1,正好是21。

算法設計:用以上模型求解的數d,可能比100大,這時隻要減去3,5,7的最小公倍數就是問題的解了。

裴波那契數列應用

【例】樓梯上有n階台階,上樓可以一步上1階,也可以一步上2階,編寫算法計算共有多少種不同的上樓梯方法。

數學模型:此問題如果按照習慣,從前向後思考,也就是從第一階開始,考慮怎麼樣走到第二階、第三階、第四階……,則很難找出問題的規律;而反過來先思考“到第n階有哪幾種情況?”,答案就簡單了,隻有兩種情況:

      1)  從第n-1階到第n階;

      2)  從第n-2階到第n階。

   記n階台階的走法數為f(n),則

   f(n)= 1                  n=1

  f(n)=2              n=2

  f(n-1)+f(n-2)       n>2

算法設計:算法可以用遞歸或循環完成。下面是問題的遞歸算法。

算法如下:

遞推關系求解方程

【例】核反應堆中有α和β兩種粒子,每秒鐘内一個α粒子可以反應産生3個β粒子,而一個β粒子可以反應産生1個α粒子和2個β粒子。若在t=0時刻的反應堆中隻有一個α粒子,求在t時刻的反應堆中α粒子和β粒子數。

數學模型1:本題中共涉及兩個變量,設在i時刻α粒子數為ni,β粒子數為mi,則有:n0=1,m0=0,ni=mi—1,mi=3ni—1+2mi—1

算法設計1:本題友善轉化為求數列N和M的第t項,可用遞推的方法求得nt和mt,此模型的算法如下:

算法分析1:此模型的空間需求較小,時間複雜度為O(n),但随着n的增大,所需時間越來越大。

數學模型2:設在t時刻的α粒子數為f(t),β粒子數為g(t),依題可知:

    g(t)=3f(t -1)+2g(t -1)            (1)

    f(t)=g(t -1)                      (2)

    g(0)=0,f(0)=1

   下面求解這個遞歸函數的非遞歸形式

   由(2)得f(t -1)=g(t-2)             (3)

   将(3)代入(1)得

  g(t)=3g(t -2)+2g(t-1)   (t≥2)    (4)

 g(0)=0,g(1)=3

 (4)式的特征根方程為:

 x2—2x—3=0

 其特征根為x1=3,x2= -1

是以該式的遞推關系的通解為

g(t)=C1·3t+C2·( -1)t

代入初值g(0)=0,g(1)=3得

C1+C2=0

3C1—C2=3

解此方程組

6數學模型和數學模組化

是以該遞推關系的解為

∴g(t)=

6數學模型和數學模組化
6數學模型和數學模組化

6數學模型和數學模組化

由數學模型2,設計算法2如下

算法分析:在數學模型2中,運用數學的方法建立了遞歸函數并轉化為非遞歸函數。它的優點是算法的複雜性與問題的規模無關。針對某一具體資料,問題的規模對時間的影響微乎其微。