没有合适的资源?快使用搜索试试~ 我知道了~
计算机算法总结.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 125 浏览量
2021-10-11
17:20:54
上传
评论
收藏 945KB PDF 举报
温馨提示
试读
11页
计算机技术
资源推荐
资源详情
资源评论
算法总结
1.穷举法
穷举法,又称暴力算法,即列举问题解空间所有可能情况,并逐个测试,从而找出符合
问题条件的解。这份通常是一种费时算法,人工手动求解困难,但计算机的出现使得穷举法
有了用武之地。例如:密码破译通常用的是穷举法,即将密码进行逐个推算直到找到真正的
密码为止。理论上讲,穷举法可以破解任何一种密码,但对于一个长度为n 位的密码,其可
能的密码有 2^n 种。可见,当 n 较大时穷举法将成为一个 NP 难度问题。
典型例题
【百钱买百鸡问题】公元 5 世纪末,中国古代数学家张丘建在他的《算经》中提到了著名的
百钱买百鸡 问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问
翁、母、雏各几何?
分析:设鸡翁、鸡母、鸡雏的个数各为 x、y、z,百钱买
百鸡问题可以用如下方程式表示:
5x+3y+z/3=100
x+y+z=100
1<=x<20,1<=y<33,3<=z<100,z mod3=0
对于百钱买白鸡问题,很容易用穷举法对 x、y、z 的取值,判断
方程(1)、(2)及 z mod3=0 是否成立,若成立,则是问题的一个
解。
百钱买白鸡问题求解算法:
//百钱买白鸡问题穷举算法
//设鸡翁、鸡母、鸡雏的个数分别为 x、y、z
for(x=1;x<20;x++)
for(y=1;y<33;y++)
for(z=3;z<100;z++)
if(x+y+z= =100)and(5x+3y+z/3==100)and(z mod 3==0)
writeln(x,y,z)
上述算法是一个三重循环,最内层的条件判断需要执行 19*32*97 次,即 58976。在条件判断中,利用了整
数的求模运算,如果将鸡雏的个数设为 3z,可以避免该项判断,且可减少内重循环次数。即:
for(z=1;z<34;z++)
if(x+y+3z==100)and(5x+3y+z==100)
writeln(x,y,3z)
【 0-1 背包问题 1】给定 n 种物品和一个背包,物品 i 的重量是 W
i
,其价值为 V
i
,背包的
容量为 W
m
。应如何选择装入背包的物品,使得装入背包的物品总价值最大?
分析:所谓 0-1 背包问题,是指在选择装入背包的
物品时,对每种物品 i 只有两种选择,即装入背包或
不装入背包。另外,不能将物品 i 装入背包多次,也
不能只装入部分的物品 i。0-1 背包问题是一种组合
优化的 NP 完全问题,最容易想到方法的就是穷举
法。
0-1 背包问题求解的穷举算法。
//设数组 w[0…n–1]存储 n 件物品的重量,数组 c[0…n-1]存储
//n 件物品的价值,数组 b[0…n-1]为标识数组,若物品 i 未选
//择,则 b[i-1]=0,否则 b[i-1]=1
cmax=0
for(i=1;i<=2^n-1;i++)
{
b[0..n-1]=将 i 转化为 n 位的二进制字符串
tempw=求和 b[j]*w[j]
tempc=求和 b[j]*c[j]
If(tempw<wmax&&tempc>cmax)
{
tempb=b[0..n-1];
cmax=tempc;
}
}
输出最佳方案 tempb[0..n-1],cmax
结束
2.递推法
递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数
学模型,即给定一个数的序列a
0
,a
1
,…,a
n
若存在整数 n
0
,使当 n>n
0
时,可以用等号(或大于
号,小于号)将 a
n
与其前面的某些项 a
i
(0<i<n)联系起来,这样的式子称为递推公式,又称
递推关系。递推算法的基本思想是把一个复杂庞大的计算过程转化为简单过程的多次重复。
该类算法利用了计算机速度快和自动化的特点。
递推算法是一种简单的算法,通过已知条件利用特定的递推关系可以得到中间推论,直
至得到问题的最终结果。递推算法分为顺推法和逆推法两种。
【斐波那契数列算法 1】斐波那契数列,又称为黄金分割数列。在数学上,斐波那契数列可
以用递推方法定义,其递推公式为 F
1
=0,F
2
=1,F
n
=F
(n-1)
+F
(n-2)
(n>=3,n∈N*)。写一算法求斐波
那契数列第 10 项的值。
分析:从斐波那契数列的定义可知,数列的第一项为一,第二项也为一,递推关系是当前项
等于前二项之和。因此,通过顺推可以得到 f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5,
以此类推,可以得到 f(10)的值。
求斐波那契数列的顺推算法:
//求斐波那契数列第十项的值并输出
f[1]=1
f[2]=2
n=3
while(n<=10)
{
f[n]=f[n-1]+f[n-2]
n=n+1
}
write(f[10])
3.递归法
在问题求解思想上,递推是从已知条件出发,一步步递推出未知项,直到问题的解。递
归也是递推的一种,只不过它是对待解问题的递推,直到把一个复杂的问题递推为简单的易
解问题,然后再一步步返回,从而得到原问题的解。
【斐波那契数列算法 2】利用递归思想写出求斐波那契数列的递归算法。
分析:在问题求解中,求解同一个问题
的方法通常不止一个。根据递归法的思
想,由斐波那契数列递推公式可以很容
易地写出递归算法,伪代码描述如下。
求斐波那契数列递归算法:
//函数 fib 返回第 n(n>=1)个斐波那契数列的值
int fib(int n)
{
if(n ==1)
return(1)
else
if(n ==2)
return(2)
else return (fib(n-1)+fib(n-2))
}
【 Hanoi 塔 问 题 】 Hanoi 塔 问 题 ( Tower of Hanoi Problem ) 递 归 算 法 。
分析:可以把问题用初始状态和目标状态来表达,问题求解就是要找出搬移的次序和所有
的中间状态。
Hanoi 塔问题递归算法:
//n 为盘子数目
//三根柱子 from、to 和 temp 分别表示起始柱子、目标柱子和临时柱子
剩余10页未读,继续阅读
资源评论
nidezlk
- 粉丝: 1
- 资源: 11万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功