数据结构若干经典问题和算法 (收藏)
一、迭代法
迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为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) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
二、穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
【问题】 将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++) {
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
# 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<VARIABLES;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; }
}
}
从上述问题解决的方法中,最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。
【问题】 背包问题
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。
【算法】
maxv=0;
for (i=0;i<2n;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]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
并用a[0]存储长整数N的位数m,即a[0]=m。按上述约定,数组的每个元素存储k的阶乘k!的一位数字,并从低位到高位依次存于数组的第二个元素、第三个元素……。例如,5!=120,在数组中的存储形式为:
3 0 2 1 ……
首元素3表示长整数是一个3位数,接着是低位到高位依次是0、2、1,表示成整数120。
计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加k-1次后求得。例如,已知4!=24,计算5!,可对原来的24累加4次24后得到120。细节见以下程序。
# include <stdio.h>
# include <malloc.h>
# define MAXN 1000
void pnext(int a[ ],int k)
{ int *b,m=a[0],i,j,r,carry;
b=(int * ) malloc(sizeof(int)* (m+1));
for ( i=1;i<=m;i++) b[i]=a[i];
for ( j=1;j<=k;j++)
{ for ( carry=0,i=1;i<=m;i++)
{ r=(i<a[0]?a[i]+b[i]:a[i])+carry;
a[i]=r%10;
没有合适的资源?快使用搜索试试~ 我知道了~
各大软件公司笔试面试题
共599个文件
txt:190个
doc:142个
gif:108个
5星 · 超过95%的资源 需积分: 10 20 下载量 188 浏览量
2011-03-17
14:15:11
上传
评论
收藏 3.17MB RAR 举报
温馨提示
很全的C/C++笔试面试题,会了这些题,什么软件公司都能进!!!!!!!!!!!!!!
资源详情
资源评论
资源推荐
收起资源包目录
各大软件公司笔试面试题 (599个子文件)
default.aspx 352B
ScriptResource(1).axd 82KB
ScriptResource(2).axd 29KB
ScriptResource.axd 21KB
WebResource.axd 20KB
test.cpp 2KB
AntiAndMaxlong.cpp 2KB
my.css 53KB
7.css 19KB
1.css 19KB
common.css 15KB
style.css 7KB
csdn.css 4KB
group.css 1KB
group.css 1KB
default.css 1KB
style.css 1KB
Thumbs.db 34KB
Thumbs.db 13KB
Thumbs.db 13KB
Thumbs.db 5KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
Thumbs.db 4KB
C语言之精华总结!.doc 538KB
金华业ISV SER招聘笔试(2).doc 114KB
应聘Java笔试时可能出现问题及其答案.doc 109KB
程序设计课程设计第3次.doc 98KB
全面整理的C++面试题.doc 91KB
标准C++测试题及解决.doc 88KB
C++C试题及解决.doc 87KB
计算机专业试题(09).doc 85KB
标准C++测试题.doc 85KB
计算机专业试题(05).doc 76KB
计算机专业试题(10).doc 73KB
计算机专业试题(06).doc 71KB
计算机专业试题(11).doc 70KB
计算机专业试题(11)_答案.doc 70KB
计算机专业试题(12).doc 69KB
计算机专业试题(12)_答案.doc 69KB
计算机专业试题(04).doc 68KB
Java试题(3).doc 66KB
Java试题(4).doc 65KB
增值定制服务部一面招聘试题答案-数据库.doc 64KB
JAVA培训资料.doc 62KB
嵌入式软件试题.doc 62KB
嵌入式软件试题.doc 62KB
C++测试题2及答案.doc 62KB
计算机专业试题(12)无答案.doc 62KB
计算机专业试题(10)无答案.doc 61KB
Java 笔试题.doc 61KB
计算机专业试题(07).doc 61KB
计算机专业试题(11)无答案.doc 59KB
软件开发人员招聘笔试试题(初试).doc 58KB
计算机专业试题(08).doc 58KB
软件开发人员招聘笔试试题(初试).doc 58KB
linux下串口编程.doc 57KB
友元.doc 57KB
增值定制服务部一面招聘试题答案-C++.doc 56KB
类与对象06-09.doc 55KB
增值定制服务部一面招聘试题-数据库.doc 55KB
简历模板(表格).doc 54KB
计算机专业试题(03).doc 54KB
Java试题(2).doc 52KB
计算机专业试题(10)_答案.doc 52KB
C++专业试题.doc 51KB
C++ Test Answer.doc 51KB
计算机专业试题(02).doc 49KB
引用.doc 49KB
java华为面试题.doc 49KB
科诺招聘试题.doc 48KB
C语言测试试题.doc 48KB
重载.doc 48KB
金华业c++面试题目抽样一.doc 47KB
计算机专业试题(01).doc 47KB
Java试题完全版051020.doc 46KB
摸板.doc 46KB
增值定制服务部一面招聘试题-C++.doc 46KB
ZTE-JAVA面试题目2.doc 42KB
C++ Test.doc 42KB
增值定制服务部一面招聘试题-java.doc 42KB
继承与派生.doc 41KB
增值定制服务部一面招聘试题答案-java.doc 41KB
ZTE-JAVA面试题目1.doc 40KB
C 语言基础题.doc 40KB
C++试题2.doc 39KB
C 语言基础测试题答案.doc 39KB
金华业Java面试题(1).doc 38KB
软件开发人员招聘笔试试题(培训).doc 37KB
软件开发人员招聘笔试试题(培训).doc 37KB
Java试题(1).doc 36KB
C++试题1.doc 36KB
软件测试工程师测试试题大集合(二)包括答案.doc 35KB
学员入学测试题库.doc 35KB
学员入学测试题库.doc 35KB
共 599 条
- 1
- 2
- 3
- 4
- 5
- 6
tangtianfly
- 粉丝: 1
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论3