算法分析与设计习题集整理

算法分析与设计问题集排列第一章算法介绍一、填空：1.算法运算所需的计算机资源量称为算法复杂度，主要包括时间复杂度和空间复杂度。2.多项式的上限是0(nm)。3.算法的基本特征：输入、输出、确定性、有限性和可行性。4.如何从时间复杂度和空间复杂度两个方面评估算法。5.将以下算法的时间复杂度计算为0(n3)。对于(I=1；i=n。(I)对于(j=1；j=n。j)j=0；对于(k=1；k=n；k)cIj=cIjaIk* bkj；6.描述算法的常用方法：自然语言、伪代码、编程语言、流程图、方框图和PAD。7.算法设计的基本要求：正确性和可读性。8.计算以下算法的时间复杂度：0(N2)。对于(I=1；当i4时，a=16。因此，A的最大整数值是15。5.算法分析的目的？答：1)为算法的某些特定输入估计算法所需的内存空间和运行时间；2)建立一个标准来衡量算法的优缺点，并对同一类问题的不同算法进行比较。6、算法设计常用技术？(写5)答：分治法；(2)回溯法；(3)贪婪方法；动态规划方法(5)分治边界法；蛮力法；反演方法三、算法设计问题暴力手段：百凤百钱的问题？2.倒置：穿越沙漠？第二章分治算法(1)递归循环一、填空：1.直接或间接调用自身的算法称为递归算法，由函数本身定义的函数称为递归函数。2.递归方程和约束函数(递归终止条件)是递归函数的两个要素。2.真或假：1.所有递归函数都可以找到相应的非递归定义。()2.递归函数可以在没有初始值的情况下定义。(十)三、简短回答问题：1.什么是递归算法？递归算法的特点是什么？答：1)递归算法：是一个模块(函数、过程)，除了其他模块(函数、过程)之外，还可以直接或间接地调用自己的算法。2)递归算法特征：(1)每个递归函数必须有一个非递归定义的初始值；否则，递归函数无法计算；(递归终止条件)(2)在递归中，用较小的自变量函数值来表示较大的自变量函数值；(递归方程)2、比较循环和递归的异同？回答：1)相同：递归和循环都是解决“重复操作”的机制。2)不同：就效率而言，递归算法的实现通常比迭代算法(调用和返回需要额外的时间)和存储空间(用于存储不同调用下变量的当前值的堆栈空间)花费更多的时间，这也限制了递归的深度。原则上，每个迭代算法总是可以转换成它的等效递归算法。恰恰相反。递归的级别是可以控制的，而循环嵌套的级别只能是固定的，因此递归是一种比循环更灵活的重复操作机制。3.递归算法通常有三个步骤来解决问题？答：1)分析问题，寻找递归：找出大规模问题和小规模问题之间的关系，通过递归使问题的规模逐渐缩小。2)设置边界和控制递归：找出停止条件，即算法能够解决的最小规模问题。3)设计函数和确定参数：像其他算法模块一样设计函数体中的操作和相关参数。四、算法设计问题：1.楼梯上有n级台阶。上楼时可以走一两步。设计了一个递归算法来找出楼上有多少种方法。(1)写出F(n)的递归表达式？(2)并编写其相应的递归算法？解决方法：写出F(n)的递归表达式分析：有两种方法可以达到订单编号：1)从n-1阶到n阶；2)从n-2阶到n阶；1 n=1F(n)=2 n=2F(n-1) F(n-2) n2(2)写下相应的递归算法？整数F(整数n)如果(n=1)返回1；否则如果(n=2)返回2；其他返回F(n-1)F(n-2)；2.设置a，b和c为三个塔。开始时，在塔底座a上有一堆n个磁盘，从下到上从上到下堆叠。每个磁盘编号为1，2，n.从小到大。现在，需要将塔底座A上的这一堆磁盘移动到塔底座B上，并且仍然以相同的顺序堆叠它们。移动光盘时，应遵守以下移动规则：规则1:一次只能移动一张光盘；规则2:任何时候都不允许将较大的光盘压在较小的光盘上。规则3:在满足移动规则1和2的前提下，磁盘可以移动到a、B、c、B和c中的任何一个塔基(1)写下解决问题的步骤？(2)并编写其相应的递归算法？解决方案：(1)步骤1:将N-1个板作为一个整体，将它们从一个移动到另一个；步骤2:将第n块板移至B；第三步：把N-1个板块作为一个整体，把它们从C移到B；(2)编写其相应的递归算法：void hanoi(int n，int a，int b，int c)if (n 0)河内(n-1，a，c，b)；移动(a，b)；河内(n-1，c，b，a)； 第二章分治算法(2)分治算法一、填空：1.在快速排序、插入排序和合并排序算法中，插入排序算法不是分治算法。2.合并排序算法采用分治算法设计的思想。3.采用分治算法的思想设计了二进制搜索算法。第二，简短回答问题：1.适合用分治算法解决的问题的基本特征是什么？答：1)在一定程度上缩小规模可以很容易地解决问题；2)问题可以分解成几个较小的相同问题，即问题具有最优子结构性质；3)问题分解的子问题是相互独立的，即子问题之间没有共同的子问题。4)问题分解后子问题解可以合并成问题的解；2.分治算法的基本思想和解决问题的步骤？三、算法设计问题：1、重写二进制搜索算法：让1.n为有序数组，重写二进制搜索算法，以便当搜索元素X不在数组中时，返回小于X的最大元素位置I和大于X的最小元素位置J；当搜索元素x在数组中时，I和j是相同的，都是x在数组中的位置。并分析其时间复杂性？解决方案：int binsearch(int an)，int x，/x待定数据int mid，I，j；低=1；int high=n；同时(低=高)中=(低高)/2；如果(中值)=x，返回i=j=中值；如果(中部)x高=中部1；/继续在左侧搜索否则/(中值=2)来寻找最大和最小元素。使用分而治之的方法(二分法)，上述问题可以用较少的比较来解决：1)将数据平均分为两组(两组可能相差1)，以选择最大(最小)值。2)递归分解，直到每组中元素的数量2，可以简单地找到最大(最小)值。3)回溯时，两组分解后的解将合并为当前问题的解，大的解取大的解，小的解取小的解。、第三章动态规划算法一、填空：1.子问题的解存储在动态规划算法中，以避免重复求解子问题。(2)最优子结构)是用动态规划算法解决问题的前提。3.矩阵乘法问题的算法可以用(动态规划)算法来设计和实现。2.真或假：1.动态规划算法的基本要素是最优子结构。()2.最优子结构性质是指原问题的最优解包含其子问题的最优解。()3.动态规划算法解决问题时，分解的子问题是相互独立的。(十)三、简短回答问题：1、动态规划算法解题步骤？答：找出最优解的性质并描述其结构特征；(也就是说，原始问题的最优解包括子问题的最优解)(2)递归定义最优值；(即子问题是重叠的，子问题定义了原始问题)(3)自下而上计算最优值；(4)根据计算最优值时获得的信息构造最优解；2、动