算法与数据结构综合应用——典型竞赛试题分析

《算法与数据结构综合应用——典型竞赛试题分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法与数据结构综合应用——典型竞赛试题分析算法与数据结构综合应用--典型竞赛试题分析一、数值计算问题：1、打印所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数字本身，例2、一个数如果恰好等于它的因子之和，这个数就称为"完数"。例如：6的因子为1、2、3，而6＝1＋2＋3，因此6是"完数"。编程序找出1000以内的所有完数。3、有一分数序列：求出这个数列的前20项的和。（32.660259）4、求之值，其中a是一个数字。例如：（当n=5时），n由键盘输入。5、已知四位数3025有一个

2、待殊性质:它的前两位数字30和后两位数字25的和是55,而55的平方刚好等于该数(552=3025)。试编一程序打印具有这种性质的所有四位数。分析：从32至99之间的数的平方是四位数，满足题目条件的数必须在这些四位数之内选择。分别把它们按前两位数后两位数进行分离,验证分离后的两个两位数之和的平方是否等于分离前的那个四位数,若等于即打印输出,否则放弃。6、求两个自然数，其和是667，最小公倍数与最大公约数之比是120：1。（例如：115，552）迭代法例题：用二分法求方程在区间（0,3）之间的一个解。算法提示：二分法是用计算机求解多项

3、式方程的一中常用方法。基本思想是：,如果和的符号相反，那么在(x1,x2)之间一定存在一个数使f(x)=0即方程的一个解。取x1,x2的中点r，如果f(r)与f(x1)异号，解肯定在(x1,r)之间，否则解在(r,x2)之间，重复直到

4、f(r)

5、

6、情况经验证后都不符合题目的全部条件,则本题无答案。用穷举法解题时，答案所在的范围总是要求是有限的，怎样才能使我们不重复的、一个不漏、一个不增的逐个列举答案所在范围的所有情况，就是本节所讲的"列举方法"。列举方法按答案的数据类型,常用的有下面三种。顺序列举：顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数,可以按自然数的变化顺序去列举。排列列举：有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排列,称为排列列举。组合列举：（参考组合数学知识）当答案的数据形式为一些元素的组合时，往往需要用组合列举。从几个不同

7、的元素中任取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重循环实现。forI=5to1forj=5to1fork=5to1ifI<>jANDI!=kANDj

8、<>KANDI>jANDj>kprintI,j,k练习：1、求出具有下列两个性质的最小自然数n：（1）、n是个6位数（2）、若将n的各位数移到其余各位之前，所得的新数是n的4倍。递推法:例题：运动会连续开了n天，一共发了m枚奖章，第一天发1枚并剩下（m－1）枚的1/7，第二天发2枚并剩下的1/7，以后每天按规律发放奖章，在最后一天即第n天发剩下的n枚奖章。问运动会一共开了多少天？一共发了几枚奖章？贪心算法一、算法思想贪心法的基本思路：--从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不

9、能再继续前进时，算法停止。该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do　　求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；二、例题分析1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品：ABCDEFG重量：35306050401025价值：10403050354030分

10、析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150)（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占空间最小的物品装入是否能得到最优解？（3）每次选取