没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
常用算法设计方法
要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序 。
计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象
程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。
算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确
地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终
止,或终止于给出问题的解,或终止于指出问题对此输入数据无解。
通常求解一个问题可能会有多种算法可供选择,选择的主要标准是算法的正确性和可靠性,简单性和易理解性 。
其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回
溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,
用递归描述算法。
一、迭代法
迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 ,用某种数学方法导出等价
的形式 ,然后按以下步骤执行:
() 选一个方程的近似根,赋给变量 ;
() 将 的值保存于变量 ,然后计算 ,并将结果存于变量 ;
() 当 与 的差的绝对值还小于指定的精度要求时,重复步骤()的计算。
若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的 就认为是方程的根。上述算法
用 程序的形式表示为:
【算法】迭代法求方程的根
初始近似根;
;
; 按特定的方程计算新的近似根
;
! "#方程的近似根是$% &,;
迭代算法也常用于求方程组的根,令
'(,,…, )
设方程组为:
'(,,…,
则求方程组根的迭代算法可描述如下:
【算法】迭代法求方程组的根
!)* )++
,-初始近似根)
!)* )++
.,-,-)
!)* )++
,-')
!"/0)* )++
- 1 -
.,-,-"".,-,-;
" ;
!)* )++
! "#变量 ,$-的近似根是 $&,(,,-;
! "#% &;
具体使用迭代法求根时应注意以下两种可能发生的情况:
() 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先
考察方程是否有解,并在程序中对迭代的次数给予限制;
() 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
二、穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作
为问题的解。
【问题】 将 1、2、、3、、4 这六个变量排成如图所示的三角形,这六个变量分别取,,5-上的整数,且均
不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。
程序引入变量 、、6、、、,并让它们分别顺序取 至 5 的证书,在它们互不相同的条件下,测试由它们排
成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量
取尽所有的组合后,程序就可得到全部可能的解。细节见下面的程序。
【程序 】
7 68*"/
9:
"006000)
!)*5)++
!)*5)++
6 " 8)
!6)6*5)6++
6;;66 " 8)
!)*5)++
;;;;66 " 8)
!)*5)++
;;;;6;;6 " 8)
++6++)
++66++<<++6++
! "#$50)
! "#$=$=&00)
! "#$$=$=&0600)
6 #$6&)
按穷举法编写的程序通常不能适应变化的情况。如问题改成有 > 个变量排成三角形,每条边有 = 个变量的情况,程
- 2 -
序的循环重数就要相应改变。
对一组数穷尽所有排列,还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组
整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每
个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整
来实现。倘若当前排列为 ,,=,5,?,,并令其对应的长整数为 =5?。要寻找比长整数 =5? 更大的
排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的
5 比它的前一位数字 = 大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调
整得太大,如本例中将数字 5 与数字 = 交换得到的排列 5=? 就不是排列 =5? 的下一个排列。为了得到排
列 =5? 的下一个排列,应从已经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如
数字 ? ,与数字 = 交换。该数字也是从后向前考察过程中第一个比 = 大的数字。? 与 = 交换后,得到排列
?5=。在前面数字 ,,? 固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的
排 列 顺 序 颠 倒 , 如 将 数 字 5 , = , 的 排 列 顺 序 颠 倒 , 得 到 排 列 , , ? , , = , 5 , 这 才 是 排 列
,,=,5,?, 的下一个排列。按以上想法编写的程序如下。
【程序 】
7 68*"/
7@ A(3BC
7@ DCEFG
7@ H1I(12DA5
"102003004)
"",-<10<20<0<30<0<4)
",A(3BC-,DCEFG-<10<20<0<0<30<0<0<40<1)
"B"",A(3BC-)
:
"0J0"0K8)
!J)J*H1I(12DA)J++
",J-J+)
!)*A(3BC)++
!"J)J*DCEFG)J++
"+,-,J-)
B"",-")
!K80)K8<<*A(3BC)++
B"",-LB"",+-K8)
K8
!)*H1I(12DA)++
! "#$=&0",-)
! "#% &)
6 #$6&)
!JH1I(12DA)J)J
",J-",J-!M)
J!M)
!H1I(12DA)J)
",-",-!M)
- 3 -
"",J-)",J-",-)",-")
!H1I(12DA)J)0J++
"",J-)",J-",-)",-")
从上述问题解决的方法中,最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。
【问题】 背包问题
问题描述:有不同价值、不同重量的物品 件,求从这 件物品中选取一部分物品的选择方案,使选中物品的总重
量不超过指定的限制重量,但选中物品的价值之和最大。
设 个物品的重量和价值分别存储于数组 ,-和 9,-中,限制重量为 "。考虑一个 元组(,,…,
),其中 表示第 个物品没有选取,而 则表示第 个物品被选取。显然这个 元组等价于一个选择方
案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的 元组,就可以得
到问题的解。
显然,每个分量取值为 或 的 元组的个数共为 个。而每个 元组其实对应了一个长度为 的二进制数,且
这些二进制数的取值范围为 ~ 。因此,如果把 ~ 分别转化为相应的二进制数,则可以得到我们所需
要的 个 元组。
【算法】
:9)
!)* )++
2,// -)
把 转化为二进制数,存储于数组 2 中)
":B)
":B9)
!J)J* )J++
2,J-
":B":B+,J-)
":B9":B9+9,J-)
":B*"<<":B9:9
:9":B9)
保存该 2 数组;
三、递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 C 的解,当 C 时,解
或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为 的
解后,由问题的递推性质,能从已求得的规模为 ,,…, 的一系列解,构造出问题规模为 ( 的解。这样,程
序可从 或 出发,重复地,由已知至 规模的解,通过递推,获得规模为 的解,直至得到规模为 C 的解。
【问题】 阶乘计算
问题描述:编写程序,对给定的 ( N),计算并输出 M 的阶乘 M!( M,,…, )的全部有效数字。
由于要求的整数可能大大超出一般整数的位数,程序用一维数组存储长整数,存储长整数数组的每个元素只存储长
- 4 -
整数的一位数字。如有 : 位成整数 C 用数组 ,-存储:
C,:-O:+,:-O:+P+,-O+,-O
并用 ,-存储长整数 C 的位数 :,即 ,-:。按上述约定,数组的每个元素存储 M 的阶乘 M!的一位数字,并从
低位到高位依次存于数组的第二个元素、第三个元素……。例如,?!,在数组中的存储形式为:
PP
首元素 表示长整数是一个 位数,接着是低位到高位依次是 、、,表示成整数 。
计算阶乘 M!可采用对已求得的阶乘M!连续累加 M 次后求得。例如,已知 =!=,计算 ?!,可对原来
的 = 累加 = 次 = 后得到 。细节见以下程序。
7 68*"/
7 68*:6/
7@ Q1'C
9 " ",-0 "M
"0:,-00J0!06!!.)
":6R ":+)
!)*:)++,-,-)
!J)J*M)J++
!6!!.0)*:)++
!*,-S,-+,-T,-+6!!.)
,-!$)
6!!.!)
6!!.,++:-6!!.)
!)
,-:)
9!" "0 "M
")
! "#$=!&0M)
!,-))
! "#$&0,-)
! "#% % &)
9:
",Q1'C-0 0M)
! "# "!" 8:! T#)
6 #$&0< )
,-)
,-)
!"0)
!M)M* )M++
"0M)
!"0M)
- 5 -
剩余33页未读,继续阅读
资源评论
liu10062007
- 粉丝: 2
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于 Java的班级管理系统课程设计
- 深入探索Suno AI:教程、元标签与案例分析.pdf
- 超市会员积分管理系统主要用于实现了企业管理数据统计等
- 基于 Java的班级管理系统
- MyBatis 动态 SQL:灵活而强大的查询构建器.pdf
- com.accordion.prettyo.apk
- 毕业设计:基于SSM的mysql-ssm软件bug管理系统(源码 + 数据库 + 说明文档)
- MTSQL8.0.35windows(64bit)-mysql-installer-community-8.0.35.0
- 人工智能引领音乐创作新时代之Suno AI
- Public-bicycle-usage-forecast-master.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功