2010年下半年初级软考辅导:程序员数据结构笔记（五） _计算机_软件水平考试_复习指导

回溯法:
　　回溯跟递归都是程序员考试里常出现的问题，大家必须掌握!
　　回溯法的有关概念:
　　1)解答树:叶子结点可能是解，对结点进行后序遍历.
　　2)搜索与回溯
　　五个数中任选三个的解答树:
　　ROOT虚根
　　//““
　　12345
　　/“/“/“
　　2345345455
　　/“/“/“
　　3454554555
　　回溯算法实现中的技巧:栈
　　要搞清回溯算法，先举一个来说明栈在非递归中所起的作用。
　　A过程：push->push->push->push栈内结果:ABDE
　　/“popABD
　　BCpopAB
　　/“popA
　　DF..
　　//“..
　　EGH..
　　/..
　　I最后结果：EDBGFIHAC
　　简单算法:
　　…
　　if//树不空
　　while)//栈非空，出栈
　　}
　　}//这就是传说中的回溯，嘻嘻……没吓着你吧
　　5选3问题算法:
　　思想:进栈:搜索
　　出栈:回溯
　　边建树边遍历
　　基本流程:
　　太复杂了，再说我不太喜欢用WORD画图（有损形象），以后再整理!
　　程序:n=5;r=3
　　……
　　init//初始化栈
　　push//根进栈
　　while&&//有孩子
　　push;//孩子入栈
　　while)
　　背包问题:TW=20，w=
　　解的条件:1)该解答树的叶子结点
　　2)重量最大
　　解答树如下：ROOT
　　/“
　　610758
　　/“/“/“
　　10758758588
　　588
　　程序:
　　temp_w表示栈中重量和
　　…
　　init;//初始化栈
　　i=0;
　　While
　　i++;
　　IfReturn-1;//无解
　　Else
　　max_w=0;
　　while)
　　}
　　请大家思考:四色地图问题，比如给中国地图涂色，有四种颜色，每个省选一种颜色，相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的"大国"哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。
　　贪婪法:
　　不求最优解，速度快
　　例:哈夫曼树，最小生成树
　　装箱问题:
　　有n个物品，重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内，需要几个集装箱?
　　思想1:对n个物品排序
　　拿出第1个集装箱，从大到小判断能不能放。
　　2…
　　3…
　　.…
　　.…
　　思想2:对n个物品排序
　　用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量，则装进去，反之则取一只新箱子。
　　程序:
　　count=1;qw[0]=TW;
　　for
　　}
　　用贪婪法解背包问题:
　　n个物品，重量:w[n]价值v[i]
　　背包限重TW，设计一个取法使得总价值最大.
　　方法:
　　0123…n-1
　　w0w1w2w3…wn-1
　　v0v1v2v3…vn-1
　　v0/w0…v/w求出各个物品的"性价比"
　　先按性价比从高到低进行排序
　　已知:w[n]，v[n]，TW
　　程序:
　　…
　　for
　　d[i]=v[i]/w[i];//求性价比
　　for
　　}
　　e[i]=x;
　　d[x]=0;
　　}
　　temp_w=0;temp_v=0;
　　for
　　分治法:
　　思想:把规模为n的问题进行分解，分解成几个小规模的问题.然后在得到小规模问题的解的基础上，通过某种方法组合成该问题的解.
　　例:数轴上有n个点x[n]，求距离最小的两个点.
　　分:任取一点，可以把x[i]这n个点分成两个部分
　　小的部分分点大的部分
　　_._.__.__.____.___._._.__._.__._______._.__._._.__.___._____._
　　治:解=min