南財數(shù)據(jù)智能化課件

計算機軟件技術(shù)基礎(chǔ)（第4版）王曉慶QQ:26445100Office:8671-8170Mobile:189-5199-5050Email:onermb@計算機軟件技術(shù)基礎(chǔ)（第4版）王曉慶第1章預(yù)備知識1.1集合1.2算法第1章預(yù)備知識1.1集合1.1集合1.1.1集合及其基本性質(zhì)1.1.2自然數(shù)集與數(shù)學歸納法1.1.3笛卡爾積1.1.4二元關(guān)系31.1集合1.1.1集合及其基本性質(zhì)31.1.1集合及其基本性質(zhì)

1.集合的基本概念所謂集合，是指若干個或無窮多個具有相同屬性的元（元素）的集體。通常，一個集合名稱用大寫字母表示，而集合中的某個元素用小寫字母表示。41.1.1集合及其基本性質(zhì)455667788一個集合，通常用以下兩種方法表示。

(1)列舉法用列舉法表示一個集合是將此集合中的元素全部列出來，或者列出若干項但能根據(jù)規(guī)律可知其所有的元素。例如9一個集合，通常用以下兩種方法表示。9大于1而小于100的所有整數(shù)的集合可以表示為

A＝{2，3，4，…，99}，有限集所有整數(shù)構(gòu)成的集合可以表示為

Z＝{0，±1，±2，±3，…，}，無限集空集表示為＝{}，空集10大于1而小于100的所有整數(shù)的集合可以表示為10(2)性質(zhì)敘述法用性質(zhì)敘述法表示一個集合是將集合中的元素所具有的屬性描述出來。例如：11(2)性質(zhì)敘述法11大于1而小于100的所有整數(shù)的集合可以表示為

A＝{a|1＜a＜100的所有整數(shù)}所有整數(shù)構(gòu)成的集合可以表示為

Z＝{z|z為一切整數(shù)}大于0而小于1的所有實數(shù)構(gòu)成的集合可以表示為

B＝{b|0＜b＜1的所有實數(shù)}所有實數(shù)構(gòu)成的集合可以表示為

R＝{r|r為一切實數(shù)}12大于1而小于100的所有整數(shù)的集合可以表示為1213132.集合的基本運算(1)兩個集合的并（union）設(shè)有兩個集合M和N，它們的并集記作M∪N，其定義如下：

即兩個集合M與N的并集是指M與N中的所有元素（去掉重復(fù)的元素）組成的集合。142.集合的基本運算14(2)兩個集合的交（intersection）設(shè)有兩個集合M和N，它們的交集記作M∩N，其定義如下：

即兩個集合M與N的交集是指M與N中所有共同元素組成的集合。15(2)兩個集合的交（intersection）15兩個集合與的并、交均滿足交換律，即

M∪N＝N∪MM∩N＝N∩M16兩個集合與的并、交均滿足交換律，即16(3)兩個集合的差（difference）設(shè)有兩個集合M和N，M和N的差集記作M－N，其定義如下：

M－N＝{α|α∈M但α不屬于N}

兩個集合的差不滿足交換律，即

M－N≠N－M17(3)兩個集合的差（difference）17

例設(shè)集合

A＝{a，b，c，d，e}B＝{d，e，f，g，h}則

A∪B＝{a，b，c，d，e，f，g，h}A∩B＝{d，e}A－B＝{a，b，c}B－A＝{f，g，h}18例設(shè)集合18基本性質(zhì)：(1)結(jié)合律

(A∩B)∪C＝A∩(B∩C)(A∪B)∪C＝A∪(B∪C)(2)分配律

A∩(B∪C)＝(A∩B)∪(A∩C)A∪(B∩C)＝(A∪B)∩(A∪C)(3)(A－B)∪(B－A)＝(A∪B)－(A∩B)(4)B∩(A－B)＝Φ(A∩B)∪(A－B)＝A19基本性質(zhì)：193.映射203.映射20212122222323242425251.1.2自然數(shù)集與數(shù)學歸納法261.1.2自然數(shù)集與數(shù)學歸納法26由所有自然數(shù)所組成的集合

{1，2，3，…}稱為自然數(shù)集。自然數(shù)集是一個無限集。由自然數(shù)組成的集合均是自然數(shù)集的子集。自然數(shù)集的子集可以是有限集，也可以是無限集。27由所有自然數(shù)所組成的集合27與自然數(shù)集對等（即具有相等濃度）的集合稱為可列集（或可數(shù)集）。任一可列集中的元素排列時可標以正整數(shù)下標，即任意可列集均可寫成28與自然數(shù)集對等（即具有相等濃度）的集合稱為可列集（或可數(shù)集）定理：在自然數(shù)集的任一非空子集M中，必定有一個最小數(shù)。即在集合M中有不大于其它任意數(shù)的數(shù)。29定理：293030定理：設(shè)M是由自然數(shù)形成的集合，如果它含有1，2，…，k，并且當它含有數(shù)n－1，n－2，…，n－k（n＞k）時，也含有數(shù)n，那么它含有所有的自然數(shù)，即M是自然數(shù)集。31定理：313232為了證明一個命題對于所有的自然數(shù)是真，采用數(shù)學歸納法證明的步驟如下：(1)證明命題對于自然數(shù)1，2，…，k是真的；(2)假設(shè)命題對于自然數(shù)n－k，n－k＋1，…，n－1（n＞k）是真的（這一步稱為歸納假設(shè)）；(3)證明命題對于自然數(shù)n也是真的。33為了證明一個命題對于所有的自然數(shù)是真，33例證明下列命題：對于任意的自然數(shù)n，必存在一對非負整數(shù)(i，j)有

7＋n＝3i＋5j34例證明下列命題：34證明：(1)當n＝1時，有7＋1＝3＋5，即i＝1，j＝1。命題成立。當n＝2時，有7＋2＝3×3＋5×0，即即i＝3，j＝0。命題成立。當n＝3時，有7＋3＝3×0＋5×2，即即i＝0，j＝2。命題成立。(2)假設(shè)命題對于自然數(shù)n－1，n－2，n－3（n＞3）成立（歸納假設(shè)）。(3)考慮自然數(shù)n，有

7＋n＝[7＋(n－3)]＋3根據(jù)歸納假設(shè)，對于自然數(shù)n－3命題成立，設(shè)存在一對非負整數(shù)I，J有

7＋(n－3)＝3I＋5J則有

7＋n＝[7＋(n－3)]＋3＝3(I＋1)＋5J＝3i＋5j其中i＝I＋1，j＝J均為非負整數(shù)。即對于自然數(shù)n命題也成立。由此得出結(jié)論，對于所有的自然數(shù)n命題成立。35證明：351.1.3笛卡爾積361.1.3笛卡爾積36373738381.1.4二元關(guān)系391.1.4二元關(guān)系3940404141424243434444454546461.2算法1.2.1算法的基本特征1.2.2算法設(shè)計基本方法1.2.3算法的復(fù)雜度分析1.2算法1.2.1算法的基本特征1.2.1算法的基本概念

算法是指解題方案的準確而完整的描述。

1.能行性(effectiveness)

A＝1012，B＝1，C＝－1012

A＋B＋C＝1012＋1＋(－1012)＝0

A＋C＋B＝1012＋(－1012)＋1＝1

2.確定性(definiteness)

3.有窮性(finiteness)

4.擁有足夠的情報1.2.1算法的基本概念算法是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法是一組嚴謹?shù)囟x運算順序的規(guī)則，1.2.2算法設(shè)計基本方法1.2.2算法設(shè)計基本方法1.列舉法根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的。因此，列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題，例如求解不定方程的問題。1.列舉法例設(shè)每只母雞值3元，每只公雞值2元，兩只小雞值1元。現(xiàn)要用100元錢買100只雞，設(shè)計買雞方案。

假設(shè)買母雞I只，公雞J只，小雞K只。例

FORI＝0TO100DOFORJ＝0TO100DOFORK＝0TO100DO{M＝I＋J＋KN＝3I＋2J＋0.5KIF((M＝100)and(N＝100))THENOUTPUTI，J，K}RETURN總循環(huán)次數(shù)為1013FORI＝0TO100DO

FORI＝0TO33DOFORJ＝0TO50－1.5IDO{K＝100－I－JIF(3I＋2J＋0.5K＝100)THENOUTPUTI，J，K}RETURN總循環(huán)次數(shù)為FORI＝0TO33DO

#include"stdio.h"main(){inti，j，k；

for(i＝0；i＜＝33；i＋＋)for(j＝0；j＜＝50－1.5*i；j＋＋){k＝100－i－j；

if(3*i＋2*j＋0.5*k＝＝100.0)printf("%5d%5d%5d\n"，i，j，k)；

}}#include"stdio.h"

運行結(jié)果如下：

2306852570820721115741410761757820080運行結(jié)果如下：2.歸納法通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。3.遞推從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。第1章南財數(shù)據(jù)智能化課件例例第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件4.遞歸將一個復(fù)雜的問題歸結(jié)為若干個較簡單的問題，然后將這些較簡單的每一個問題再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止。4.遞歸例編寫一個過程，對于輸入的參數(shù)n，依次打印輸出自然數(shù)1到n。

PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN#include"stdio.h"wrt(intn){intk；

for(k＝1；k＜＝n；k＋＋)printf("%d\n"，k)；

return；

}例

輸出自然數(shù)1到n的遞歸算法。

PROCEDUREWRT1(n)IF(n≠0)THEN{WRT1(n－1)OUTPUTn}RETURN#include"stdio.h"wrt1(intn){if(n!＝0){wrt1(n－1)；printf("%d\n"，n)；}return；

}輸出自然數(shù)1到n的遞歸算法。5.減半遞推技術(shù)所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變。所謂“遞推”，是指重復(fù)“減半”的過程。5.減半遞推技術(shù)第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件例二分法求方程實根的減半遞推過程：首先取給定區(qū)間的中點c＝(a＋b)/2。然后判斷f(c)是否為0。若f(c)＝0,則說明c即為所求的根，求解過程結(jié)束；如果f(c)≠0,則根據(jù)以下原則將原區(qū)間減半：若f(a)f(c)＜0，則取原區(qū)間的前半部分；若f(b)f(c)＜0，則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長度是否已經(jīng)很?。喝魘a－b|＜ε，則過程結(jié)束，取(a＋b)/2為根的近似值；若|a－b|≥ε，則重復(fù)上述的減半過程。例FUNCTIONROOT(a，b，eps，f)f0＝f(a)WHILE(|a－b|≥ε)DO{c＝(a＋b)/2；f1＝f(c)IF(f1＝0)THEN{ROOT＝c；RETURN}IF(f0*f1＞0)THENa＝cELSEb＝c}c＝(a＋b)/2；ROOT＝cRETURNFUNCTIONROOT(a，b，eps，f)#include"stdio.h”#include"math.h”doubleroot(a，b，eps，f)doublea，b，eps，(*f)()；{doublef0，f1，c；

f0＝(*f)(a)；

while(fabs(a－b)＞＝eps){c＝(a＋b)/2；f1＝(*f)(c)；

if(f1＝＝0)return(c)；

if(f0*f1＞0)a＝c；

elseb＝c；

}c＝(a＋b)/2；return(c)；}#include"stdio.h”6.回溯法通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探。6.回溯法例求解皇后問題。由n2個方塊排成n行n列的正方形稱為“n元棋盤”。如果兩個皇后位于棋盤上的同一行或同一列或同一對角線上，則稱它們?yōu)榛ハ喙簟，F(xiàn)要求找使n元棋盤上的n個皇后互不攻擊的所有布局。例假設(shè)棋盤上的每一行放置一個皇后，分別用自然數(shù)進行編號為1，2，…，n。首先定義一個長度為n的一維數(shù)組q，其中每一個元素q[i]（i＝1，2，…，n）隨時記錄第i行上的皇后所在的列號。初始時，先將各皇后放在各行的第1列。即數(shù)組q的初值為

q[i]＝1，i＝1，2，…，n第i行與第j行上的皇后在某一對角線上的條件為

|q[i]－q[j]|＝|i－j|而它們在同一列上的條件為

q[i]＝q[j]假設(shè)棋盤上的每一行放置一個皇后，分別用自然數(shù)進行編號回溯法的步驟如下：從第一行（即i＝1）開始進行以下過程：設(shè)前i－1行上的皇后已經(jīng)布局好，即它們均互不攻擊?，F(xiàn)在考慮安排第i行上的皇后的位置，使之與前i－1行上的皇后也都互不攻擊。為了實現(xiàn)這一目的，可以從第i行皇后的當前位置q[i]開始按如下規(guī)則向右進行搜索：回溯法的步驟如下：①若q[i]＝n＋1，將第i個皇后放在第1列（即置q[i]＝1），且回退一行，考慮重新安排第i－1行上的皇后與前i－2行上的皇后均互不攻擊的下一個位置。此時如果已退到第0行（實際沒有這一行），則過程結(jié)束。②若q[i]≤n，則需檢查第i行上的皇后與前i－1行的皇后是否互不攻擊。若有攻擊，則將第i行上的皇后右移一個位置（即置q[i]＝q[i]＋1），重新進行這個過程；若無攻擊，則考慮安排下一行上的皇后位置，即置i＝i＋1。③若當前安排好的皇后是在最后一行（即第n行），則說明已經(jīng)找到了n個皇后互不攻擊的一個布局，將這個布局輸出（即輸出q[i]，i＝1，2，…，n）。然后將第n行上的皇后右移一個位置（即置q[n]＝q[n]＋1），重新進行這個過程，以便尋找下一個布局。①若q[i]＝n＋1，將第i個皇后放在第1列（即置q[i]＝回溯法求解皇后問題。PROCEDUREQUEEN(n)定義長度為n的數(shù)組存儲空間q。FORi＝1TOnDOq[i]＝1i＝1loop:IF(q[i]≤n)THEN{k＝1WHILE((k＜i)and((q[k]－q[i])*(|q[k]－q[i]|－|k－i|))≠0)DOk＝k＋1IF(k＜i)THENq[i]＝q[i]＋1回溯法求解皇后問題。

ELSE{i＝i＋1IF(i＞n)THEN{OUTPUTq[i](i＝1，2，…，n)q[n]＝q[n]＋1i＝n}}}ELSEELSE{q[i]＝1i＝i－1IF(i＜1)THENRETURNq[i]＝q[i]＋1}GOTOloopRETURNELSE#include"stdio.h"#include"math.h"#include"stdlib.h"voidqueen(intn){inti，j，k，jt，*q；

q＝malloc(n*sizeof(int))；

for(i＝0；i＜n；i＋＋)q[i]＝0；

i＝0；jt＝1；

printf("\n")；

printf("%dqueenproblem\n"，n)；#include"stdio.h"while(jt＝＝1){if(q[i]＜n){k＝0；

while((k＜i)&&((q[k]－q[i])*(fabs(q[k]－q[i])－fabs(k－i)))!＝0)k＝k＋1；

if(k＜i)q[i]＝q[i]＋1；

else{i＝i＋1；

if(i＞n－1){for(j＝0；j＜n；j＋＋)printf("%5d"，q[j]＋1)；while(jt＝＝1)printf("\n")；

q[n－1]＝q[n－1]＋1；

i＝n－1；

}}}else{q[i]＝0；i＝i－1；

if(i＜0){printf("\n")；free(q)；return；}q[i]＝q[i]＋1；

}}}printf("\n")1.2.3算法的復(fù)雜度分析1.2.3算法的復(fù)雜度分析1.算法的時間復(fù)雜度

指執(zhí)行算法所需要的計算工作量

算法的工作量＝f(n)

1.算法的時間復(fù)雜度1.平均性態(tài)(AverageBehavior)1.平均性態(tài)(AverageBehavior)2.最壞情況復(fù)雜性

(Worst－CaseComplexity)2.最壞情況復(fù)雜性

(Worst－CaseCom例采用順序搜索法，在長度為n的一維數(shù)組中查找為x的元素。即從數(shù)組的第一個元素開始，逐個與被查值x進行比較?；具\算為x與數(shù)組元素的比較。例平均性態(tài)分析平均性態(tài)分析最壞情況分析

W(n)＝max{ti|1≤i≤n＋1}＝n最壞情況分析2.算法的空間復(fù)雜度

執(zhí)行算法所需要的內(nèi)存空間。

inplace

2.算法的空間復(fù)雜度

執(zhí)行算法所需要的內(nèi)存空計算機軟件技術(shù)基礎(chǔ)（第4版）王曉慶QQ:26445100Office:8671-8170Mobile:189-5199-5050Email:onermb@計算機軟件技術(shù)基礎(chǔ)（第4版）王曉慶第1章預(yù)備知識1.1集合1.2算法第1章預(yù)備知識1.1集合1.1集合1.1.1集合及其基本性質(zhì)1.1.2自然數(shù)集與數(shù)學歸納法1.1.3笛卡爾積1.1.4二元關(guān)系941.1集合1.1.1集合及其基本性質(zhì)31.1.1集合及其基本性質(zhì)

1.集合的基本概念所謂集合，是指若干個或無窮多個具有相同屬性的元（元素）的集體。通常，一個集合名稱用大寫字母表示，而集合中的某個元素用小寫字母表示。951.1.1集合及其基本性質(zhì)4965976987998一個集合，通常用以下兩種方法表示。

(1)列舉法用列舉法表示一個集合是將此集合中的元素全部列出來，或者列出若干項但能根據(jù)規(guī)律可知其所有的元素。例如100一個集合，通常用以下兩種方法表示。9大于1而小于100的所有整數(shù)的集合可以表示為

A＝{2，3，4，…，99}，有限集所有整數(shù)構(gòu)成的集合可以表示為

Z＝{0，±1，±2，±3，…，}，無限集空集表示為＝{}，空集101大于1而小于100的所有整數(shù)的集合可以表示為10(2)性質(zhì)敘述法用性質(zhì)敘述法表示一個集合是將集合中的元素所具有的屬性描述出來。例如：102(2)性質(zhì)敘述法11大于1而小于100的所有整數(shù)的集合可以表示為

A＝{a|1＜a＜100的所有整數(shù)}所有整數(shù)構(gòu)成的集合可以表示為

Z＝{z|z為一切整數(shù)}大于0而小于1的所有實數(shù)構(gòu)成的集合可以表示為

B＝{b|0＜b＜1的所有實數(shù)}所有實數(shù)構(gòu)成的集合可以表示為

R＝{r|r為一切實數(shù)}103大于1而小于100的所有整數(shù)的集合可以表示為12104132.集合的基本運算(1)兩個集合的并（union）設(shè)有兩個集合M和N，它們的并集記作M∪N，其定義如下：

即兩個集合M與N的并集是指M與N中的所有元素（去掉重復(fù)的元素）組成的集合。1052.集合的基本運算14(2)兩個集合的交（intersection）設(shè)有兩個集合M和N，它們的交集記作M∩N，其定義如下：

即兩個集合M與N的交集是指M與N中所有共同元素組成的集合。106(2)兩個集合的交（intersection）15兩個集合與的并、交均滿足交換律，即

M∪N＝N∪MM∩N＝N∩M107兩個集合與的并、交均滿足交換律，即16(3)兩個集合的差（difference）設(shè)有兩個集合M和N，M和N的差集記作M－N，其定義如下：

M－N＝{α|α∈M但α不屬于N}

兩個集合的差不滿足交換律，即

M－N≠N－M108(3)兩個集合的差（difference）17

例設(shè)集合

A＝{a，b，c，d，e}B＝{d，e，f，g，h}則

A∪B＝{a，b，c，d，e，f，g，h}A∩B＝{d，e}A－B＝{a，b，c}B－A＝{f，g，h}109例設(shè)集合18基本性質(zhì)：(1)結(jié)合律

(A∩B)∪C＝A∩(B∩C)(A∪B)∪C＝A∪(B∪C)(2)分配律

A∩(B∪C)＝(A∩B)∪(A∩C)A∪(B∩C)＝(A∪B)∩(A∪C)(3)(A－B)∪(B－A)＝(A∪B)－(A∩B)(4)B∩(A－B)＝Φ(A∩B)∪(A－B)＝A110基本性質(zhì)：193.映射1113.映射2011221113221142311524116251.1.2自然數(shù)集與數(shù)學歸納法1171.1.2自然數(shù)集與數(shù)學歸納法26由所有自然數(shù)所組成的集合

{1，2，3，…}稱為自然數(shù)集。自然數(shù)集是一個無限集。由自然數(shù)組成的集合均是自然數(shù)集的子集。自然數(shù)集的子集可以是有限集，也可以是無限集。118由所有自然數(shù)所組成的集合27與自然數(shù)集對等（即具有相等濃度）的集合稱為可列集（或可數(shù)集）。任一可列集中的元素排列時可標以正整數(shù)下標，即任意可列集均可寫成119與自然數(shù)集對等（即具有相等濃度）的集合稱為可列集（或可數(shù)集）定理：在自然數(shù)集的任一非空子集M中，必定有一個最小數(shù)。即在集合M中有不大于其它任意數(shù)的數(shù)。120定理：2912130定理：設(shè)M是由自然數(shù)形成的集合，如果它含有1，2，…，k，并且當它含有數(shù)n－1，n－2，…，n－k（n＞k）時，也含有數(shù)n，那么它含有所有的自然數(shù)，即M是自然數(shù)集。122定理：3112332為了證明一個命題對于所有的自然數(shù)是真，采用數(shù)學歸納法證明的步驟如下：(1)證明命題對于自然數(shù)1，2，…，k是真的；(2)假設(shè)命題對于自然數(shù)n－k，n－k＋1，…，n－1（n＞k）是真的（這一步稱為歸納假設(shè)）；(3)證明命題對于自然數(shù)n也是真的。124為了證明一個命題對于所有的自然數(shù)是真，33例證明下列命題：對于任意的自然數(shù)n，必存在一對非負整數(shù)(i，j)有

7＋n＝3i＋5j125例證明下列命題：34證明：(1)當n＝1時，有7＋1＝3＋5，即i＝1，j＝1。命題成立。當n＝2時，有7＋2＝3×3＋5×0，即即i＝3，j＝0。命題成立。當n＝3時，有7＋3＝3×0＋5×2，即即i＝0，j＝2。命題成立。(2)假設(shè)命題對于自然數(shù)n－1，n－2，n－3（n＞3）成立（歸納假設(shè)）。(3)考慮自然數(shù)n，有

7＋n＝[7＋(n－3)]＋3根據(jù)歸納假設(shè)，對于自然數(shù)n－3命題成立，設(shè)存在一對非負整數(shù)I，J有

7＋(n－3)＝3I＋5J則有

7＋n＝[7＋(n－3)]＋3＝3(I＋1)＋5J＝3i＋5j其中i＝I＋1，j＝J均為非負整數(shù)。即對于自然數(shù)n命題也成立。由此得出結(jié)論，對于所有的自然數(shù)n命題成立。126證明：351.1.3笛卡爾積1271.1.3笛卡爾積3612837129381.1.4二元關(guān)系1301.1.4二元關(guān)系39131401324113342134431354413645137461.2算法1.2.1算法的基本特征1.2.2算法設(shè)計基本方法1.2.3算法的復(fù)雜度分析1.2算法1.2.1算法的基本特征1.2.1算法的基本概念

算法是指解題方案的準確而完整的描述。

1.能行性(effectiveness)

A＝1012，B＝1，C＝－1012

A＋B＋C＝1012＋1＋(－1012)＝0

A＋C＋B＝1012＋(－1012)＋1＝1

2.確定性(definiteness)

3.有窮性(finiteness)

4.擁有足夠的情報1.2.1算法的基本概念算法是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法是一組嚴謹?shù)囟x運算順序的規(guī)則，1.2.2算法設(shè)計基本方法1.2.2算法設(shè)計基本方法1.列舉法根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的。因此，列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題，例如求解不定方程的問題。1.列舉法例設(shè)每只母雞值3元，每只公雞值2元，兩只小雞值1元?，F(xiàn)要用100元錢買100只雞，設(shè)計買雞方案。

假設(shè)買母雞I只，公雞J只，小雞K只。例

FORI＝0TO100DOFORJ＝0TO100DOFORK＝0TO100DO{M＝I＋J＋KN＝3I＋2J＋0.5KIF((M＝100)and(N＝100))THENOUTPUTI，J，K}RETURN總循環(huán)次數(shù)為1013FORI＝0TO100DO

FORI＝0TO33DOFORJ＝0TO50－1.5IDO{K＝100－I－JIF(3I＋2J＋0.5K＝100)THENOUTPUTI，J，K}RETURN總循環(huán)次數(shù)為FORI＝0TO33DO

#include"stdio.h"main(){inti，j，k；

for(i＝0；i＜＝33；i＋＋)for(j＝0；j＜＝50－1.5*i；j＋＋){k＝100－i－j；

if(3*i＋2*j＋0.5*k＝＝100.0)printf("%5d%5d%5d\n"，i，j，k)；

}}#include"stdio.h"

運行結(jié)果如下：

2306852570820721115741410761757820080運行結(jié)果如下：2.歸納法通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。3.遞推從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。第1章南財數(shù)據(jù)智能化課件例例第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件4.遞歸將一個復(fù)雜的問題歸結(jié)為若干個較簡單的問題，然后將這些較簡單的每一個問題再歸結(jié)為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止。4.遞歸例編寫一個過程，對于輸入的參數(shù)n，依次打印輸出自然數(shù)1到n。

PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN#include"stdio.h"wrt(intn){intk；

for(k＝1；k＜＝n；k＋＋)printf("%d\n"，k)；

return；

}例

輸出自然數(shù)1到n的遞歸算法。

PROCEDUREWRT1(n)IF(n≠0)THEN{WRT1(n－1)OUTPUTn}RETURN#include"stdio.h"wrt1(intn){if(n!＝0){wrt1(n－1)；printf("%d\n"，n)；}return；

}輸出自然數(shù)1到n的遞歸算法。5.減半遞推技術(shù)所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變。所謂“遞推”，是指重復(fù)“減半”的過程。5.減半遞推技術(shù)第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件第1章南財數(shù)據(jù)智能化課件例二分法求方程實根的減半遞推過程：首先取給定區(qū)間的中點c＝(a＋b)/2。然后判斷f(c)是否為0。若f(c)＝0,則說明c即為所求的根，求解過程結(jié)束；如果f(c)≠0,則根據(jù)以下原則將原區(qū)間減半：若f(a)f(c)＜0，則取原區(qū)間的前半部分；若f(b)f(c)＜0，則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長度是否已經(jīng)很?。喝魘a－b|＜ε，則過程結(jié)束，取(a＋b)/2為根的近似值；若|a－b|≥ε，則重復(fù)上述的減半過程。例FUNCTIONROOT(a，b，eps，f)f0＝f(a)WHILE(|a－b|≥ε)DO{c＝(a＋b)/2；f1＝f(c)IF(f1＝0)THEN{ROOT＝c；RETURN}IF(f0*f1＞0)THENa＝cELSEb＝c}c＝(a＋b)/2；ROOT＝cRETURNFUNCTIONROOT(a，b，eps，f)#include"stdio.h”#include"math.h”doubleroot(a，b，eps，f)doublea，b，eps，(*f)()；{doublef0，f1，c；

f0＝(*f)(a)；

while(fabs(a－b)＞＝eps){c＝(a＋b)/2；f1＝(*f)(c)；

if(f1＝＝0)return(c)；

if(f0*f1＞0)a＝c；

elseb＝c；

}c＝(a＋b)/2；return(c)；}#include"stdio.h”6.回溯法通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探。6.回溯法例求解皇后問題。由n2個方塊排成n行n列的正方形稱為“n元棋盤”。如果兩個皇后位于棋盤上的同一行或同一列或同一對角線上，則稱它們?yōu)榛ハ喙簟，F(xiàn)要求找使n元棋盤上的n個皇后互不攻擊的所有布局。例假設(shè)棋盤上的每一行放置一個皇后，分別用自然數(shù)進行編號為1，2，…，n。首先定義一個長度為n的一維數(shù)組q，其中每一個元素q[i]（i＝1，2，…，n）隨時記錄第i行上的皇后所在的列號。初始時，先將各皇后放在各行的第1列。即數(shù)組q的初值為

q[i]＝1，i＝1，2，…，n第i行與第j行上的皇后在某一對角線上的條件為

|q[i]－q[j]|＝|i－j|而它們在同一列上的條件為

q[i]＝q[j]假設(shè)棋盤上的每一行放置一個皇后，分別用自然數(shù)進行編號回溯法的步驟如下：從第一行（即i＝1）開始進行以下過程：設(shè)前i－1行上的皇后已經(jīng)布局好，即它們均互不攻擊。現(xiàn)在考慮安排第i行上的皇后的位置，使之與前i－1行上的皇后也都互不攻擊。為了實現(xiàn)這一目的，可以從第i行皇后的當前位置q[i]開始按如下規(guī)則向右進行搜索：回溯法的步驟如下：①若q[i]＝n＋1，將第i個皇后放在第1列（即置q[i]＝1），且回退一行，考慮重新安排第i－1行上的皇后與前i－2行上的皇后均互不攻擊的下一個位置。此時如果已退到第0行（實際沒有這一行），則過程結(jié)束。②若q[i]≤n，則需檢查第i行上的皇后與前i－1行的皇后是否互不攻擊。若有攻擊，則將第i行上的皇后右移一個位置（即置q[i]＝q[i]＋1），重新進行這個過程；若無攻擊，則考慮安排下一行上的皇后位置，即置i＝i＋1。③若當前安排好的皇后是在最后一行（即第n行），則說明已經(jīng)找到了n個皇后互不攻擊的一個布局，將這個布局輸出（即輸出q[i]，i＝1，2，…，n）。然后將第n行上的皇后右移一個位置（即置q[n]＝q[n]＋1），重新進行這個過程，以便尋找下一個布局。①若q[