【每日一题】备战冲击蓝桥杯国赛——Python程序设计 | Day05 | 排序 | 真题代码解析
每天刷一道题，话不多说，先刷近两年的题吧，从2020的开始，如果有一起的可以加入我们！！！
一起来刷题，冲击国赛！！！
2020年第十一届蓝桥杯赛题总览
2020年的题就是这些，类型分为两种，分别是结果填空和程序设计，我们每天刷一道题，省赛没问题！
蛇形填数（题目）
（本题总分：10分）
—>【问题描述】
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻. 在冒泡排序中，每次只能交换相邻的两个元素。 小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。 例如， 对于字符串lan排序，只需要1次交换。对于字符串qiao排序， 总共需要4次交换。 小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要100次交换，
可是他忘了把这个字符串记下来，现在找不到了。 请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要100次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
—>【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
解析
通过阅读题干，本题——难度较易：⭐
考察类型：数论
考察知识点：冒泡法排序+时间复杂度 O
分析：
由于是填空题，我们只需要得出一个结果即可。结果为一个整数。
意图很明显，考察冒泡排序，给出了四个条件：
① 只包含小写英文字母
②没有重复出现的字母
③ 正好交换100次
④ 有多个找出字符串最短的那个
我们可以根据题干给的约束条件，一步一步的将范围给缩小，最终找到满足条件最小的那一个。
首先，小写字母，也就是从（a~z）共26个。
一个必备知识点：冒泡排序的排序交换次数计算公式——count = （n*(n-1)）/ 2根据100次的要求，我们带入count中，求解出n的结果为13.94，我们得不到整数，那可怎么办额。字母的个数不可能是需要小数吧，所以我们怎么办呢？当n=15的时候，count=105次；当n=14时，count=91，理性的选择n=15，所以我们需要挑选15个小写英文字母。然后，我们可以自己手动再换5次回去，那不是剩下就只剩100次就可以换回去了吗？
题目要求字典序最小*(字典序最小就是指 a,b,c,d的顺序最小），那么就是顺着来一遍:abcdefghijklmno
然后再逆序：onmlkjihgfedcba
按照上面的思路先换5次，则为：jonmlkihgfedcba
现在来检测一下是否正确吧！~
代码
Python代码实现：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/2/27 14:17
# @Author : 府学路18号车神
# @Email ：yurz_control@163.com
# @File : Day05.py
#
num = list("jonmlkihgfedcba") # 将字符串化成列表，独立出单个字母为字符
res = 0 # 设置计数器，目标为100次
n = len(num)
# print(num[0], n)
for i in range(n-1): # 普通冒泡
for j in range(n-i-1):
if num[j] > num[j+1]: # 前面大于后面，下面执行交换操作
num[j], num[j+1] = num[j+1], num[j]
res += 1
print("转化的次数为：", res) # 100
由此，我们可以快速的出结果为：jonmlkihgfedcba
- 点赞
- 收藏
- 关注作者
评论（0）