贪心算法报告.docVIP

算法与分析 课程设计报告 题 目： 刪数法 专 业： 网络工程 班 级： 1020552 学 号： 08 姓 名： 牛慧敏 太原工业学院计算机工程系 2012年 11 月17 日 算法问题描述 删数问题 给定一个n位正整数a，删掉其中任意k(k=n)个位，剩下的为按原顺序形成一个新的正整数。 找出剩下的数字最小的删树方案。对于给定的正整数a，编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1 行是1 个正整数a。第2 行是正整数k。 Output 程序运行结束时，将计算出的最小数输出到文件output.txt中。 Sample Input 178543 4 Sample Output 13 自左向右逐位扫描数字a，找到第i位，使得a[i]a[i+1]，那么删掉第i位后，剩下的是当前数字删掉1位后的最小值。最近下降点优先。迭代k次，删掉k位即可。 应如何来确定该删除哪s位呢？是不是只要删掉最大的s个数字就可以了呢？为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序有哪些信誉好的足球投注网站，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。 问题实例及算法运算步骤 最近降落点优先，设计一个算法找出剩下数字组成的新数最小的删数打算， 好比，剩下的数字按原次第陈列组成一个新的正整数，删除四个数字后。去掉其中k=n个数字。public static int RNB(int a, int k) { StringBuffer sb = new StringBuffer(a + ); int i, j; for (i = 0; i k; i++) { for (j = 0; j sb.length() - 1 sb.charAt(j) = sb.charAt(j + 1); j++) { } sb.delete(j, j + 1); } return sb.length() == 0 ? 0 : Integer.parseInt(sb.toString()); } public static void main(String[] args) { int min = RNB(178543, 4); System.out.println(min); } } 算法运行截图 算法复杂度分析 若用T(n)表示删除数所需要的时间复杂度，则整个算法的时间复杂度可表示为： T(n)=O(n2)。 算法的空间复杂度为：O(n2)。