第6章數(shù)學(xué)問題

1、零基礎(chǔ)學(xué)算法零基礎(chǔ)學(xué)算法第第6章：數(shù)學(xué)問題章：數(shù)學(xué)問題課程安排課程安排6.1 有趣的整數(shù)有趣的整數(shù)6.2 素?cái)?shù)素?cái)?shù)6.3 階乘階乘6.4 求求的近似值的近似值6.5 方程求解方程求解6.6 矩陣的運(yùn)算矩陣的運(yùn)算6.7 一元多項(xiàng)式的運(yùn)算一元多項(xiàng)式的運(yùn)算6.1 有趣的整數(shù)有趣的整數(shù)如果一個(gè)數(shù)恰好等于其因子之和，這個(gè)數(shù)就稱為完數(shù)。6.1.1 完數(shù)完數(shù)6=12328=124714 求10000以內(nèi)的所有完數(shù)的過程：（1）則用n去除以1n之間的所有整數(shù)，將能整除的被除數(shù)保存到一個(gè)數(shù)組中，作為n的一個(gè)因子。（2）用數(shù)n減去該因子，以方便計(jì)算各因子之和是否正好等于n。（3）繼續(xù)重復(fù)步驟1和步驟2，直至將所有

2、整數(shù)除完為止。（4）最后判斷各因子之和是否等于數(shù)n，若相等，則數(shù)n為完數(shù)，輸出該數(shù)和各因子。6.1 有趣的整數(shù)有趣的整數(shù) 假設(shè)有a、b兩個(gè)數(shù)，若a的所有因子之和等于b的所有因子之和，并且a不等于b，則稱a和b是一對(duì)親密數(shù)。如284和220就是一對(duì)親密數(shù)。 若要找出10000以內(nèi)的親密數(shù)，可使用以下算法：（1）對(duì)每一個(gè)數(shù)a，將其因子分解出來，并將因子保存到一個(gè)數(shù)組中，再將因子之和保存到變量b1。（2）將因子之和b1再進(jìn)行因子分解，并將因子保存到一個(gè)數(shù)組中，將因子之和保存到變量b2中。（3）若b2等于a，并且b1不等于b2，則找到一對(duì)親密數(shù)為a和b1，可將其輸出。（4）重復(fù)步驟（1）（3），即可找

3、出指定范圍的親密數(shù)。6.1.2 親密數(shù)親密數(shù)6.1 有趣的整數(shù)有趣的整數(shù) 一個(gè)三位數(shù)，若數(shù)值等于各位數(shù)字的三次冪之和，就稱為“水仙花數(shù)”。6.1.3 水仙花數(shù)水仙花數(shù)6.1 有趣的整數(shù)有趣的整數(shù) 所謂自守?cái)?shù)，是指一個(gè)數(shù)的平方的尾數(shù)等于該數(shù)自身的自然數(shù)。例如：6的平方等于36，尾數(shù)是6，所以6是自守?cái)?shù)；25的平方等于625，尾數(shù)是25，所以25是自守?cái)?shù)。6.1.4 自守?cái)?shù)自守?cái)?shù)26.1 有趣的整數(shù)有趣的整數(shù)歐幾里德算法歐幾里德算法 歐幾里德算法采用輾轉(zhuǎn)相除的方法來求最大公約數(shù)，這是計(jì)算兩個(gè)數(shù)最大公約數(shù)的傳統(tǒng)算法其算法思路為：（1）對(duì)于已知兩數(shù)m、n，使mn；（2）m除以n得余數(shù)r；（3）若r=0

4、，則n為求得的最大公約數(shù)，跳至第（5）求最小公倍數(shù)；否則執(zhí)行第4步；（4）將n的值保存到m中，將r的值保存到n中，重復(fù)執(zhí)行步驟（2）和（3）。（5）有了兩數(shù)的最大公約數(shù)，則最小公倍數(shù)就很簡單了，將兩數(shù)相乘的積除以最大公約數(shù)即可。 6.1.5 最大公約數(shù)最小公倍數(shù)最大公約數(shù)最小公倍數(shù)6.1 有趣的整數(shù)有趣的整數(shù)stein算法算法 stein算法只有整數(shù)的移位和加減法，而不需要進(jìn)行除法和取模運(yùn)算，這將提高算法的執(zhí)行效率。stein算法如下（求a、b兩數(shù)的最大公約數(shù)）：（1）首先判斷a或b是否為0，若a=0，b就是最大公約數(shù)；若b=0，a就是最大公約數(shù)，完成計(jì)算操作。（2）設(shè)a1=a、b1=b和c1

5、=1。（3）判斷an和bn是否為偶數(shù)，若都是偶數(shù)，則使an+1=an/2，bn+1=bn/2，cn+1=cn*2。（4）若an是偶數(shù)，bn是奇數(shù)，則使an+1=an/2，bn+1=bn，cn+1=cn。（5）若bn是偶數(shù)，an是奇數(shù)，則使bn+1=bn/2，an+1=an，cn+1=cn。（6）若an和bn都是奇數(shù)，則使an+1=|an-bn|，bn+1=min(an,bn)，cn+1 =cn。（7）n累加1，跳轉(zhuǎn)到第3步進(jìn)行下一輪運(yùn)算。 6.1.5 最大公約數(shù)最小公倍數(shù)最大公約數(shù)最小公倍數(shù)6.2 素?cái)?shù)素?cái)?shù) 所謂素?cái)?shù)，是指除了1和自身之外，沒有別的因數(shù)的數(shù)。除了1和自身外，還有別的因數(shù)的數(shù)是合

6、數(shù)。1既不是素?cái)?shù)也不是合數(shù)。素?cái)?shù)的分布是沒有規(guī)律的。如：101、401、601、701都是素?cái)?shù)，但上下面的301和901卻是合數(shù)。 要求n是不是素?cái)?shù)，可用n逐個(gè)除以2n-1之間的數(shù)，若某個(gè)數(shù)能被整除，則表示該數(shù)不是素?cái)?shù) 6.2.1 求素?cái)?shù)求素?cái)?shù)6.2 素?cái)?shù)素?cái)?shù) 所謂回文數(shù)，是指一個(gè)多位數(shù)在按位讀時(shí)，無論從左向右還是從右向左倒序讀取，其結(jié)果都是一樣的特征。例如：11、22、101、111、818、12321等?；匚臄?shù)素?cái)?shù)平方回文數(shù)6.2.2 回文素?cái)?shù)回文素?cái)?shù)6.2 素?cái)?shù)素?cái)?shù) 所謂哥德巴赫猜想，是指哥德巴赫在教學(xué)中發(fā)現(xiàn)，每個(gè)不小于6的偶數(shù)都是兩個(gè)素?cái)?shù)之和。大家都相信這個(gè)猜想是正確的，但不能證明。

7、對(duì)于哥德巴赫猜想的驗(yàn)證，算法很簡單，其基本思路是：設(shè)n為大于等于6的一個(gè)偶數(shù)，可將其分解為n1和n2兩個(gè)數(shù)，分別檢查n1和n2是否為素?cái)?shù)，如都是，則在該數(shù)得到驗(yàn)證。若n1不是素?cái)?shù)，就不必再檢查n2是否素?cái)?shù)。先從n1=2開始，檢驗(yàn)n1和n2（n2=n-n1）是否素?cái)?shù)。然后使n1+2再檢驗(yàn)n1、n2是否素?cái)?shù)，直到n1=n/2為止。6.2.3 哥德巴赫猜想哥德巴赫猜想6.3 階乘階乘6.3.1 用遞歸計(jì)算階乘用遞歸計(jì)算階乘6.3.2 大數(shù)階乘大數(shù)階乘6.4 求求的近似值的近似值6.4.1 概率法概率法6.4 求求的近似值的近似值6.4.2 割圓法割圓法6.4 求求的近似值的近似值6.4.3 公式法公

8、式法6.4 求求的近似值的近似值6.4.4 計(jì)算任意位數(shù)的計(jì)算任意位數(shù)的52326.5 方程求解方程求解6.5.1 高斯消元法解線性方程組高斯消元法解線性方程組55446720435321321321xxxxxxxxxkjkkikijijaaaaakknkjjkjknknnnnnaxaaxaax/ )(/1116.5 方程求解方程求解6.5.2 二分法解非線性方程二分法解非線性方程 二分法又稱對(duì)分法，是最簡單的求解一元非線性方程根的算法之一。其基本思想是：將含根區(qū)間i逐次分半縮小，得到一個(gè)區(qū)間長度以1/2的比例減小的含根區(qū)間序列i1、i2，在給定根的誤差界時(shí)，利用ik的長度趨于0的特點(diǎn)，可得到

9、在某個(gè)區(qū)間i中求得滿足要求的近似根。01523 xx6.5 方程求解方程求解6.5.3 牛頓迭代法解非線性方程牛頓迭代法解非線性方程 牛頓迭代法是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。迭代法的基本思想就是構(gòu)造一串收斂到解的序列，即建立一種從已有近似解來計(jì)算新的近似解的迭代式，然后選取方程的某個(gè)初始近似值x0代入迭代式，反復(fù)這個(gè)過程使得到的根逐漸逼近于真實(shí)根，直到滿足精度為止。045 . 13234xxx039423xxx導(dǎo)函數(shù)：導(dǎo)函數(shù)：6.6 矩陣運(yùn)算矩陣運(yùn)算6.6.1 矩陣加法和乘法運(yùn)算矩陣加法和乘法運(yùn)算1. 矩陣加法運(yùn)算矩陣加法運(yùn)算2. 矩陣乘法運(yùn)算矩陣乘法運(yùn)算6.

10、6 矩陣運(yùn)算矩陣運(yùn)算6.6.2 多維矩陣轉(zhuǎn)一維矩陣多維矩陣轉(zhuǎn)一維矩陣二維矩陣轉(zhuǎn)一維矩陣下標(biāo)公式（以行為主）： loc=row*每行元素?cái)?shù)量+column二維矩陣轉(zhuǎn)一維矩陣下標(biāo)公式（以列為主）： loc= column*每列元素?cái)?shù)量+row6.6 矩陣運(yùn)算矩陣運(yùn)算6.6.3 逆矩陣逆矩陣 對(duì)于n階方陣a，如果存在一個(gè)n階方陣b，使得ab=ba=c（c為n階單位矩陣），則把方陣b稱為a的逆矩陣（簡稱逆陣）記作a-1，即b=a-1 6.6 矩陣運(yùn)算矩陣運(yùn)算6.6.4 稀疏矩陣稀疏矩陣 將表示稀疏矩陣的非0元素的三元組按行優(yōu)先（或列優(yōu)先）的順序排列，并依次存放在數(shù)組中，這種稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)稱為三元組表。6.7 一元多項(xiàng)式的運(yùn)算一元多項(xiàng)式的運(yùn)算6.7.1 多項(xiàng)式加法多項(xiàng)式加法 一元多項(xiàng)式加法運(yùn)算的規(guī)則非常簡單，就是將具有相等冪項(xiàng)的系數(shù)相加即可得到合并后的多項(xiàng)式。若某個(gè)冪只存在于一個(gè)多項(xiàng)式中，則直接合并到結(jié)果中。5312653)(xxxxp43227)(xxxxp543221325753)()()(xxxxxxp