专题十:算法分析与设计 1.常用的算法设计方法: 1.1 迭代法 1.2 穷举搜索法 1.3 递推法 1.4 递归法 1.5 贪婪法 1.6 分治法 1.7 动态规划法 1.8 回溯法 算法基础部分: 算法是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。 算法具有以下5个属性: 有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 确定性:算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性:一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入:一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。 输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系的量。 所以对应的算法设计的要求: 正确性:算法应满足具体问题的需求; 可读性:算法应该好读,以有利于读者对程序的理解; 健壮性:算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。 效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 1.1 迭代法: 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: (1)选一个方程的近似根,赋给变量x0; (2)将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; (3)当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i<n;i++) x[i]=初始近似根; do { for (i=0;i<n;i++) y[i]=x[i]; for (i=0;i<n;i++) x[i]=gi(X); for (delta=0.0,i=0;i<n;i++) if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i]); } while (delta>Epsilon); for (i=0;i<n;i++) printf(“变量x[%d]的近似根是 %f”,I,x[i]); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: (1)如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; (2)方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 1.2 穷举搜索法: 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。 要解决的问题只有有限种可能,在没有更好算法时总可以用穷举搜索的办法解决,即逐个的检查所有可能的情况。可以想象,情况较多时这种方法极为费时。实际上并不需要机械的检查每一种情况,常常是可以提前判断出某些情况不可能取到最优解,从而可以提前舍弃这些情况。这样也是隐含的检查了所有可能的情况,既减少了搜索量,又保证了不漏掉最优解。 【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形,这六个变量分别取[1,6]上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。 程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的整数,在它们互不相同的条件下,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽所有的组合后,程序就可得到全部可能的解。细节见下面的程序。 # include <stdio.h> void main() { int a,b,c,d,e,f; for (a=1;a<=6;a++) //a,b,c,d,e依次取不同的值 for (b=1;b<=6;b++) { if (b==a) continue; for (c=1;c<=6;c++) { if (c==a)||(c==b) continue; for (d=1;d<=6;d++) { if (d==a)||(d==b)||(d==c) continue; for (e=1;e<=6;e++) { if (e==a)||(e==b)||(e==c)||(e==d) continue; f=21-(a+b+c+d+e);//最后一个用减法算 if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) { printf(“%6d,a); printf(“%4d%4d”,b,f); printf(“%2d%4d%4d”,c,d,e); scanf(“%c”); } } } } } } 【算法分析与设计】在软件工程中扮演着至关重要的角色,它是解决问题的关键步骤,涉及到一系列技术,包括迭代法、穷举搜索法等。算法是一种精确的、有限的、确定的计算过程描述,它由一系列指令构成,用于解决特定问题。 **迭代法**是一种常见的算法设计方法,特别适用于求解方程或方程组的近似根。迭代法的基本思想是通过不断更新一个变量的值来逐步逼近问题的解。例如,当要解方程f(x)=0时,可以找到一个等价形式x=g(x),初始化一个近似根x0,然后不断用g(x1)更新x0,直到x0与x1的差的绝对值小于预定精度Epsilon。这个过程可以用C语言表示为一个循环结构。迭代法也适用于求解方程组,通过对每个变量迭代更新,直至所有变量的差值小于预设精度。在实际应用中,需要注意方程是否有解以及迭代公式和初始近似根的选择,以避免迭代失败或陷入无限循环。 **穷举搜索法**通常在问题的可能解集有限时使用,通过遍历所有可能的情况来寻找符合条件的解。尽管这种方法在解集庞大时效率低下,但在没有其他更优算法的情况下,穷举搜索仍然是一个可靠的解决方案。例如,对于一个六变量的排列问题,我们可以通过嵌套循环逐个尝试所有可能的整数组合,检查是否满足条件。在实际编程时,可以利用提前判断和剪枝策略来减少不必要的计算,提高效率。 在设计算法时,要确保其**正确性**,即算法能够正确地解决给定问题。同时,**可读性**也很重要,以便于其他人理解并维护代码。**健壮性**是指算法能处理异常和非法输入,不会因为错误的数据而导致不可预测的结果。此外,算法的**效率**和**存储量需求**也是评价算法优劣的重要指标,这通常与问题的规模和复杂度有关。 除了上述两种方法,还有其他的算法设计策略,如**递推法**、**递归法**、**贪婪法**、**分治法**、**动态规划法**和**回溯法**。递推法通过定义一个序列的后一项与前一项的关系来解决问题;递归法则是通过函数调用自身来解决子问题;贪婪法采取局部最优决策,期望达到全局最优;分治法将大问题分解为小问题来解决;动态规划则通过记忆化子问题的解,避免重复计算;回溯法则在搜索解空间树的过程中,通过回退撤销先前的决策,以找到满足条件的解。 算法分析与设计是软件工程中的核心技能,涉及多种方法和技术,要求开发者具备良好的逻辑思维和问题解决能力。掌握这些方法可以帮助我们编写出高效、准确且易于理解的代码,以应对各种复杂的计算问题。在准备计算机等级考试或软件设计师的复习中,深入理解并熟练运用这些算法设计原则至关重要。
剩余16页未读,继续阅读
- 粉丝: 31
- 资源: 62
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于javaweb的网上拍卖系统,采用Spring + SpringMvc+Mysql + Hibernate+ JSP技术
- polygon-mumbai
- Chrome代理 switchyOmega
- GVC-全球价值链参与地位指数,基于ICIO表,(Wang等 2017a)计算方法
- 易语言ADS指纹浏览器管理工具
- 易语言奇易模块5.3.6
- cad定制家具平面图工具-(FG)门板覆盖柜体
- asp.net 原生js代码及HTML实现多文件分片上传功能(自定义上传文件大小、文件上传类型)
- whl@pip install pyaudio ERROR: Failed building wheel for pyaudio
- Constantsfd密钥和权限集合.kt
评论0