算法与数据结构综合应用——典型竞赛试题分析
一、数值计算问题：
1、    打印所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数字本身，例
2、    一个数如果恰好等于它的因子之和，这个数就称为"完数”。例如：6的因子为1、2、3,而6 = 1 + 2 + 3,因此6是''完数”。编程序出1000以内的所有完数。
3、    有一分数序列：求出这个数列的前20项的和。(32. 660259)
4、    求之值，其中a是一个数字。例如：(当n=5时，n由键盘输入。
5、    已知四位数3025有一个待殊性质：它的前两位数字30和后两位数字25的和是55,而55的平方刚好等 于该数(552=3025)。试编一程序打印具有这种性质的所有四位数。
分析：从32至99之间的数的平方是四位数，满足题目条件的数必须在这些四位数之内选择。分别把它们 按前两位数后两位数进行分离，验证分离后的两个两位数之和的平方是否等于分离
前的那个四位数，若等 于即打印输出，否则放弃。
6、    求两个自然数，其和是667,最小公倍数与最大公约数之比是120： lo (例如：115, 552)
迭代法
例题：
用二分法求方程在区间(0,3)之间的一个解。
算法提示：二分法是用计算机求解多项式方程的一中常用方法。基本思想是：，如果和的符号相反，那么 在(xl, x2)之间一定存在一个数使f (x) =0即方程的一个解。取xl, x2的中点r,如果f (r)与f (xl)异号， 解肯定在(xl.r)之间，否则解在(r,x2)之间，重复直到|f(r)|〈eO, e0是一个很小的数,通过这种方法能 够求出，方程f(x)=O的一个近似解r,误差在e0内。
穷举搜索法
穷举法也叫枚举法，它的基本思想是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情 况逐一验证，直到全部情况验证完。若某个情况经验证符合题目的全部条件，
则为本题的一个答案。若全部 情况经验证后都不符合题目的全部条件，则本题无答案。
用穷举法解题时，答案所在的范围总是要求是有限的，怎样才能使我们不重复的、一个不漏、一个不增的 逐个列举答案所在范围的所有情况，就是本节所讲的“列举方法”。
列举方法按答案的数据类型，常用的有下面三种。
顺序列举：顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变 化顺序去列举。
排列列举：有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排列，称为排列列举。
组合列举：(参考组合数学知识)当答案的数据形式为一些元素的组合时，往往需要用组合列举。从几个 不同的元素中任取m(mn)个元素组成的一组，就叫做从n个元素取m个元素的一个组合。组合是无序的， 如：123, 132, 321, 312, 213, 231是同一个组合(但是6个不同的排列)。
例题：
【问题提出】
出n个自然数(1, 2, 3, 4, ...n)屮r个数的组合。例如n=3, r=2,所有的组合为：12,13,23； n = 5, r = 3,所有的情况为：123, 124, 125, 134, 135, 145, 234, 235, 245, 345。
【算法】
当r = 3时用3重循环实现。
for 1=5 tol
for j=5 tol
for k=5 to 1
if IOj AND I!=k AND jOK AND I>j AND j>k
print I,j,k
练习：
1、求出具有下列两个性质的最小自然数n：
(1)、n是个6位数
(2)、若将n的各位数移到其余各位之前，所得的新数是n的4倍。
递推法：
例题：
运动会连续开了 n天，一共发了 m枚奖章，第一天发1枚并剩下(m-1)枚的1/7,第二天发2枚并剩下 的1/7,以后每天按规律发放奖章，在最后一天即第n天发剩下的n枚奖章。问运动会一共开了多少天？ 一共发了几枚奖章？
贪心算法
一、    算法思想
贪心法的基本思路：
数据结构与算法分析答案—
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某 一步不能再继续前进时，算法停止。
该算法存在问题：
1.不能保证求得的最后解是最佳的；
2.不能用来求最大或最小解问题；
3.只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while能朝给定总13标前进一步do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、    例题分析
1、［背包问题］有一个背包，背包容量是M=150o有7个物品，物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品：A B C D E F G
重量：35 30 60 50 40 10 25
价值：10 40 30 50 35 40 30
分析：
目标函数：工pi最大
约束条件是装入的物品总重量不超过背包容量：Swi<=M( M=150)
(1)根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优?
(2)每次挑选所占空间最小的物品装入是否能得到最优解？
(3)每次选取单位容量价值最大的物品，成为解本题的策略。
简单背包问题
[问题描述]背包是一个简单的递归问题，要求是从n件物品中抽取几件,使之质量一定•该程序只求一组 解.
输入:[KEYBOARD]输出:[SCREEN]
10
123456789 12
9
5
12 3 4 5
45
23 4
NO ANSWER!
[问题分析]使用递归算法完成.每件物品只有放入，不放入两种情况. program knapProg;
cons t
m 二 5;
var
item: array[1. . m] of integer;
i,w: integer;
function knap(a, b: integer): boolean;
begin
if item[a] = b then
begin
knap := true; write(item[a]: 8);
exit;
end;
if ((item[a] > b) and (a = m)) then
begin
knap := false;
exit;
end;
if knap (a + 1, b - item[a]) then
begin
knap := true; write(item[a]: 8);
exit;
end;
if not knap(a + 1, b) then knap :二 false;
end;
begin
writeln('Please input item weights:');
for i :二 1 to m do
read(item[i]);
writeln('Total weight:');
readln(w);
writeln;
if not knap(1, w) then writein C NO ANSWER!!');
readln;
end.
2、    [单源最短路径]一个有向图G,它的每条边都有一个非负的权值c[i,j],"路径长度"就是所经过的所 有边的权值之和。对于源点需要出从源点出发到达其他所有结点的最短路径。E. Dijkstra发明的贪婪算 法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最 短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短 的目的顶点。
设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于 集合S。初始时S中只含源。
设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径，并把这 个特殊路径记录下来(例如程序中的dist[i, j])。
每次从V-S选出具有最短特殊路径长度的顶点u,将u添加到S中，同时对特殊路径长度进行必要的 修改。一旦V=S,就得到从源到其他所有顶点的最短路径，也就得到问题的解。
3、    [机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有 下表：
任务 _a_b_c_d_e_f_g
开始(si)-O-3-4-9-7-1-6 完成(fi)-2-7-7-ll-10-5-8
在可行分配屮每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方 案。请就本题给出的条件，求出最优分配。
三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻一条耗油量较少的飞行路线。5个城市的联系网络如 图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定 从城市i到j和城市j到i之间的耗油量是相同的。
分析：
1.运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2.图解：若从1出发，有图：
总耗油量=14 1-2-5-3-4T
但若路线改为:1-5-3-4-2-1,则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3.改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1.数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array [1.. 5, 1. . 5] of integer= ((0, 1, 2, 7, 5),
(1,0, 4, 4, 3),
(2,4, 0, 1,2),
(7,4, 1,0, 3));
2.贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i : = 1 to n-1 do {nT 个城市}
begin
s:=UV至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3.主过程：实现改善方案
begin
for i:=l to n do
begin
costl: =maxint; ｛初始化｝
调用贪心过程，返回本次搜索耗油量cost；
if cost<costl then 替换；
end;
输出；
end.
例：设计一个程序，把一个真分数表示为埃及分数之和的形式。
问题分析：
所谓埃及分数，是指分子为1的形式。古代埃及有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干 个分子为1的分数之和的形式。如，7/8=1/2+1/3+1/24。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。