贪心算法一般按如下步骤进行:
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解,得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解
一、实验目的
练习使用贪心算法解决实际问题(使用Java语言实现)。
二、实验内容
【问题描述】
随着大量的基因组DNA序列数据被获得, 它对于了解基因越来越重要(基因组DNA的一部分, 是负责蛋白质合成的) 。众所周知, 在基因组序列中, 由于存在垃圾的DNA中断基因的编码区,真核生物(相对于原核生物)的基因链更加复杂。也就是说,一个基因被分成几个编码片段(称为外显子)。虽然在蛋白质的合成过程中,外显子的顺序是固定的,但是外显子的数量和长度可以是任意的。 大多数基因识别算法分为两步:第一步,寻找可能的外显子;第二步,通过寻找一条拥有尽可能多的外显子的基因链,尽可能大地拼接一个基因。这条链必须遵循外显子出现在基因组序列中的顺序。外显子i在外显子j的前面的条件是i的末尾必须在j开头的前面。 本题的目标是,给定一组可能的外显子,找出一条拥有尽可能多的外显子链,拼接成一个基因。
【输入】
给出几组输入实例。每个实例的开头是基因组序列中可能的外显子数n(0<n<1000)。接着的n行,每行是一对整数,表示外显子在基因组序列中的起始和结束位置。假设基因组序列最长为50000。当一行是0时,表示输入结束。
【输出】
对于每个实例,找出最可能多的外显子链,输出链中的外显子,并占一行。假如有多条链,外显子数相同,那么,可以输出其中的任意一条。
该题的解决方案类似于课上老师所讲的会议安排问题,因此,在原有代码基础上稍作修改。
采用的贪心选择策略:
对结束时间,进行升序排序。优先选择最先结束的外显子,这样就可以选择最多的外显子。
package Gene; public class Gene implements Comparable<Gene> { public int begin; public int end; public int number; @Override public int compareTo(Gene o) { if(end==o.end){ return o.begin-begin; } return end-o.end; } }
package GeneAssembly; import Gene.Gene; import java.util.Arrays; import java.util.Scanner; public class GeneAssembly { int amount; Gene[] genes = new Gene[1000]; public void init() { Scanner scanner = new Scanner(System.in); System.out.print("请输入外显子总数:"); amount = scanner.nextInt(); for (int i = 0; i < amount; i++) { Gene temp = new Gene(); temp.number = i + 1; System.out.print("外显子" + temp.number + "的起始位:"); temp.begin = scanner.nextInt(); System.out.print("外显子"+temp.number + "的终止位:"); temp.end = scanner.nextInt(); System.out.println("***********************"); genes[i] = temp; } } public void solve() { Arrays.sort(genes, 0, amount); System.out.println("拼接后的基因如下:"); //选中了第一个外显子 System.out.print(genes[0].number); //记录刚刚被选中外显子的终止位 int last = genes[0].end; for (int i = 1; i < amount; i++) { if (genes[i].begin >= last) { last = genes[i].end; System.out.print(" "+genes[i].number); } } } }
package TestMain; import GeneAssembly.GeneAssembly; import java.util.Scanner; public class TestMain { public static void main(String[] args){ GeneAssembly gene =new GeneAssembly(); int i=1; while (i==1){ gene.init(); gene.solve(); System.out.println("是否还要输入外显子(1/0)"); Scanner scanner=new Scanner(System.in); i=scanner.nextInt(); } } }
分三个包编写:Gene,GeneAssembly,TestMain
欢迎来我的公众号:玹之空间
更多精彩有趣,尽在其中!!
源文件可私信后台发送,也可在公众号自提!