Python算法学习: 竞码编程-蓝桥杯模拟赛3题解

Python算法

字数统计: 2k阅读时长: 8 min

 2020/03/07   Share

@TOC

A. 试题A：生存还是毁灭,这是一个问题 7’

描述
对于给定的文章，求出出现频率最高的字母。

对于字母的出现频率，我们定义为：该字母在整个文章中出现的次数。

例如：“To be or not to be, that is the question!”

出现频率最高的字母是：t,总共出现了77次。

对于以下莎士比亚的《哈姆雷特》经典片段，你能帮JM找到出现频率最高的字母出现的次数吗？

输出出现频率最高的字母出现的次数。

注意：字母不区分大小写。

思路:

这里我将a-z A-Z的ascii 编码作为筛选点, 将所有的字母传入新列表然后寻找

str = ''' To be, or not to be: that is the question,
Whether it's nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them. To die,to sleep;
No more; and by a sleep to say we end
The heartache, and the thousand natural shocks
That flesh is heir to, it's a consummation
Devoutly to be wished. To die, to sleep.
To sleep, perchance to dream: ay, there's the rub;
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause. There's the respect
That makes calamity of so long life;
For who would bear the whips and scorns of time,
The oppressor's wrong, the proud man's contumely,
The pangs of despised love, the law's delay,
The insolence of office, and the spurns
That patient merit of the unworthy takes,
When he himself might his quietus make
With a bare bodkin? Who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscovered country from whose bourn
No traveller returns, puzzles the will,
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all,
And thus the native hue of resolution
Is sicklied or with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry
And lose the name of action.'''
strq = ""
tmp = 0
ans = 0
# 97 122 65 90
for i in str:
    if 65<=ord(i)<=90 or 97<=ord(i)<=122:
        strq += i.lower()
for i in strq:
    tmp = strq.count(i)
    if tmp>ans:
        ans = tmp
print(ans)

B. 试题B：小小神枪手开局98K 8’

描述
JM是一个吃鸡玩家，开局98K，人物描边大师。

已知JM的初始射击命中率为75\%75%。如果JM一击未中，则会由于种种原因(心理压力)导致JM的命中率在上一枪的命中率基础上，减低10\%10%。

例如：第一枪的命中率为75\%75%，则第二枪的命中率为75\% 90\%75%∗90%，第三枪的命中率为75\% 90\% * 90\%75%∗90%∗90%，以此类推。

当然，当命中率低于50\%50%的时候，JM则会放弃射击。

现在，JM想知道，他击中敌人的期望次数是多少？保留66位小数。

注意：

1、射击命中则停止射击
2、放弃射击则不统计次数。

思路:
在这里插入图片描述
这里就是很简单的数学期望问题

n1 = 0.75
n2 = 0.675000
n3 = 0.607500
n4 = 0.546750
ans = n1 + 2*((1-n1)*n2) + 3*((1-n1)*(1-n2)*n3) + 4*((1-n1)*(1-n2)*(1-n3)*n4)
print(ans)

C. 试题C：关云长单刀会金莲，贾宝玉三打白骨精 10’

描述
三国在国，治国，兴国，安国，丧国。

水浒在气，勇气，义气，豪气，霸气。

红楼在情，亲情，爱情，宦情，民情。

西游在趣，情趣，游曲，野趣，妖趣。

由于四大名著的魅力实在是太大了，JM决定把整个3月空出来，再次品味一下这四大名著。

JM 决定在3月的31天中挑出连续的4天学习《水浒传》，连续的3天看《西游记》，连续的5天看《三国演义》，连续的3天看《红楼梦》。注意：同一天不可能看两本名著。

现在，JM同学想知道，他有多少种时间安排方法，能够满足他学习的需求。

例如：

第1-5天看《三国演义》，第6-8天看《西游记》，第9-11天看《红楼梦》，第12-15天看《水浒传》，这是一种合法的方案
第2-5天看《水浒传》，第10-14天看《三国演义》，第17-19天看《西游记》，第29-31天看《红楼梦》，这也是一种合法的方案。

思路:

我们通过枚举每一个名著的开始阅读时间，然后判断这种可能方案，满不满足要求。
也就是每一本名著读书的那天，不能读其他的。
我们可以用一个变量 vis，记录每一天是否已经读过了

'''
我们通过枚举每一个名著的开始阅读时间，然后判断这种可能方案，满不满足要求。也就是每一本名著读书的那天，不能读其他的。
我们可以用一个变量 vis，记录每一天是否已经读过了
'''

def is_True(a,b,c,d):
    vis = [0 for _ in range(32)]
    for i in range(4):
        vis[a+i] = 1
    for i in range(3):
        if vis[b+i] != 1:
            vis[b+i] = 1
        else:
            return False
    for i in range(5):
        if vis[c + i] != 1:
            vis[c + i] = 1
        else:
            return False
    for i in range(3):
        if vis[d + i] != 1:
            vis[d + i] = 1
        else:
            return False
    return True
if __name__ == '__main__':
    # a = 《水浒传》 4天
    # b = 《西游记》 3天
    # c = 《三国演义》 5天
    # d = 《红楼梦》 3天
    ans = 0
    for a in range(1, 29): # 第28天为最晚读书日期
        for b in range(1, 30):# 第29天为最晚读书日期
            for c in range(1, 28):# 第27天为最晚读书日期
                for d in range(1, 30):# 第28天为最晚读书日期
                    if is_True(a,b,c,d):
                        ans += 1

    print(ans)

D. 试题D：抽刀断水水更流，举杯销愁愁更愁 10’

忧郁的JM，借酒消愁。略微喝醉的他，和下酒花生聊起了天。

JM：“你知道质数是什么吗？”

花生：“……”

JM：“质数是指在大于11的自然数中，除了11和它本身以外不再有其他因数的自然数。”

花生：“……”

JM：“现在我有一个质数集合{3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 41, 53, 59, 61, 67, 71, 97, 101, 127, 197, 211, 431}3,5,7,11,13,19,23,29,31,37,41,53,59,61,67,71,97,101,127,197,211,431，你可以从中挑出任意多个(0-12个)不同的数出来构成一个新数（取出数的和）”

JM：“构成的新数从小到大依次为：0, 3, 5, 7, 8, 10, 11, 12, 13…，0,3,5,7,8,10,11,12,13…，你知道[0, 1694][0,1694]中有多少个数是没法构成的吗？”
花生：”……“

JM：“例如：1，2，4…1，2，4…均是不能够从质数集合中挑数构成”

你来帮帮花生吧~

思路:

这道题乍一看很简单,但是写代码的时候思路总是理不清楚
上网查了一下发现这道题可以用二进制枚举的方法
总共 22 个数，选择其中的 0 -12 个数，加上来组成一个新数。

我们可以用二进制枚举，对于 22 个数，每一个数，只有拿或不拿两种情况，也就是 0 或者 1。所以总共有 2 ^ 22 约等于 4e6。不会超时。

因为我们用二进制枚举，每一位对应这个数要不要取，如果取，那就累和。还要注意，最后只能取 12 个，所以我们要判断，这种取法中 1 的个数，如果是 >12 ，那这种方案不成立。

然后算出所有情况的数，用 set 统计（可能有重复的，去重）。

最后答案是问，无法构成的个数，因此答案是 ： 总数（1695） - set 中的数（可以构成了这么多数）

具体可以参考我的这篇博客:Python算法学习:全排列的回溯实现与二进制枚举

nums = [3,5,7,11,13,19,23,29,31,37,41,53,59,61,67,71,97,101,127,197,211,431]
ans = [] #存放所有答案

for i in range(1<<22): # 2^22-1种情况(这里是取0或者取22个数的全部可能情况)
    cnt = 0 # 计数 控制取数不超过12
    res = 0 # 结果
    tmp = i
    for j in range(22): # 查看22位中都有哪一位放了数字,即是1
        if (tmp >> j) & 1: # 如果第j位是1,则符合
            cnt += 1
            res += nums[j]
        if cnt <= 12:    # 不超过12位
            ans.append(res)
ans = set(ans)         # 使用集合的特性,去重
cnt = 1695
print(ans)
print(cnt - len(ans))