Java教程

算法第四章上机实验报告

本文主要是介绍算法第四章上机实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.问题描述

给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

2.算法描述

3.问题求解

显然高位数位的数值大小更对数字的大小起决定性作用,因此从高位开始贪心,挑选小数字数位保留。

简单贪心删k法的思路是从高位往低位贪心,当当前可删k个数时,选取前k+1个高位,找到最小数(有多个最小则优先选定靠左高位数),该最小数即保留数位,该位的左方数字删去

从第一个数开始遍历,到寻找到单调递减的第一个数(即单调递增的最后一个数),则删除,若无单调递减子序列,则删掉最后一个非递减序列的数;每找到一个就又从头开始。即每做一次删数,就是一次贪心选择,删掉此数剩下的数为组成最小,经过证明,此结论正确

 

 4.心得体会

基础不牢地动山摇,以后要好好学习。

这篇关于算法第四章上机实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!