1.1 算法
考點1 算法的基本概念
計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。
算法(algorithm)是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，同時是明確的；此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。
1算法的基本特征
(1)可行性(effectiveness)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。
(2)確定性(definiteness)：算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。
(3)有窮性(finiteness)：算法必需在有間內(nèi)做完，即算法必需能在執(zhí)行有限個步驟之后終止。
(4)擁有足夠的情報：要使算法有效必需為算法提供足夠的情報當(dāng)算法擁有足夠的情報時，此算法才的；而當(dāng)提供的情報不夠時，算法可能無效。
2算法的基本要素
(1)算法中對數(shù)據(jù)的運算和操作：每個算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。
計算機可以執(zhí)行的基本操作是以指令的形式描述的。一個計算機系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計算機系統(tǒng)的指令系統(tǒng)。計算機程序就是按解題要求從計算機指令系統(tǒng)中選擇合適的指令所組成的指令序列在一般的計算機系統(tǒng)中，基本的運算和操作有以下4類：
①算術(shù)運算：主要包括加、減、乘、除等運算；
②邏輯運算：主要包括“與”、“或”、“非”等運算；
③關(guān)系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算；
?、軘?shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。
(2)算法的控制結(jié)構(gòu)：一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。
算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。
(3)算法設(shè)計的基本方法
計算機算法不同于人工處理的方法，下面是工程上常用的幾種算法設(shè)計，在實際應(yīng)用時，各種方法之間往往存在著一定的聯(lián)系。
(1)列舉法
列舉法是計算機算法中的一個基礎(chǔ)算法。列舉法的基本思想是，根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的?BR> 列舉法的特點是算法比較簡單。但當(dāng)列舉的可能情況較多時，執(zhí)行列舉算法的工作量將會很大。因此，在用列舉法設(shè)計算法時，使方案優(yōu)化，盡量減少運算工作量，是應(yīng)該重點注意的。
(2)歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論。
(3)遞推
遞推是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關(guān)系式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關(guān)系式往往是歸納的結(jié)果。對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。
(4)遞歸
人們在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程度(如問題的規(guī)模等)，一般總是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當(dāng)解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。
遞歸分為直接遞歸與間接遞歸兩種。
(5)減半遞推技術(shù)
實際問題的復(fù)雜程度往往與問題的規(guī)模有著密切的聯(lián)系。因此，利用分治法解決這類實際問題是有效的。工程上常用的分治法是減半遞推技術(shù)。
所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推”，是指重復(fù)“減半”的過程。
(6)回溯法
在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題，一種有效的方法是“試”。通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。
考點1 算法的基本概念
計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。
算法(algorithm)是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，同時是明確的；此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。
1算法的基本特征
(1)可行性(effectiveness)：針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。
(2)確定性(definiteness)：算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。
(3)有窮性(finiteness)：算法必需在有間內(nèi)做完，即算法必需能在執(zhí)行有限個步驟之后終止。
(4)擁有足夠的情報：要使算法有效必需為算法提供足夠的情報當(dāng)算法擁有足夠的情報時，此算法才的；而當(dāng)提供的情報不夠時，算法可能無效。
2算法的基本要素
(1)算法中對數(shù)據(jù)的運算和操作：每個算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。
計算機可以執(zhí)行的基本操作是以指令的形式描述的。一個計算機系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計算機系統(tǒng)的指令系統(tǒng)。計算機程序就是按解題要求從計算機指令系統(tǒng)中選擇合適的指令所組成的指令序列在一般的計算機系統(tǒng)中，基本的運算和操作有以下4類：
①算術(shù)運算：主要包括加、減、乘、除等運算；
②邏輯運算：主要包括“與”、“或”、“非”等運算；
③關(guān)系運算：主要包括“大于”、“小于”、“等于”、“不等于”等運算；
?、軘?shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。
(2)算法的控制結(jié)構(gòu)：一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。
算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。
(3)算法設(shè)計的基本方法
計算機算法不同于人工處理的方法，下面是工程上常用的幾種算法設(shè)計，在實際應(yīng)用時，各種方法之間往往存在著一定的聯(lián)系。
(1)列舉法
列舉法是計算機算法中的一個基礎(chǔ)算法。列舉法的基本思想是，根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的?BR> 列舉法的特點是算法比較簡單。但當(dāng)列舉的可能情況較多時，執(zhí)行列舉算法的工作量將會很大。因此，在用列舉法設(shè)計算法時，使方案優(yōu)化，盡量減少運算工作量，是應(yīng)該重點注意的。
(2)歸納法
歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論。
(3)遞推
遞推是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關(guān)系式實際上是通過對實際問題的分析與歸納而得到的，因此，遞推關(guān)系式往往是歸納的結(jié)果。對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。
(4)遞歸
人們在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程度(如問題的規(guī)模等)，一般總是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問題進行求解，而只是當(dāng)解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想。
遞歸分為直接遞歸與間接遞歸兩種。
(5)減半遞推技術(shù)
實際問題的復(fù)雜程度往往與問題的規(guī)模有著密切的聯(lián)系。因此，利用分治法解決這類實際問題是有效的。工程上常用的分治法是減半遞推技術(shù)。
所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推”，是指重復(fù)“減半”的過程。
(6)回溯法
在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題，一種有效的方法是“試”。通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再逐步試探。