【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业

第一周作业(Python描述)

1.跑步训练

问题描述:

小明要做一个跑步训练,初始时,小明充满体力,体力值计为 10000。

如果小明跑步,每分钟损耗 600 的体力。
如果小明休息,每分钟增加 300 的体力。
体力的损耗和增加都是 均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。

如果某个时刻小明的体力到达 0,他就停止锻炼,请问小明在多久后停止锻炼。

为了使答案为整数,请以秒为单位输出答案,答案中只填写数,不填写单位。

答案提交:

这是一道结果填空题,你只需要算出结果后提交即可。
本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

题解:

思路:

1.结束条件:体力 = 0。
2.时间累加。体力按照状态进行计算。
3.由于结果单位为秒,记得换算。

代码:

虽然这是一道结果填空题,但是既然是作业,我们不妨用代码来解决

# encoding:utf-8
# @Author  : fyl

time = 0
power = 10000
while power > 0:
	time += 1
    if time % 2 == 0:# 判断 过去的1分钟内的状态
    	power += 300
    else:
        power -= 600
if power == 0:
	time = time*60
else:
	 #最后1分钟一定是跑步 有可能导致power会小于0 
	time = (time-1)*60 + ((power+600)/600)*60  #补齐最后1分钟power按比例换算成秒。
    time = int(time) #因为本题结果只写这个整数 所以进行类型转换
    
print(time)

运行结果:3880

总结:

该题有一小陷阱:就是最后一分钟跑步结束后,power为负值, 即power经过整分钟的运动后,不能正好减到0。我们要将最后一分钟单独计算。

2.阶乘约数

问题描述:

定义阶乘 n! = 1 × 2 × 3 × ··· × n。
请问 100! (100 的阶乘)有多少个约数。

答案提交:

这是一道结果填空的题,你只需要算出结果后提交即可。
本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

题解:

思路:

100! 是个超巨大的数,暴力求解肯定是行不通。我们可以先将1~100 分别做因数分解,这些因数累乘起来,得到100!的因数分解。

约数个数:
任意一个大于 1 的正整数 n 可以分解质因数:p1a1p2a2pkak
其中pi为两两不同的素数,ai为对应指数,则n的约数个数为(a1+1)
(a2+1)(ak+1)

代码:

# encoding:utf-8
# @Author  : fyl

dic={}
for i in range(2,101): #字典dic用于统计 这100个数的因子数量 初始化值为0
	dic[i] = 0
for i in range(2,101): #循环2~100 求他们的质因子 并统计数量
    n=i
    while n!=1:
    	for p in range(2,n+1):
        	if n % p == 0:
            	dic[p]+=1
                n = n//p
                break                     
res = 1 
for k in arr.keys(): #约数个数为(a~1~+1)*(a~2~+1)*....*(a~k~+1)
        res *= dic[k]+1
print(res)

运行结果:39001250856960000

总结:

该题涉及到统计数量,需要用到字典进行统计。还要有一定的约数方面的数学知识。

3.出栈次序

问题描述:

X星球特别讲究秩序,所有道路都是单行线。
一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。
路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。
X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。
那么,该车队再次上路后,可能的次序有多少种?
为了方便起见,假设检查站可容纳任意数量的汽车。
显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
现在足足有16辆车啊,亲!需要你计算出可能次序的数目。
【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业

答案提交:

这是一个整数,请通过浏览器提交答案,不要填写任何多余的内容(比如说明性文字)。

题解:

思路:

采用递归,递归分三种情况考虑
1.当车道左边没车,不管这时检查站里面有没有车,都只有一种次序,此为基线条件 return 1。
2.当左边有车,检查站里面没车,按照题目要求,每辆车都必须要进检查站,所以左边车的数量 - 1,检查站内车的数量 + 1 return f (n-1,1)。
3.如果检查站里面有车,这种情况下的方案数是两个递归的和,这两个递归分别对应的情况是:左边再来一辆车进站和从检查站出去一辆车 return f (n - 1,m + 1) + f (n,m - 1)。

代码:

# encoding:utf-8

def fun(n,m):#n为左边车的数量,m为检查站的中的数量 
	if n == 0:#如果左边没车 
		return 1
    if m == 0:#如果检查站没车,就要入站 
        return fun(n-1,1)
    if m > 0:#如果检查站有车 
    #分两种情况:1.左边再来一辆车进站 2.检查站出去一辆车 
        return fun(n-1,m+1) + fun(n,m-1)

print(fun(16,0))

参考链接:https://blog.csdn.net/qq_45281807/article/details/104221946

另一种解法思路:出栈次序数目为卡特兰数,满足一个递推公式:h1=1;hn=hn-1(4n-2)/(n+1).其中n表示数的个数。

# encoding:utf-8
ans = 1
for x in range(1, 17):
    ans = ans*(4*x-2)/(x+1)
print(ans)

参考链接:https://blog.csdn.net/milk_paramecium/article/details/113893758

运行结果:35357670

总结:

使用递归方法 一定要找好基线条件和递归条件。

4.哥德巴赫分解

问题描述:

【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业

题解:

思路:

每个偶数分解为两个素数,只要最小的那个,再在这个范围中找出最大的。本题的偶数范围为10000以内。

代码:

# encoding:utf-8
x = []
def Split_even(n):#定义分解偶数的函数
    def IsPrime(num): #判断num是否为素数
        if num == 2:
            return True
        for i in range(2,num):
            if num % i == 0:
                return False
        return True

    for j in range(2, n // 2 + 1):
        if IsPrime(j) and IsPrime(n - j):#判断这两个数是否素数 
            return [j,n-j]# 都是 则将这两个素数返回
            
for i in range(4,10001,2):
    x.append(min(Split_even(i)))#把分解的两个质数中最小的数 添加到x列表中
print(max(x))#打印列表中最大元素

运行结果:173

5.图书排列

问题描述:

将编号为1~10的10本书排放在书架上,要求编号相邻的书不能放在相邻的位置。
请计算一共有多少种不同的排列方案。

答案提交:

需要提交的是一个整数,不要填写任何多余的内容。

题解:

思路:

1.找出所有排列可能(全排列)。

列表有n个元素,将第一个元素固定,对剩下n - 1个元素进行全排列。
将第一个元素依此与其他元素交换,对每次交换后剩下的n-1个元素进行全排列。
剩下的n - 1个元素全排列,同上,固定后对n - 2排列。
直到数组数量为1,全排列就是它自己,完成一次排列。

2.然后判断这些排列 是否符合”编号相邻的书不在相邻的位置”,把符合的排列计数。

代码:

# encoding:utf-8
res = 0
def check(book):#检查是否符合”编号相邻的书不在相邻的位置” 并计数
    for i in range(9):
        if abs(book[i]-book[i+1]) == 1:
            return False
    return True

def Full_Perm(book, begin, end):
    global res#函数内部对函数外部的变量进行操作 要用global声明
    if begin == end:#递归结束条件,当交换到最后一个元素的时候不需要再交换了,这次排列完成。
        if check(book):
            res += 1
            return
    else:
        j = begin
        for i in range(begin, end):#从begin到end全排列
            book[i],book[j] = book[j],book[i]#交换
            Full_Perm(book, begin+1, end)# 交换后对剩下数组进行全排列。[begin + 1, end]
            book[i],book[j] = book[j],book[i] #还原到交换前的状态,为了进行下一次交换 
            
book = [i for i in range(1, 11)]
Full_Perm(book, 0, len(book))
print(res)

运行结果:479306

总结:

该题关键点是写出 实现全排列的递归函数。
Python itertools库有实现全排列的函数。

# encoding:utf-8
import itertools
s = ['a','b','c']
for i in itertools.permutations(s):
	print(i)

6.猴子分香蕉

问题描述:

【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业

题解:

思路:

代码:

# encoding:utf-8
n=6#设置 第一只猴子醒来看到的香蕉数量 初始值 至少为6
a=b=c=d=0
while True:
    if(n%5==1):#满足第一只猴子均分香蕉还剩一个的条件
        a=(n-1)/5*4#第二只猴子醒来时看到的香蕉的数量
        if(a%5==2):
            b=(a-2)/5*4#第三只猴子醒来时看到的香蕉的数量
            if(b%5==3):
                c=(b-3)/5*4#第四只猴子醒来时看到的香蕉的数量
                if(c%5==4):
                    d=(c-4)/5*4#第五只猴子醒来时看到的香蕉的数量          
                    if(d%5==0 and d!=0):#判断是否满足第五只猴子均分香蕉刚好分完的条件
                        print(n)
                        break
                                                                       
    n+=1 

参考链接:https://blog.csdn.net/qq_40871196/article/details/86690969

总结:

没有想出怎么用递归方法求解。好像用不了递归吧,

7.稍小分数

问题描述:

回到小学----
真分数:分子小于分母的分数
既约分数:分子分母互质,也就是说最大公约数是1
x星球数学城的入口验证方式是:
屏幕上显示一个真分数,需要你快速地找到一个比它小的既约分数,要求这个分数越大越好。
同时限定你的这个分数的分母不能超过100。

题解:

思路:

代码:

# encoding:utf-8
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)	

#这是屏幕上显示的那个分数 a/b	
a = 7
b = 13
max_a = 0
max_b = 1

for n in range(100,1,-1):
    for m in range(n-1,0,-1):
        if (m*b<a*n) and (gcd(m,n) == 1):
            if max_a*n < max_b*m:
                max_a = m
                max_b = n
                break		    	
print("%d/%d"%(max_a, max_b))	            

总结:

该题在蓝桥杯原题中是一道填空题。由于作业中未指定输入格式,所以无法控制输入,直接复制了原题。

8.excel 地址

问题描述:

时间限制:1.0s 内存限制:256.0MB

问题描述:

Excel单元格的地址表示很有趣,它使用字母来表示列号。
  比如,
  A表示第1列,
  B表示第2列,
  Z表示第26列,
  AA表示第27列,
  AB表示第28列,
  BA表示第53列,
  …
  当然Excel的最大列号是有限度的,所以转换起来不难。
  如果我们想把这种表示法一般化,可以把很大的数字转换为很长的字母序列呢?
  本题目即是要求对输入的数字, 输出其对应的Excel地址表示方式。

样例输入
26
样例输出
Z

样例输入
2054
样例输出
BZZ

数据规模和约定
我们约定,输入的整数范围[1,2147483647]
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。
提交程序时,注意选择所期望的语言类型和编译器类型。

题解:

思路:

该题类似于10进制转换为26进制,但仅仅是类似。我们用循环取余即可解决。

代码:

# encoding:utf-8
n = int(input()) 
ans = []
while n!= 0:
    if n % 26 == 0:
        ans.append(26)
        n = n // 26 - 1 #这里需要-1
    else:
        ans.append(n%26)
        n = n // 26
for i in range(len(ans)):
	#加64把数字转化成字符,且是从列表最后向前打印
    print(chr(ans[len(ans)-i-1]+64), end='')

参考链接:https://blog.csdn.net/qq_43604482/article/details/105825981

总结:

该题要注意,他并不是真正的26进制,如在26,52这也的点上是Z和AZ。并没有像真正的进制一样,已经进位,而是需要再加1完成进位。所以在26的倍数结点上要减去一次进位。

9.日期问题

问题描述:

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入
一个日期,格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

输出
输出若干个不相同的日期,每个日期一行,格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

样例输入
02/03/04

样例输出
2002-03-04
2004-02-03
2004-03-02

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

题解:

思路:

将不满足的情况考虑全面,最后要排序,去重。

代码:

# encoding:utf-8
data = list(map(int, input().split("/")))
res = []


def isLeapYear(year):
    if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0:
        return True
    else:
        return False

def fun(x, y, z):  # 默认年月日
    
    if 0<=x<=59:   #讨论年份
        x += 2000
    elif 60<=x<=99:
        x += 1900
                
    if y <= 0 or y > 12:#讨论月份
        return False
    
    if z <= 0 or z > 31:#讨论日
        return False
    if isLeapYear(x) and y == 2 and z > 29:
        return False
    if isLeapYear(x) == False and y == 2 and z > 28:
        return False
    if y in [4,6,9,11] and z > 30:
        return False
    else:
        if y < 10:
            y = str(0) + str(y)
        if z < 10:
            z = str(0) + str(z)
        res.append(str(x) + "-" + str(y) + '-' + str(z))
        return

fun(data[0], data[1], data[2])#a[0]为年 a[1]为月 a[2]为日
fun(data[2], data[0], data[1])#a[0]为月 a[1]为日 a[2]为年
fun(data[2], data[1], data[0])#a[0]为日 a[1]为月 a[2]为年
for i in sorted(list(set(res))):
    print(i)

参考链接:https://blog.csdn.net/bianxia123456/article/details/106816421

总结:

10.整数划分

问题描述:

对于一个正整数n的划分,就是把n变成一系列正整数之和的表达式。注意,分划与顺序无关,例如6=5+1.跟6=1+5是同一种分划,另外,这个整数本身也是一种分划。
例如:对于正整数n=5,可以划分为:
1+1+1+1+1
1+1+1+2
1+1+3
1+2+2
2+3
1+4
5
输入描述
输入一个正整数n

输出描述
输出n整数划分的总数k

输入样例
5

输出样例
7

题解:

思路:

把上述每种数字定义为6的划分因子,可知,6有6种划分因子,每种都有可能组成6。于是可以用一个for循环来依次遍历划分因子。比如从1开始,1是第一位组成6的数,那么还剩rest = 6-1.再对rest进行同样分析,也就是递归。递归终止条件为当rest = 0时,6被分完了,就输出。此时需要一个数据结构来存储合适的划分因子,从这里遍历输出。最后,为了去重,在递归后回溯时,加个if判断,规定满足:在数据结构里存储的划分因子,当要存储新的划分因子之前,判断该划分因子比上一位(下标-1)不小于时才能允许存入。

代码:

# 用python字典这个数据结构存储划分因子,从1开始,用0占位
dividing_number = {0: 0}
# 次数累加变量
times = 0

def int_divide(number, index):
    global times
    # 从1开始遍历该整数所有划分因子
    for i in range(1, number+1):
        # 与前一位划分因子比较,去重,如先有24,42则不行
        if i >= dividing_number[index-1]:
            dividing_number[index] = i
            # 当前数-划分因子后还剩数,如6-1剩5
            number_rest = number - i
            # 整数被划分完毕
            if number_rest == 0:
                # 输出划分因子
                for j in range(1, index):
                    print(str(dividing_number[j])+'+', end='')
                print(str(dividing_number[index]))
                times = times + 1
            # 未被划分完毕,继续,dividing_Number划分位数+1
            else:
                int_divide(number_rest, index+1)
        else:
            pass
            
n = int(input("请输入一个整数\n"))
int_divide(n, 1)
print("所以该整数的划分数为:%d" % times)

参考链接:https://blog.csdn.net/qq_42980666/article/details/105037553

总结:

该题巧妙的运用递归求解,既完成因子划分同时避免重复 思路很好,学习了。

11.一步之遥

问题描述:

从昏迷中醒来,小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮,分别写着“F”和“B”。

小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。
按F,会前进97米。按B会后退127米。
透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方,才有机会争取同伴的援助。
或许,通过多次操作F和B可以办到。

矿车上的动力已经不太足,黄色的警示灯在默默闪烁…
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算,至少要多少次操作,才能把矿车准确地停在前方1米远的地方。

请填写为了达成目标,最少需要操作的次数。

注意,需要提交的是一个整数,不要填写任何无关内容(比如:解释说明等

题解:

思路:

根据题意可列出方程:97x - 127y = 1 通过暴力枚举即可求出答案

代码:

# encoding:utf-8
for x in range(0,1000):
    for y in range(0,1000):
        if 97 * x - 127 * y == 1:
            print(x + y)
            break
    else:
        continue
    break
            

总结:

可以把枚举的范围写大一些,利用for-else语句 跳出双层循环。也可以设置一个全局变量flag跳出多层循环如:

# encoding:utf-8
flag = False
for x in range(0,1000):
    for y in range(0,1000):
        if 97 * x - 127 * y == 1:
            print(x + y)
            flag = True
            break
    if flag:
    	break          

12.机器人塔

问题描述:

X星球的机器人表演拉拉队有两种服装,A和B。
他们这次表演的是搭机器人塔。

类似:

A
B B
A B A
A A B B
B B B A B
A B A B B A

队内的组塔规则是:

A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下,在给定A与B的人数时,可以组成多少种花样的塔。

输入一行两个整数 M 和 N,空格分开(0<M,N<500),分别表示A、B的人数,保证人数合理性。

要求输出一个整数,表示可以产生的花样种数。

例如:
用户输入:
1 2

程序应该输出:
3

再例如:
用户输入:
3 3

程序应该输出:
4

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms

题解:

思路:

cnt = num*(num+1)/2 = M+N,所以 num = sqrt((M + N) * 2)
接下来就是来寻找底层了,然后再查看是否可以向上扩展,A,B的数目是否足够使用。
这里遍历所有第一行的选项,我们使用递归的方式,同时用1表示A,2表示B。
然后设置一个检查代码,从而行开始计算所有的A,B,个数如果到了顶层还是和m,n相同,说明是可行的。

代码:

# encoding:utf-8
import math

def check():# 判断是否可以向上拓展
    a = 0
    b = 0
    tmp = row
    while tmp >0:
        for i in range(1, tmp+1):
            if cnt[i] == 1:
                a +=1
            else:
                b += 1
        for i in range(2, tmp+1):
            if cnt[i-1]==cnt[i]:
                cnt[i-1] = 1
            else:
                cnt[i-1] = 2
        tmp -=1
    if a == m and b == n:
        return True
    else:
        return False

def dfs(k):# 遍历所有底层
    global res
    if k > row:
        if check():
            res +=1
        return
    cnt[k] = 1
    dfs(k+1)
    cnt[k] = 2
    dfs(k+1)

if __name__ == "__main__":
    m = int(input())
    n = int(input())
    res = 0
    cnt = [0 for _ in range(100010)]
    row = int(math.sqrt(2*(m+n)))
    dfs(1)
    print(res)

参考链接:https://blog.csdn.net/zznnniuu/article/details/122352199

13.七星填空

问题描述:

如下图所示。在七角星的 14 个节点上填入 1 ~ 14的数字,不重复,不遗漏。 要求每条直线上的四个数字之和必须相等。
图片描述
【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业

图中已经给出了 3 个数字。 请计算其它位置要填充的数字,答案唯一。
填好后,请输出绿色节点的 4 个数字(从左到右,用空格分开)。

题解:

思路:

利用python全排列函数遍历所有。在图上写好下标,利用if语句进行七条线的判断。

代码:

# encoding:utf-8
import itertools
for i in itertools.permutations([1,2,3,4,5,7,8,9,10,12,13]):
  num=i[0]+i[1]+i[2]+i[3]
  if num==i[3]+i[5]+i[7]+i[10]:
    if num==i[10]+i[9]+i[6]+14:
      if num==14+i[4]+i[1]+6:
        if num==6+i[2]+i[5]+11:
          if num==11+i[7]+i[9]+i[8]:
            if num==i[8]+i[6]+i[4]+i[0]:
              print(i[0],i[1],i[2],i[3])
              break

运行结果:10 3 9 8

上一篇:Photoshop为秋季山坡上的美女加上暖暖的黄蓝色


下一篇:Photoshop制作中国加油奥运福娃动画