典型算法舉例

1、典型算法舉例：歷史上有三大算法：1，求最大公約數(shù)的歐幾里得輾轉(zhuǎn)相除法；2，求素?cái)?shù)的埃拉托塞尼篩法；3，求方根的開(kāi)方算法。后面兩種方法都可以用公式表達(dá)。一，求素?cái)?shù)的埃拉托塞尼篩法公式。屬于遞歸的。篩法與公式的關(guān)系：公元前250年同樣是古希臘的數(shù)學(xué)家埃拉托塞尼提出一種篩法：（一）“要得到不大于某個(gè)自然數(shù)N的所有素?cái)?shù)，只要在2-N中將不大于N的素?cái)?shù)的倍數(shù)全部劃去即可”。（二）將上面的內(nèi)容等價(jià)轉(zhuǎn)換：“如果N是合數(shù)，則它有一個(gè)因子d滿足1<dN”。（基礎(chǔ)數(shù)論13頁(yè)，U杜德利著，上?？萍汲霭嫔纾?。.（三）再將（二）的內(nèi)容等價(jià)轉(zhuǎn)換：“若自然數(shù)N不能被不大于(根號(hào))N的任何素?cái)?shù)整除，則N是一個(gè)素?cái)?shù)”。見(jiàn)

2、（代數(shù)學(xué)辭典上海教育出版社1985年。屜部貞世朗編。259頁(yè)）。（四）這句話的漢字可以等價(jià)轉(zhuǎn)換成為用英文字母表達(dá)的公式：N=p1m1+a1=p2m2+a2=.=pkmk+ak 。(1)其中 p1，p2，.，pk表示順序素?cái)?shù)2，3，5，,。a0。即N不能是2m+0，3m+0，5m+0，.，pkm+0形。若N<P（k+1）的平方 注：后面的1，2，3，.，k，（k+1）是腳標(biāo)，由于打印不出來(lái)，凡字母后面的數(shù)字或者i與k都是腳標(biāo) ，則N是一個(gè)素?cái)?shù)。（五）可以把（1）等價(jià)轉(zhuǎn)換成為用同余式組表示：Na1(modp1)， Na2(modp2)，.，Nak(modpk)。 (2)例如，29，29不能夠

3、被根號(hào)29以下的任何素?cái)?shù)2，3，5整除，29=2x14+1=3x9+2=5x5+4。 291(mod2)，292(mod3)， 294(mod5)。29小于7的平方49，所以29是一個(gè)素?cái)?shù)。以后平方用“*”表示，即：=m*。由于（2）的模p1，p2，.，pk 兩兩互素，根據(jù)孫子定理(中國(guó)剩余定理）知，（2）在p1p2.pk范圍內(nèi)有唯一解。例如k=1時(shí)，N=2m+1，解得N=3，5，7。求得了（3，3*）區(qū)間的全部素?cái)?shù)。k=2時(shí)，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）區(qū)間的全部素?cái)?shù)。k=3時(shí),-| 5m+1-|-

4、 5m+2-| 5m+3,| 5m+4.|-|-|-|-|-|n=2m+1=3m+1= |-31-|-7, 37-|-13,43|-19-|n=2m+1=3m+2= |-11,41-|-17,47-|-23-|-29-|-求得了（7，7*）區(qū)間的全部素?cái)?shù)。仿此下去，可以求得任意大的數(shù)以內(nèi)的全部素?cái)?shù)。二，求方根的開(kāi)方方法公式;開(kāi)方的反饋方法或者叫做自動(dòng)調(diào)節(jié)開(kāi)方。方法是迭代的。公式：X_(n+1)=X_n+【A/(X（k-1）)-X_n】1/k"_"表示下角標(biāo)，“”表示上角標(biāo)。例如，X2,表示x的平方；X_1表示第一個(gè)X。例如，A=5，k=3.即開(kāi)3次方。公式：X(n+1）=X

5、n+（A/Xn2-Xn）1/35介于13至23之間（1的3次方=1，2的3次方=8）X_0可以取1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0都可以。例如我們?nèi)?.0.按照公式：第一步：X_1=2.0+5/(2.02)-2.01/3=1.7.。即5/2×2=1.25，1.25-2=-0.75，0.75×1/3=0.25，2-0.25=1.75，取2位數(shù)值,即1.7。第二步：X_2=1.7+5/(1.72)-1.71/3=1.71.。即5/1.7×1.7=1.73010，1.73-1.7=0.03，0.03×1/3=0.01

6、，1.7+0.01=1.71。取3位數(shù)，比前面多取一位數(shù)。第三步：X_3=1.71+5/(1.712)-1.711/3=1.709第四步：X_4=1.709+5/(1.7092)-1.7091/3=1.7099.這種方法可以自動(dòng)調(diào)節(jié)，第一步與第三步取值偏大，但是計(jì)算出來(lái)以后輸出值會(huì)自動(dòng)轉(zhuǎn)??；第二步，第四步輸入值偏小，輸出值自動(dòng)轉(zhuǎn)大。X_4=1.7099.當(dāng)然也可以取1.1，1.2，1.3，。1.8，1.9中的任何一個(gè)。.a必須大于或等于零，即a為非負(fù)數(shù)開(kāi)平方公式X（n + 1） = Xn + (A / Xn Xn)1 / 2.。（n，n+1與是下角標(biāo)）例如，A=5：5介于2的平方至3的平方;之

7、間。我們?nèi)〕跏贾?.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9都可以，我們最好取 中間值2.5。第一步：2.5+（5/2.5-2.5)1/2=2.2；即5/2.5=2，2-2.5=-0.5，-0.5×1/2=-0.25，2.5+(-0.25)=2.25，取2位數(shù)2.2。第二步：2.2+(5/2.2-2.2)1/2=2.23；即5/2.2=2.27272，2.27272-2.2=-0.07272，-0.07272×1/2=-0.03636，2.2+0.03636=2.23。取3位數(shù)2.23。第三步：2.23+(5/2.23-2.23)1/2=2.236

8、。即5/2.23=2.2421525，,2.2421525-2.23=0.0121525，,0.0121525×1/2=0.00607，,2.23+0.006=2.236.，取4位數(shù)。每一步多取一位數(shù)。這個(gè)方法又叫反饋開(kāi)方，即使你輸入一個(gè)錯(cuò)誤的數(shù)值，也沒(méi)有關(guān)系，輸出值會(huì)自動(dòng)調(diào)節(jié)，接近準(zhǔn)確值。例如A=200.200介如10的平方-20的平方之間。初始值可以取11，12，13，14，15，16，17，18，19。我們?nèi)?5.15+（200/15-15)1/2=14。取19也一樣得出14.。：19+（200/19-19)1/2=14.。14+(200/14-14)1/2=14.1。14.1+（200/14.1-14.1)1/2=14.14.中間值，即1.5。 1.5+（5/1.52;-1.5）1/3=1.7。順便介紹開(kāi)5次方公式：X(n+1)=Xn+(A/X4-Xn)1/5 . (n，n+1是下角標(biāo)）例如：A=5;5介入1的5次方至2的5次方之間。2的5次方是32，5靠近1的5次方。初始值可以取1.1，1.2，1.3，1.4，1.5，1.6，