【实践】算法第四章上机实践报告

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【实践】算法第四章上机实践报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1503字，纯文字阅读大概需要3分钟。

内容图文

1. 实践题目：卡了很久的”删数问题“

2. 问题描述：

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

要求输出最小数。如：给定a = 178543，k = 4，则输出13。

3. 算法描述：

先上代码

 1 # 进行删数操作
 2 def delete(my_list, times):
 3     while times > 0:
 4         for j in range(1, len(my_list)):
 5             if my_list[j] < my_list[j-1]:
 6                 del my_list[j-1]
 7                 times -= 1
 8                 break
 9     return my_list
10 
11 
12 # 输入原正整数a和删除位数k
13 a = input()
14 k = int(input())
15 num = []
16 for i in a:
17     num.append(int(i))
18 
19 # 调用函数进行处理
20 num = delete(num, k)
21 
22 # 把处理完的num列表转换为字符串类型输出
23 output = ""
24 for i in num:
25     output += str(i)
26 # 处理output中所含的前导零
27 print(output.lstrip("0"))

一开始没有发现规律，用字符串切片做的，写了特别多个if...elif...else语句判断，结果10个点只过了3个。后面才摸索到该问题的正确贪心性质其实很简单，就是把整个数字按位遍历一下，如果后一位数比前一位数小就把前一位删掉，从左删到右直至删够。整体代码实现不难，要想到这个费了点功夫。

4. 算法时间及空间复杂度分析：

嵌套最多层数的在delete函数，因为是while跟for两层循环，所以时间复杂度是O(n2)。

空间复杂度应该是O(1)，因为没有多开别的东西，仅使用了删除操作。

5. 心得体会：

贪心算法最重要的是找到贪心性质。在有些情况下贪心性质不好找。

在使用自己最初的做法无法AC时不要盲目多次尝试增加条件判断，有可能算法是假的，考虑下重新设计算法。

内容总结

以上是互联网集市为您收集整理的【实践】算法第四章上机实践报告全部内容，希望文章能够帮你解决【实践】算法第四章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---