算法第四章上机实践报告
2021/11/11 14:10:23
本文主要是介绍算法第四章上机实践报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
删数问题给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。
输入格式:
第 1 行是1 个正整数 a。第 2 行是正整数k。
输出格式:
输出最小数。
算法描述(满足贪心选着性质)
因为要剩下的数最小,单纯的把最大的数字删去并没有办法得到最小,如175438,最小应该是删去数字7,而不是最大的8。
多观察一些样例,可以发现:
每一步总是选择一个使剩下的数最小的数字删除。即按高位到低位的顺序搜索(使用char 数组存储),若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首字符。这样得出来的就是局部最优解
删除之后,其他数字往前移动一位,填补位置。最后把剩下的几个数字,组成一个整数。
然后为了把剩下的数字里开头的“0”删除,设置一个flag,当这个位置内容不为0,并且该i<n-1(防止删除后全为零无输出结果)、flag没被改变过,可得出这个是在开头的数字0,不输出;否者,就输出,并且改变flag的值表面有非零数字开头了。
算法时间及空间复杂度分析
时间复杂度O(kn)
无借用辅助空间,空间复杂度为0。
对贪心算法的理解
与动态规划不同的是,贪心算法在求解问题时,总是选择对于当前子问题最好的选择。也就是贪心算法的本质是每次只顾眼前利益,并且到最后能获得最大利益。
对于贪心算法,最重要的就是找到每次的局部最优解,而动态规划的关键在于找到状态转移方程。
贪心算法对问题只需考虑当前局部信息就要做出决策,也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。该算法的适用范围较小, 若应用不当, 不能保证求得问题的最优解。都需要通过数学方法来证明其正确性。
这篇关于算法第四章上机实践报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)