基于Java实现多个题目求解(算法课程)【100012653】

# 题目一 二项式公式计算 ## 1. 问题描述 完成二项式公式计算，即  公式解释：为了从n个不同元素中抓取k个元素，可以这样考虑，如果第一个元素一定在结果中，那么就需要从剩下的n-1个元素中抓取k-1个元素；如果第一个元素不在结果中，就需要从剩下的n-1个元素中抓取k个元素。 要求分别采用以下方法计算，并进行三种方法所需时间的经验分析。 a. 直接采用递归算法 b. 采用备忘录方法 c. 采用迭代算法 要有性能数据。最好是的曲线或者曲面图。迭代算法要和递归思路相关。另外，Excel其实可以帮你你完成函数拟合（回归)，就是帮你猜时间复杂度。 ## 2. 题所用的算法设计方法及基本思路 利用3个方式来实现。但是3种方式的总体思路是一样的。都是分为两种情况，一种是取元素时抓到了第一个元素，那么就在N-1个中进行K-1的迭代或者是递归。第二种是抓去元素时未抓到第一个那么就在N-1个中进行K的迭代和递归。 ## 3. 数据结构描述 未使用数组结构 ## 4. 算法描述 算法名称：Binonial 输入：正整数k，正整数n 输出：二项式公式计算结果 算法实现细节 ```java r = int[n + 1][k + 1]; for i <- 1 to n do for j <- 0 to k do if i=j || j=0 r[i][j] = 0; else r[i][j] = r[i - 1][j - 1] + r[i- 1][j]; return r[n][k]; ``` ## 5. 算法的时间空间复杂度分析 ​ 时间复杂度：O(nlogn) ​ 空间复杂度：O(n²) ## 6. 算法实例 输入的数据  输出的数据  # 题目二 简单分形树 ## 1. 问题描述 先垂直绘制一根线段，然后在线段顶端向右一定倾角绘制一根线段，长度分别为原线段的k倍. 再同样的，在线段左侧以固定倾角绘制一根线段，如此反复，直至线段长度小于某个较小的值。其中，线条颜色以及长度，夹角（例如产生某个范围的随机数）都可以自行进行微调。 ## 2. 解决问题所用的算法设计方法及基本思路 这题就是用一直递归方式，向下输出分支，设计一个合理的出口形成一个分支树。左右支分别分别就是一次递归。那么两次递归所放的位置在输出前还是输出后，都可以完成分形树的标准。但是所放位置的不同，就有点类似于先序遍历，中序遍历和后序遍历一样。 而最后界面实现利用的javaFX实现界面的输出 ## 3. 采用的数据结构描述 未使用数据结构 ## 4. 算法描述 算法名称：Branch 输入：正整数n 出口整数 输出：递归输出分形树 算法实现细节 ```java if n < 10 return Branch(n) Branch(n) ``` ## 5. 算法的时间空间复杂度分析 时间复杂度：O(nlogn) 空间复杂度:O(nlogn) ## 6. 算法实例 数据的输出  # 题目三 三水杯倒水问题 ## 1. 问题描述 西蒙.丹尼斯.泊松是著名的法国数学家和物理学家。据说在他遇到某个古老的谜题之后，就开始对数学感兴趣了，这个谜题是这样的：给定一个装满水的8品脱壶以及两个容量分别为5品脱和3品脱的空壶，如何通过完全灌满或者到空这些壶从而使得某个壶精确地装有4品脱的水？用广度优先查找来求解这个谜题。要求在输出结果中包含广度优先的遍历过程（结点的遍历顺序）。 ## 2. 解决问题所用的算法设计方法及基本思路 本题根据提示使用广度优先遍历，对每次倒水的所有方式先拿出来，存储到队列当中。对队列中的倒水后的情况取出，又得到所有的当前情况下的所有倒水操作，进行存储。最后得到题目要求的数，立即终止当前树的遍历回到之前的节点。 ## 3. 采用的数据结构描述 利用队列先进先出的特征，进行广度优先遍历。 ## 4. 算法描述  ## 5. 算法的时间空间复杂度分析 时间复杂度：O(n²) 空间复杂度：O(n²) ## 6. 算法实例 数据的输入  数据的输出  …...（情况未完成截取） # 题目四 九宫格问题 ## 1. 问题描述 画出所有可能的九宫图, 即每行每列，每一斜行的和都相同  ## 2. 解决问题所用的算法设计方法及基本思路 本题使用深度优先遍历，从九宫格从未填开始，依次往下遍历。先填满，看是否符合标准。若符合保存到结果数组中。若不符合那么回到上一结点，更改上一结点的情况，继续向下遍历，直至填满。一直循环，直至将所有情况拿出来，进行核对。 ## 3. 采用的数据结构描述 未使用数据结构。 ## 4. 算法描述  ## 5. 算法的时间空间复杂度分析 ​ 时间复杂度：O(n²) 空间复杂度：O(n) ## 6. 算法实例 数据的输出  # 题目五 租船问题 ## 1. 问题描述 长江游艇俱乐部在长江上设置了n个游艇出租站1,2,...,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j)，。试着设计一个算法，计算处从游艇出租站1到游艇出租站n所需要的最少租金。输入：n和相应规模的r(i,j) 。注意j>i，所以r(i,j)只有n-1行。 例如:  表示n=3, r(1,2) = 5, r(1,3) = 15, r(2,3) = 7 输出：最少租金。 ## 2. 解决问题所用的算法设计方法及基本思路 本题的问题可以划分为上一站的最少价值，加上当前的直达价值。这样就符合动态规划的思想。对问题的划分为子问题。而每一个子问题又对当前的问题可以进行影响或是比较。最后确立当前这个问题的最优选择。 ## 3. 采用的数据结构描述 未使用数据结构。 ## 4. 算法描述 算法名称：Charter 输入：数组a[x][x] 租船每个节点的价格 输出：从出发到最后最便宜的价格 算法实现细节 ## 5. 算法的时间空间复杂度分析 时间复杂度：O(n²) 空间复杂度：O(n²) ## 6. 算法实例 动态规划填表  数据的输入  数据的输出  题目六 基因序列比较 ## 1. 问题描述 人类基因由4种核苷酸，分别用字母ACTG表示。要求编写一个程序，按以下规划比较两个基因序列并确定它们的相似程度。即两给出两个基因序列AGTGATG和GTTAG，它们有多相似呢？测量两个基因的相似度一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格，让两个基因的长度相等，然后根据基因的分值矩阵计算分数。  比较AGTGATG与GTTAG: 第一种对齐方案为： 首先可以给AGTATG插入一个空格得：AGTAT-G GTTAG插入3个空格即得：-GT-TAG 上面的匹配分值为:-3+5+5+(-2)+(-3)+5+(-3)+5=9. 第二种对齐方案为： AGTGATG -GTTA-G 得到的分值为：(-3)+5+5+(-2)+5+(-1)+5=14. 当然还有其它对齐方式，但以上对齐方式是最优的，所以两个基因的相似度就为14。 ## 2. 解决问题所用的算法设计方法及基本思路 同样根据题意我们可以将两个基因分为X序列和Y序列。那么我们根据题意的划分基因匹配时无非就是3种情况：第一种XY，既是X序列和Y序列中字符的对应。第二种X-，既是X序列中的字符和空位所对应。第三种-Y，既是空位和Y序列中的字符所对应。 那么当我们将上述的情况就可以从该序列的第一个开始分起。即将一个问题划分了�