数字删除的贪心算法

1、海南师范大学算法设计与分析设计论文题目：贪心算法求解数字删除问题学生姓名：唐健峰学生姓名：吴贺寿专业班级：计算机科学与技术（非师范班）指导老师：石春 2016年12月16日Greedy algorithm to solve the problem of digital deleteAbstract:n the process of seeking the optimal solution of the problem, on the basis of a greedy standard, starting from the initial state of the problem,to fin

2、d the optimal solution for each step, through several greedy selection, finally obtains the optimal solution to the problem, this method is a greedy algorithm. From the definition of the greedy algorithm can be seen, the greedy method is not to think about the problem from the whole, it is the choic

3、e made by the local optimum in the sense of the solution, and the characteristics of the problem itself determines the use of greedy algorithm can achieve the optimal solution. The selection of the greedy algorithm can rely on previously made choices, but it does not depend on the choice of the futu

4、re, does not depend on the solution of sub problems, so the greedy algorithm and other algorithm has certain advantages compared to the speed. If a problem can be solved simultaneously in several ways, the greedy algorithm should be one of the best options. This paper first analyzes the digital dele

5、te problem, and then gives the greedy solution of the problem, finally proposed the time complexity of the algorithm is analyzed and the core of the problem, the greedy algorithm of the basic properties, characteristics and existing.Keyword：Greedy Algorithm，Digital deletion problem，Optimal solution

6、problem，Complexity。贪心算法求解数字删除问题摘要：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文首先对

7、数字删除删除问题进行了分析，然后给出了该问题的贪心解法，最后对所提出算法的时间复杂度进行了分析以及贪心算法的核心、基本性质、特点及其存在的问题。关键字：贪心算法 数字删除问题 最优解问题 复杂度引言 贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值。1. 数字删除问题描述 给定n位正

8、整数a，去掉其中任意k<=n（其中2<=n<=1000）个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。输入输入删除位数输出13245621234154789651214786541 分析：n位数t可表示为x1,x2，xi，xj，xk，xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为S，其最优解A=(y1，y2,yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为SA。  本问题采用贪心算法求解，采用最近下降点优先的贪心策略：

9、即x1<x2<<xi<xj；如果xk<xj，则删去xj，即得到一个新的数且这个数为n一1位中为最小的数Al，可表示为x1x2xixkxmxn。对A1而言，即删去了1位数后，原问题S变成了需对n-1位数删去k-1个数新问题S。新问题和原问题相同，只是问题规模由n减小为n-1，删去的数字个数由k减少为k-1。基于此种删除策略，对新问题S，选择最近下降点的数进行删除，如此进行下去，直至删去k个数为止。2.贪心算法2.1贪心选择性质所谓的贪心选择性质是指所求问题的整体最优解可以通过一系列局部最的选择。贪心选择性质的证明。对问题S删除的最近的下降点的数xj后得到的N1是n-

10、1位数是中的最小的数。2.2贪心选择性质证明：基本思路：考察一个问题的最优解，证明可修改的该最优解是的使得其从贪心选择开始，然后用数学归纳法证明每一步都可以通过贪心选择得到最优解。证明方法：1.假定首选定的元素不是贪心选择所要的元素，证明将首要的元素替换成贪心选择所需要的元素，依然得到最优解。2.数学归纳法证明每一步都可以通过贪心选择得到的最优解。证明方法一：设问题的S按照最近的下降点的方法删除，A=(y1,y2,yk)是删除数问题的一个最优解。易知，若问题有解，则1<=k<=n.(1) 当k=1时，由前得证，A=(y1,A)是问题的最优解；(2) 当k=1时，由反正法，得出A=(

11、y1,y2,yq)是最优解；当k=q+1时，由前得证，A=(y1,y2,yq+yq+1)是最优解。所以，最优解再问题具有贪心选择性质。证明方法二：设问题S已经按照最近下降点的方法删除，A=(y1,y2,.,yk)将t这个十进制数转化为下形式：x1*10(n-1)+x2*10(n-2)+xi*10(n-i)+xj*10(n-j)+xk*10(n-k)+xn这样的进制数。则：N1=x1*10(n-2)+x2*10(n-3)+xi*10(n-i-1)+xj*10(n-j-1)+xk*10(n-k-1)+xn；假设删去的不是xj而是其他位，则有N2=x1*10(n-2)+x2*10(n-3)+xj*1

12、0(n-k)+xn因为有x1<x2<<xi<xj and xj>xk,则有N1<N2.所以数字删除问题满足贪心选择性质。2.3最优子结构证明：在进行了贪心选择后，原问题T就变成了对N1如何删去k-1个数的问题T，是原问题的子问题。若A=(xj，A)是原问题T的最优解，则A是子问题T的最优解，其最值为TA。证明：假设A不是子问题T的最优解，其子问题的最优解为B，其最优值记为TB，则有TB<TA。而根据TA的定义可知：TA= TA+xj*1On-j，而TB<TA，IX 因此有TB+xj*1On-j<TA+xj*1On-j=TA。即存在一个由数a

13、删去1位数后得到的n-1位数比最优值TA更小。这与TA为问题T的最优值相矛盾。因此，A是子问题T的最优值。 因此，删数问题满足最优子结构性质。从以上贪心选择及最优子结构性质的证明可知删数问题用贪心算法可以求得最优解。3.1算法代码分析#include<stdio.h>#include<string.h>void zhuanhuan(int k, char a)while (k>0)int i = 0;/每次开始将i初始化为0，表示重新开始检。.。测下降点while (i<strlen(a) && ai <= ai + 1)i+;/ 算法

14、最为关键的部分for (int j = i; j < strlen(a); j+)aj = aj + 1;/覆盖实现删除效果k-;void main(void)int n, k;char a1000;/定义字符数组，最多可以存放1000个数字printf("请输入正整数m:");gets_s(a);n = strlen(a);printf("该数m的位数有 %d 位", n);printf("n请输入要删除的k（正整数）位的k:");scanf_s("%d", &k);while (k < 1

15、| k >= n)printf("你数输入的有误！n请重新再输入k:");scanf_s("%d", &k);printf("你要删除 %d 位数之后的结果为:", k);zhuanhuan(k, a);/删除后重新按原次序排列puts(a);3.2实验环境:(a)数据输入：输入数据第一行是一个整数m，第二行是一个整数k,2<=n<=1000(b)数据输出：输出删除后的数字(c)编程环境：Windows10 和Microsoft Visual Studio 20133.3算法流程3.复杂度针对具体算法，分析复杂性。该部分内容要有过程说明。此贪心算法的时间复杂度有whlile循环和for循环组成，所以此程序的时间复杂性为o(n2), 此程序的空间复杂性为o(n2)；总结：1） 学习到了贪心算法的性质（贪心选择性质和最优质3结构性质）以及贪心算法的证明。其中贪心算法的贪心性质需要用数学归纳证明。证明每一步的所做的贪选择最终导致问题的整体最优解来解决问题。2） 在代码方面，利用覆盖实现删除的效