第一周作业(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