《算法设计与分析期末资料总结.doc》由会员分享，可在线阅读，更多相关《算法设计与分析期末资料总结.doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制构造3、数据构造算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后完毕，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口与一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的根本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合
2、。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；强健性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反响，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法 根本思想：迭代法也称“辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法。解题步骤：1、确定迭代模型。根据问题描述，分
3、析得出前一个或几个值与其下一个值的迭代关系数学模型。2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量3、对迭代过程进展控制。确定在什么时候完毕迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来完毕迭代过程的条件。编写计算斐波那契Fibonacci数列的第n项函数fibn。写成递归函数有：int f
4、ib(int n) if (n=0) return 0;if (n=1) return 1;if (n1) return fib(n-1)+fib(n-2);一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开场，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？第 7 页Main()int I,a=1,b=1;Print(a,b);For(i=1;i=10;i+)C=a+b;Print(c);A=b;B=c;分而治之法1、根本思想 将一个难以直接解决的大问题，分割成一些规模较小的一样问题，以便各个击破，分而治之。 分治法
5、所能解决的问题一般具有以下几个特征： 1该问题的规模缩小到一定的程度就可以容易地解决； 2该问题可以分解为假设干个规模较小的一样问题，即该问题具有最优子构造性质； 3利用该问题分解出的子问题的解可以合并为该问题的解； 4该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 3、分治法的根本步骤 1分解：将原问题分解为假设干个规模较小，相互独立，与原问题形式一样的子问题； 2解决：假设子问题规模较小而容易被解决那么直接解，否那么递归地解各个子问题； 3合并：将各个子问题的解合并为原问题的解。贪婪法根本思想：以逐步的局部最优，到达最终的全局最优。无后效性【问题】 背包问题 问
6、题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一局部物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之与最大。 #includevoid main()int m,n,i,j,w50,p50,pl50,b50,s=0,max;printf(输入背包容量m,物品种类n :);scanf(%d %d,&m,&n);for(i=1;i=n;i=i+1)printf(输入物品的重量W与价值P :);scanf(%d %d,&wi,&pi);pli=pi;s=s+wi;if(s=m)printf(whole choosen);/return;for(i=1;i=n;i
7、=i+1)max=1;for(j=2;jplmax/wmax)max=j;plmax=0;bi=max;for(i=1,s=0;sm & i=n;i=i+1)s=s+wbi;if(s!=m)wbi-1=m-wbi-1;for(j=1;j=i-1;j=j+1)printf(choose weight %dn,wbj);动态规划根本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保存那些有可能到达最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。
8、根本步骤1划分阶段：按照问题的时间或空间特征，把问题分为假设干个阶段。注意这假设干个阶段一定要是有序的或者是可排序的即无后向性，否那么问题就无法用动态规划求解。 2选择状态：将问题开展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 3确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策与状态转移有着天然的联系，状态转移就是根据上一阶段的状态与决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 回溯法根本思想：按照深度优先策略，从根结点出发搜索解空间
9、。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。如果满足进入该子树，继续按深度优先的策略搜索。否那么，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法根本步骤：1、 确定问题的解空间：应用回溯法时，首先应明确定义问题的解的空间。问题的解空间应至少包含问题的一个解。2、 确定结点的扩展规那么3、 搜索解空间：从开场结点出发，以深度优先的方式搜索整个解空间。【问题】 n皇后问题 分支限界法根本思想： 分支限界法是由“分支与“限界两局部组成。“分支策略表达在对问题空间是按广度优先的策略进展搜索“限界策略是为了加速搜索速度面采用启发信息剪枝策略。可能会让画出“子集树斩图235页例题及图好好看一下。