大一上學(xué)期算法

1、要使計(jì)算機(jī)解決一個問題，必須首先針對問題設(shè)計(jì)一個解題步驟，然后將解題步驟用程序代碼實(shí)現(xiàn)，由程序解決指定的問題。所謂的算法，就是指問題的解題步驟，而程序則是用某種程序設(shè)計(jì)語言對解題步驟的描述。 由此可見，算法是問題求解規(guī)則的一種過程描述。在算法中，要精確定義一系列操作，以便在有限的步驟內(nèi)得到問題的解。 算法的設(shè)計(jì)一般采用由上至下，逐步求精的方法。算法算法會因求解問題的不同而千變?nèi)f化，但是它們都具有如下特性：（1）確定性：算法中的每一步驟都必須有明確的定義，不存在歧義。（2）有窮性：算法必須在有限的步驟之后終止。（3）可行性：算法的每一步驟都可以通過有限個已經(jīng)實(shí)現(xiàn)的基本操作來實(shí)現(xiàn)。（4）輸入：一個

2、算法有零個或多個輸入。（5）輸出：一個算法應(yīng)該至少有一個輸出。累加與累乘累加與累乘是最基本的算法，一般依靠循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。累加就是在原來的和的基礎(chǔ)上一次又一次地再加上一個數(shù)；累乘又叫連乘是在原來積的基礎(chǔ)上一次又一次地再乘上一個數(shù)。窮舉法 窮舉法是對所有可能是解的候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，從中找出那些符合要求的候選解作為問題的解。一般采用循環(huán)實(shí)現(xiàn)。 【例3- 107】數(shù)字燈謎。設(shè)有算式: ABCD-） CDC ABC遞推法 遞推法又稱迭代法，是利用問題本身所具有的一種遞推關(guān)系求問題解的方法。設(shè)要求問題的規(guī)模為N的解，當(dāng)N=1時，解或?yàn)橐阎?，或能非常方便地得到。能采用遞推法構(gòu)造算法的問題

3、一定有著遞推性質(zhì)，即當(dāng)?shù)玫絾栴}規(guī)模為i-1的解后，能從已求得的規(guī)模為1，2，i-1的一系列解，構(gòu)造出問題規(guī)模為i的解。這樣，程序可以從i=0或i=1出發(fā)，由已知i-1規(guī)模的解，通過遞推，獲得規(guī)模為i的解，直至得到規(guī)模為N的解。 【例3- 108】打印斐波那契(Fibonacci)數(shù)列的前20項(xiàng)斐波那契數(shù)列如下: 0，1，1，2，3，5，8，13，即從第三項(xiàng)起每一項(xiàng)是其前兩項(xiàng)之和遞歸算法 如果一個規(guī)模為N的問題，設(shè)法將它分解成一些規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解方法和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模

4、稍大問題的解，那么就可以用遞歸算法求解。通俗的講，就是用自身的結(jié)構(gòu)來描述自身。N! 輾轉(zhuǎn)相除法 用輾轉(zhuǎn)相除法求兩自然數(shù)m，n的最大公約數(shù)和最小公倍數(shù)。解：求最大公約數(shù)的算法： (1)對于已知兩數(shù)m，n，使得mn； (2) m除以n得余數(shù)r； (3)若r=0，則n為最大公約數(shù)結(jié)束；否 則執(zhí)行(4)； (4)mn，nr，再重復(fù)執(zhí)行(2)。求得了最大公約數(shù)后，最小公倍數(shù)就是將原來的兩個數(shù)相乘后除以最大公約數(shù)。 If m n Then t = m: m = n: n = tr=m mod nDo While (r 0) m=n n=r r= m mod nLoopPrint 最大公約數(shù)=, n 數(shù)組排

5、序 對于n個數(shù)按遞增或遞減的次序進(jìn)行的排列，叫排序。排序有很多種，如選擇排序、冒泡排序等。 選擇法對已知的六個數(shù)9、8、7、6、5、0，用選擇法遞增排序解：(1)從n個數(shù)的序列中選出最小的數(shù)(遞增),與第1個數(shù)交換位置; (2)除第1個數(shù)外，其余n-1個數(shù)再按(1)的方法選出次小的數(shù)，與第2個數(shù)交換位置; (3)重復(fù)(1)n-1遍，最后構(gòu)成遞增序列。 冒泡法 對已知的六個數(shù)9、8、7、6、5、0，用冒泡法遞增排序解：冒泡法排序與選擇排序相似，選擇法排序在每輪循環(huán)找到的第n小的數(shù)字的時候，就將其和第n個位置交換；而冒泡法排序在每輪循環(huán)找到的第n小的數(shù)字的時候，就和相鄰的數(shù)做比較，當(dāng)次序不符合要求時就交換位置，移到第n個位置。 數(shù)組查找 順序查找 二分法查找 用二分法查找可以提高效率，但在使用前被查找數(shù)組必須有序。High：表示查找范圍的頂部Low：表示查找范圍的底部 Mid：表示查找范圍的中間Mid=(high+low)2取整要