枚举:
背包问题:
枚举策略：1)可能的方案：2N
2)对每一方案进行判断.
枚举法一般流程：
while(还有其他可能方案)
{ 按某种顺序可难方案;
检验方案;
if(方案为解)
保存方案;
}
}
枚举策略:
例：把所有排列枚举出来 P6=6!.
Min:123456
Max:654321
a1a2a3a4a5a6=>?(下一排列)=>?
比如:312654的下和种情况=>314256
递归
递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。
因此,在解递归算法的题目时,要注意以下几点:
1) 找到递归调用的结束条件或继续递归调用条件.
2) 想方设法将处理对象的规模缩小或元素减少.
3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用.
4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量.
表现形式:
●定义是递归的(二叉树,二叉排序树)
●存储结构是递归的(二叉树,链表,数组)
●由前两种形式得出的算法是递归的
一般流程: function(variable list(规模为N))
{ if(规模小,解已知) return 解;
else {
把问题分成若干个部分;
某些部分可直接得到解;
而另一部分(规模为N-1)的解递归得到;
}
}
例1：求一个链表里的最大元素.
大家有没想过这个问题用递归来做呢?
非递归方法大家应该都会哦?
Max(nodetype *h) {
nodetype *p;
nodetype *q; //存放含最大值的结点
Int max=0;
P=h;
While(p!=NULL){
if (max<p->data) {
max=p->data;
q=p;
}
p=p->next;
}
return q;
}
下面真经来了,嘻嘻嘻~~~
*max(nodetype *h) {
nodetype *temp;
temp=max(h->next);
if(h->data>temp->data)
return h;
else
return temp;
}
大家有空想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!
递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)
2)二叉树(遍历等)
|
