枚舉:
背包問題:
枚舉策略：1)可能的方案：2N
2)對每一方案進行判斷.
枚舉法一般流程：
while(還有其他可能方案)
{ 按某種順序可難方案;
檢驗方案;
if(方案為解)
保存方案;
}
}
枚舉策略:
例：把所有排列枚舉出來 P6=6!.
Min:123456
Max:654321
a1a2a3a4a5a6=>?(下一排列)=>?
比如:312654的下和種情況=>314256
遞歸
遞歸算法通常具有這樣的特征：為求解規(guī)模為N的問題，設法將它分解成一些規(guī)模較小的問題，然后從這些較小問題的解能方便地構(gòu)造出題目所需的解。而這些規(guī)模較小的問題也采用同樣的方法分解成規(guī)模更小的問題，通過規(guī)模更小的問題構(gòu)造出規(guī)模校小的問題的解，如此不斷的反復分解和綜合，總能分解到最簡單的能直接得到解的情況。
因此,在解遞歸算法的題目時,要注意以下幾點:
1) 找到遞歸調(diào)用的結(jié)束條件或繼續(xù)遞歸調(diào)用條件.
2) 想方設法將處理對象的規(guī)?？s小或元素減少.
3) 由于遞歸調(diào)用可理解為并列同名函數(shù)的多次調(diào)用,而函數(shù)調(diào)用的原則是一層一層調(diào)用,一層一層返回.因此,還要注意理解調(diào)用返回后的下一個語句的作用.在一些簡單的遞歸算法中,往往不需要考慮遞調(diào)用返回后的語句處理.而在一些復雜的遞歸算法中,則需要考慮遞歸調(diào)用返回后的語句處理和進一步的遞歸調(diào)用.
4) 在讀遞歸程序或編寫遞歸程序時,必須要牢記遞歸函數(shù)的作用,這樣便于理解整個函數(shù)的功能和知道哪兒需要寫上遞歸調(diào)用語句.當然,在解遞歸算法的題目時,也需要分清遞歸函數(shù)中的內(nèi)部變量和外部變量.
表現(xiàn)形式:
●定義是遞歸的(二叉樹,二叉排序樹)
●存儲結(jié)構(gòu)是遞歸的(二叉樹,鏈表,數(shù)組)
●由前兩種形式得出的算法是遞歸的
一般流程: function(variable list(規(guī)模為N))
{ if(規(guī)模小,解已知) return 解;
else {
把問題分成若干個部分;
某些部分可直接得到解;
而另一部分(規(guī)模為N-1)的解遞歸得到;
}
}
例1：求一個鏈表里的元素.
大家有沒想過這個問題用遞歸來做呢?
非遞歸方法大家應該都會哦?
Max(nodetype *h) {
nodetype *p;
nodetype *q; //存放含值的結(jié)點
Int max=0;
P=h;
While(p!=NULL){
if (maxdata) {
max=p->data;
q=p;
}
p=p->next;
}
return q;
}
下面真經(jīng)來了,嘻嘻嘻~~~
*max(nodetype *h) {
nodetype *temp;
temp=max(h->next);
if(h->data>temp->data)
return h;
else
return temp;
}
大家有空想想下面這個算法：求鏈表所有數(shù)據(jù)的平均值(我也沒試過)，不許偷懶，用遞歸試試哦!
遞歸程序員考試題目類型：1)就是鏈表的某些操作(比如上面的求平均值)
2)二叉樹(遍歷等)
背包問題:
枚舉策略：1)可能的方案：2N
2)對每一方案進行判斷.
枚舉法一般流程：
while(還有其他可能方案)
{ 按某種順序可難方案;
檢驗方案;
if(方案為解)
保存方案;
}
}
枚舉策略:
例：把所有排列枚舉出來 P6=6!.
Min:123456
Max:654321
a1a2a3a4a5a6=>?(下一排列)=>?
比如:312654的下和種情況=>314256
遞歸
遞歸算法通常具有這樣的特征：為求解規(guī)模為N的問題，設法將它分解成一些規(guī)模較小的問題，然后從這些較小問題的解能方便地構(gòu)造出題目所需的解。而這些規(guī)模較小的問題也采用同樣的方法分解成規(guī)模更小的問題，通過規(guī)模更小的問題構(gòu)造出規(guī)模校小的問題的解，如此不斷的反復分解和綜合，總能分解到最簡單的能直接得到解的情況。
因此,在解遞歸算法的題目時,要注意以下幾點:
1) 找到遞歸調(diào)用的結(jié)束條件或繼續(xù)遞歸調(diào)用條件.
2) 想方設法將處理對象的規(guī)?？s小或元素減少.
3) 由于遞歸調(diào)用可理解為并列同名函數(shù)的多次調(diào)用,而函數(shù)調(diào)用的原則是一層一層調(diào)用,一層一層返回.因此,還要注意理解調(diào)用返回后的下一個語句的作用.在一些簡單的遞歸算法中,往往不需要考慮遞調(diào)用返回后的語句處理.而在一些復雜的遞歸算法中,則需要考慮遞歸調(diào)用返回后的語句處理和進一步的遞歸調(diào)用.
4) 在讀遞歸程序或編寫遞歸程序時,必須要牢記遞歸函數(shù)的作用,這樣便于理解整個函數(shù)的功能和知道哪兒需要寫上遞歸調(diào)用語句.當然,在解遞歸算法的題目時,也需要分清遞歸函數(shù)中的內(nèi)部變量和外部變量.
表現(xiàn)形式:
●定義是遞歸的(二叉樹,二叉排序樹)
●存儲結(jié)構(gòu)是遞歸的(二叉樹,鏈表,數(shù)組)
●由前兩種形式得出的算法是遞歸的
一般流程: function(variable list(規(guī)模為N))
{ if(規(guī)模小,解已知) return 解;
else {
把問題分成若干個部分;
某些部分可直接得到解;
而另一部分(規(guī)模為N-1)的解遞歸得到;
}
}
例1：求一個鏈表里的元素.
大家有沒想過這個問題用遞歸來做呢?
非遞歸方法大家應該都會哦?
Max(nodetype *h) {
nodetype *p;
nodetype *q; //存放含值的結(jié)點
Int max=0;
P=h;
While(p!=NULL){
if (max
max=p->data;
q=p;
}
p=p->next;
}
return q;
}
下面真經(jīng)來了,嘻嘻嘻~~~
*max(nodetype *h) {
nodetype *temp;
temp=max(h->next);
if(h->data>temp->data)
return h;
else
return temp;
}
大家有空想想下面這個算法：求鏈表所有數(shù)據(jù)的平均值(我也沒試過)，不許偷懶，用遞歸試試哦!
遞歸程序員考試題目類型：1)就是鏈表的某些操作(比如上面的求平均值)
2)二叉樹(遍歷等)