【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业
2022/1/8 22:05:29
本文主要是介绍【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
第一周作业（Python描述）
- 1.跑步训练
- 问题描述:
- 答案提交:
- 题解:
- 思路：
- 代码：
- 总结：
- 2.阶乘约数
- 问题描述:
- 答案提交:
- 题解：
- 思路：
- 代码：
- 总结:
- 3.出栈次序
- 问题描述:
- 答案提交:
- 题解：
- 思路：
- 代码：
- 总结:
- 4.哥德巴赫分解
- 问题描述:
- 题解：
- 思路：
- 代码：
- 5.图书排列
- 问题描述:
- 答案提交:
- 题解：
- 思路：
- 代码：
- 总结:
- 6.猴子分香蕉
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 7.稍小分数
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 8.excel 地址
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 9.日期问题
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 10.整数划分
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 11.一步之遥
- 问题描述:
- 题解：
- 思路：
- 代码：
- 总结:
- 12.机器人塔
- 问题描述:
- 题解：
- 思路：
- 代码：
- 13.七星填空
- 问题描述:
- 题解：
- 思路：
- 代码：
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 可以分解质因数：p1a1p2a2…pkak
其中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.当车道左边没车，不管这时检查站里面有没有车，都只有一种次序，此为基线条件 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.哥德巴赫分解
问题描述:
题解：
思路：
每个偶数分解为两个素数，只要最小的那个，再在这个范围中找出最大的。本题的偶数范围为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.猴子分香蕉
问题描述:
题解：
思路：
代码：
# 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的数字，不重复，不遗漏。 要求每条直线上的四个数字之和必须相等。
图片描述
图中已经给出了 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
这篇关于【蓝桥杯】【思特奇杯·云上蓝桥-算法集训营】第1周作业的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-27OpenFeign服务间调用学习入门
- 2024-12-27OpenFeign服务间调用学习入门
- 2024-12-27OpenFeign学习入门：轻松掌握微服务通信
- 2024-12-27OpenFeign学习入门：轻松掌握微服务间的HTTP请求
- 2024-12-27JDK17新特性学习入门：简洁教程带你轻松上手
- 2024-12-27JMeter传递token学习入门教程
- 2024-12-27JMeter压测学习入门指南
- 2024-12-27JWT单点登录学习入门指南
- 2024-12-27JWT单点登录原理学习入门
- 2024-12-27JWT单点登录原理学习入门
