没有合适的资源?快使用搜索试试~ 我知道了~
常用算法设计方法+搜集.pdf
需积分: 10 12 下载量 188 浏览量
2010-02-12
15:13:51
上传
评论
收藏 397KB PDF 举报
温馨提示
试读
43页
掌握足够的算法是程序员的必经之路,这本书有很多算法,可以使你的编程思维达到一个新的高度。
资源推荐
资源详情
资源评论
1
常用算法设计方法
要使计算机能完成人们预定的工作, 首先必须为如何完成预定的工作设计一个算法, 然
后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,
其中程序的数据结构和变量用来描述问题的对象, 程序结构、 函数和语句用来描述问题的 算
法。算法数据结构是程序的两个重要方面。
算法是问题求解过程的精确描述, 一个算法由有限条可完全机械地执行的、 有确定结 果
的指令组成。 指令正确地描述了要完成的任务和它们被执行的顺序。 计算机按算法指令所 描
述的顺序执行算法的指令能在有限的步骤内终止, 或终止于给出问题的解, 或终止于指出 问
题对此输入数据无解。
通常求解一个问题可能会有多种算法可供选择, 选择的主要标准是算法的正确性和可 靠
性,简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作, 经常采用的算法设计技术主要有迭代法、 穷举搜索
法、
递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐 视
算法,在算法设计时又常常采用递归技术,用递归描述算法。
( 下载源码就到 源码网 : www.codepub.com )
一、迭代法
迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 f(x)=0
,
用
某种数学方法导出等价的形式 x=g(x) ,然后按以下步骤执行:
( 1 )
选一个方程的近似根,赋给变量 x
0
;
( 2 )
将 x
0
的值保存于变量 x1 ,然后计算 g(x
1
) ,并将结果存于变量 x
0
;
( 3 )
当 x
0
与 x
1
的差的绝对值还小于指定的精度要求时,重复步骤( 2 )的计算。
若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的 x
0
就
认为是方程的根。上述算法用 C 程序的形式表示为:
【算法】迭代法求方程的根
{ x0 = 初始近似根;
do {
x1=x0 ;
x0=g(x1) ; /* 按特定的方程计算新的近似根 */
} while ( fabs(x0-x1)>Epsilon) ;
printf( “ 方程的近似根是 %f ” , x0) ;
}
迭代算法也常用于求方程组的根,令
X= ( x
0
, x
1
, … , x
n-1
)
设方程组为:
x
i
=g
i
(X) (I=0 , 1 , … , n-1 )
则求方程组根的迭代算法可描述如下:
2
【算法】迭代法求方程组的根
{ 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 )
方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会
导致迭代失败。 ( 下载源码就到 源码网 : www.codepub.com )
二、穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验, 并从中找出 那
些符合要求的候选解作为问题的解。
【问题】 将 A 、 B 、 C 、 D 、 E 、 F 这六个变量排成如图所示的三角形,这六个变量分别
取 [1 , 6] 上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就 是
一个解。
程序引入变量 a 、 b 、 c 、 d 、 e 、 f ,并让它们分别顺序取 1 至 6 的证书,在它们互不相 同
的条件下, 测试由它们排成的如图所示的三角形三条边上的变量之和是否相等, 如相等即 为
一种满足要求的排列, 把它们输出。 当这些变量取尽所有的组合后, 程序就可得到全部可 能
的解。细节见下面的程序。
【程序 1 】
# include <stdio.h>
void main()
{ int a,b,c,d,e,f;
for (a=1;a<=6;a++)
for (b=1;b<=6;b++)
{
3
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 ” );
}
}
}
}
}
}
按穷举法编写的程序通常不能适应变化的情况。 如问题改成有 9 个变量排成三角形, 每
条边有 4 个变量的情况,程序的循环重数就要相应改变。
对一组数穷尽所有排列, 还有更直接的方法。 将一个排列看作一个长整数,则所有排 列
对应着一组整数。 将这组整数按从小到大的顺序排列排成一个整数, 从对应最小的整数开
始。
按数列的递增顺序逐一列举每个排列对应的每个整数, 这能更有效地完成排列的穷举。 从 一
个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。 倘若当前排 列
为 1
,
2
,
4
,
6
,
5
,
3 ,并令其对应的长整数为 124653 。要寻找比长整数 124653 更大的排
列,
可从该排列的最后一个数字顺序向前逐位考察, 当发现排列中的某个数字比它前一个数字 大
时, 如本例中的 6 比它的前一位数字 4 大, 这说明还有对应更大整数的排列。但为了顺序 从
小到大列举出所有的排列, 不能立即调整得太大, 如本例中将数字 6 与数字 4 交换得到的 排
列 126453 就不是排列 124653 的下一个排列。为了得到排列 124653 的下一个排列,应从已
经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如数字 5 , 与
数字 4 交换。该数字也是从后向前考察过程中第一个比 4 大的数字。 5 与 4 交换后,得到 排
列 125643 。在前面数字 1 , 2 , 5 固定的情况下,还应选择对应最小整数的那个排列,为此
还需将后面那部分数字的排 列顺序颠倒, 如将数字 6
,
4
,
3 的排列顺序颠倒, 得到排列 1
,
2
,
5
,
3 , 4 , 6 ,这才是排列 1 , 2 , 4 , 6 , 5 , 3 的下一个排列。按以上想法编写的程序如下。
【程序 2 】
# include <stdio.h>
# define SIDE_N 3
# define LENGTH 3
4
# define VARIABLES 6
int A,B,C,D,E,F;
int *pt[]={&A,&B,&C,&D,&E,&F};
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
int side_total[SIDE_N];
main{}
{ int i,j,t,equal;
for (j=0;j<VARIABLES;j++)
*pt[j]=j+1;
while(1)
{ for (i=0;i<SIDE_N;i++)
{ for (t=j=0;j<LENGTH;j++)
t+=*side[i][j];
side_total[i]=t;
}
for (equal=1,i=0;equal&&i<SIDE_N-1;i++)
if (side_total[i]!=side_total[i+1] equal=0;
if (equal)
{ for (i=1;i<V ARIABLES;i++)
printf( “ %4d ” ,*pt[i]);
printf( “ \n ” );
scanf( “ %*c ” );
}
for (j=VARIABLES-1;j>0;j--)
if (*pt[j]>*pt[j-1]) break;
if (j==0) break;
for (i=VARIABLES-1;i>=j;i--)
if (*pt[i]>*pt[i-1]) break;
t=*pt[j-1];* pt[j-1] =*
=*
=*
=* pt[i]; *pt[i]=t;
for (i=VARIABLES-1;i>j;i--,j++)
{ t=*pt[j]; *pt[j] =*
=*
=*
=* pt[i]; *pt[i]=t; }
}
}
从上述问题解决的方法中, 最重要的因素就是确定某种方法来确定所有的候选解。 下 面
再用一个示例来加以说明。 ( 下载源码就到 源码网 : www.codepub.com )
【问题】 背包问题
问题描述: 有不同价值、 不同重量的物品 n 件, 求从这 n 件物品中选取一部分物品的 选
择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设 n 个物品的重量和价值分别存储于数组 w[ ] 和 v[ ] 中,限制重量为 tw 。 考虑一个 n 元
组( x
0
, x
1
, … , x
n -1
) ,其中
x
i
=0 表示第 i 个物品没有选取,而 x
i
=1 则表示第 i 个物品被 选
取。 显然这个 n 元组等价于一个选择方案。 用枚举法解决背包问题, 需要枚举所有的选取 方
案,而根据上述方法,我们只要枚举所有的 n 元组,就可以得到问题的解。
5
显然,每个分量取值为 0 或 1 的 n 元组的个数共为 2
n
个。而每个 n 元组其实对应了一
个长度为 n 的二进制数,且这些二进制数的取值范围为 0 ~ 2
n
-1 。因此,如果把 0 ~ 2
n
-1 分
别转化为相应的二进制数,则可以得到我们所需要的 2
n
个 n 元组。
【算法】
maxv=0;
for (i=0;i< 2
n
;i++)
{ B[0..n-1]=0;
把 i 转化为二进制数,存储于数组 B 中 ;
temp_w=0;
temp_v=0;
for (j=0;j<n;j++)
{ if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w<=tw)&&(temp_v>maxv))
{ maxv=temp_v;
保存该 B 数组;
}
}
}
三、递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。 设要求问题规模 为
N 的解,当 N=1 时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题
有重要的递推性质,即当得到问题规模为 i -1 的解后,由问题的递推性质,能从已求得的 规
模为 1 , 2 , … , i-1 的一系列解,构造出问题规模为 I 的解。这样,程序可从 i=0 或 i=1 出
发,重复地,由已知至 i-1 规模的解,通过递推,获得规模为 i 的解,直至得到规模为 N 的
解。
【问题】 阶乘计算
问题描述:编写程序,对给定的
n
( n ≦ 100
) ,计算并输出
k 的阶乘 k
! (
k= 1
,
2 , …
,
n
)
的全部有效数字。
由于要求的整数可能大大超出一般整数的位数, 程序用一维数组存储长整数, 存储长 整
数数组的每个元素只存储长整数的一位数字。如有 m 位成整数 N 用数组 a[ ] 存储:
N=a[m] × 10
m-1
+a[m-1] × 10
m-2
+ … +a[2] × 10
1
+a[1] × 10
0
并用 a[0] 存储长整数 N 的位数 m , 即 a[0]=m 。 按上述约定, 数组的每个元素存储 k 的阶乘 k
!
的一位数字, 并从低位到高位依次存于数组的第二个元素、 第三个元素 ……
。 例如,
5
!
= 120
,
在数组中的存储形式为:
剩余42页未读,继续阅读
资源评论
abc_labc
- 粉丝: 83
- 资源: 16
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功