2024年安阳工学院。
算法设计与分析考期末试题。
一、填空。1算法三要素：操作，控制结构，数据结构。
2广度优先搜索，深度优先搜索。
2、简答。1、用计算机求解问题的步骤：
1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制。
2回溯算法求解步骤。
3动态规划基本步骤。
三、计算题。
10）用贪心算法求如下背包问题的最优解，n=7,m=15,价值p=，重量w=,用列表表示。
解：p/w=经过排序后排号为：5,1,6,3,7,2,4
则5号先放入包，此时，w总=1，p总=6，x5=1
1号放入包3，….16，..1
故x4=0,则得x=,p总=55.3
注：此题有错误，欢迎同学们提出正确答案。
11）设有资源数目为3，分配给3个项目，g(x)为第i个项目得到资源x所得到的利润，求总利润最大的资源分配方案利润见表。
解：分阶段，逐步考虑每一个项目在不同资源分配情况利润，设fi(x)为将资源x分配前i个项目的最大利润，分3段决策过程：
fi(x)=gi(x) 0<=x<=3
fi(x)=max 0<=x<=3,i=3
分三步分析题：
第一个项目a的资金x与利润fi(x)的关系如下：
分配前两项目的总资金x，x与利润f2(x)的关系，x2（0<=x2<=3）为分配给项目b的资金。
f1(1)=g1(1)
f2(x2)=max(0<=x2<=2)
当资源为3时，f3(3)=max(0<=x3<=3)
则f1(1)=g1(1)=0.11 f2(2)=g2(1)+f1(1)=0.23=0.12+0.11
f3(x3)max(0<=x<=3)=g3(1)+f2(2)=0.08+0.23
故当a分得1万元，b 分得1万元，c分得1万元，最后利润为最大0.31万元。
14）为马的遍历问题check函数设计。
int check(int x,int y)
if(xreturn 1;
else return 0;
#include
using namespace std;
int ack(int m,int n)
if(m==0)
return n+1;
else if(n==0)
return ack(m-1,1);
elsereturn ack(m-1,ack(m,n-1));
int main()
int m,n,t;
cin>>m>>n;
if(m<0||n<0)
cout<<”data is wrong”
cout<<”data is too longer”
cout<<”data is too longer”
cout<<”data is too longer”
cout<<”data is too longer”
cout<<”data is too longer” t=ack(m,n); cout<} return 0; 1、用计算机求解问题的步骤： 1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制。 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 3、算法的三要素。 1、操作2、控制结构3、数据结构。 3）算法的基本特征 p6 算法的基本特征：可行性、确定性、有穷性、有一个或多个输出、有零个或多个输入。 4）简述评价算法的标准 p36 对算法的分析和评价，一般应考虑正确性，可维护性，可读性，运算量。占用存储空间等诸多因素。其中评价算法的三条主要标准是： 1 算法所耗费的时间2 算法实现所耗费的存储空间，其中主要考虑辅助存储空间；3 算法应易于理解、易于编码。易于调试等。 5）算法的存储量包括哪些？ p39 1、 输入数据所占空间 2、 程序本身所占空间 3、 辅助变量所占空间 x=2，while（x<2/n） x=x*2，分析这条语句的频度。 由题知：x=x*2，2k+1（6）for(i=1;i for(j=1;j x=x+1;分析这条语句的频度； 解：p=1+2+……n=n(n+1)/2 7）简述递归的方法。p58 递归是一个过程活函数在定义或说明中有直接或间接调用自身的一种方法。 8）什么是数学模型 p107 数学模型是利用数学语言模拟现实的模型。把现实模型抽象，简化为某种数学结构是数学模型的基本特征。它或者能解释特定现状的现实状态，或者**到对象的未来状况，或者能提供处理对象的最优决策或控制。 9）简述数学建模过程 p107 数学建模就是把现实问题加以提炼，构造出数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，把数学知识的这一应用过程称为数学建模。用流程框图如图1所示： 建模。数学处理。 解释。四皇后。 13）4皇后问题，要求4*4的国际象棋棋盘中放4个皇后，使任意两个皇后都不被吃掉。 设计问题分析。 ）在第k行a[k]列放置第k个皇后，开始时k=1,a[k]=1 ）检查放置位置是否正确，如果a[i]-a[k]=|i-k|或a[i]=a[k](i（）若放置位置（k,a[k]）满足条件，重复（）（放置k+1直到最后一个位置成功，否则a[k]+1,重置，直到放置位置（k,a[k]）满足。 11.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需o 1 的时间，l为最短布线路径的长度，则算法共耗时 o mn 构造相应的最短距离需要 o l 时间。12.用回溯法解图的m着色问题时，使用下面的函数ok检查当前扩展结点的每一个儿子所相应的颜色的可用性... 12 动态规划算法基本思想 自底向上 全局最优 讲带求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是 适用于动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。最优子结构性质 问题的最优解包含了其子问题的最优解 子问题重叠性质 在用递归算法自顶... 分治法求全排列。算法描述。分治法求解问题分为三个步骤 分解 将问题分为若干个子问题。解决 递归地求解每个子问题。合并 将每个子问题的解合并成为整个问题的解。现在我们需要求具有n个元素的数组a的全排列。例如 大小为3的数组a a,b,c 为方便起见，我把引号全都省略了，其实应该是a a b c 下同 ...算法分析与设计期末
算法设计与分析复习
算法设计与分析复习