文章目录
- 前言
- 分解质因数
-
- 问题描述
- 问题分析
- 代码实现
- 龟兔赛跑
-
- 问题描述
- 问题分析
- 代码实现
- 时间转换
-
- 问题描述
- 问题分析
- 代码实现
- 完美的代价
-
- 问题描述
- 问题分析
- 代码实现
- 芯片测试
-
- 问题描述
- 问题分析
- 代码实现
前言
今天分享的几道算法题难度适中,有的涉及到字符串处理，有的涉及到矩阵计算、有的涉及到数学相关的知识。相对来说实现起来还是很容易的。
分解质因数（将给定区间的数分解为质因数相乘的形式）
龟兔赛跑（小学数学知识,进行模拟即可）
时间转换（将以秒为单位的数转换为时间）
完美的代价（统计字符串转换为回文串至少交换几次）
芯片测试（有点离散数学的味道）
分解质因数 问题描述
问题描述问题分析
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000
先找出输入区间的所有的质数.然后遍历输入的区间,将其分解的结果以字符串的形式进行进行拼凑代码实现
加入到结果链表中,第一个因数直接加进去,后来的加上*加进去。如果没有质因数可以分解，就选定
数本身加进去。
老规矩先上运行结果：
文章图片
这里需要注意的是字符串的join方法如果加入参数的是字符串的话会对所加入的字符串进行迭代
会使字符串乱序,所以我们使用了+直接对字符串进行拼接。
# 判断是不是素数
from math import sqrtdef judge(n):
flag=True
for j in range(2,int(sqrt(n))+1):
if n%j==0:
flag=False
return flagans=[]
a,b=map(int,input().split())
ta=[]
for i in range(2,b+1):
if judge(i):
ta.append(i)print(ta)for k in range(a,b+1):
flag=True
temp=""
tk=k
while k:
for t in ta:
if k%t==0 and flag:
flag=False
temp=f"{k}={t}"
# print("temp1--->",temp)
k/=t
break
elif k%t==0:
# temp=temp.join(f"*{t}")
temp+=f"*{t}"
# print("temp2--->",temp)
k/=t
break
else:
break
if k==tk:
ans.append(f"{k}={k}")
else:
ans.append(temp)
for i in ans:
print(i)
龟兔赛跑 问题描述
问题描述问题分析
话说这个世界上有各种各样的兔子和乌龟，但是 研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。
于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。
他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，
它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1
（表示每秒兔子能跑v1 米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。
但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找 到了你——清华大学计算机系的高才生——请求帮助，
请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。
输入格式
输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100; t<=300; s<=10; l<=10000且为v1,v2的公倍数)
输出格式
输出包含两行，第一行输出比赛结果一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。
第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。
样例输入
10 5 5 2 20
样例输出
D
4
样例输入
10 5 5 1 20
样例输出
R
3
样例输入
10 5 5 3 20
样例输出
T
4
使用枚举法,进行枚举，以循环变量作为秒数,每轮循环代表一秒,乌龟每次都会移动,而兔子只会在特定的情况下移动,并且每达到一定距离差异就会使兔子无法移动,直到解除。所以我们可以定义一个变量记录兔子还有几秒开始移动,如果标记为0的话兔子就可以移动,循环终止条件是兔子乌龟任意一方通过终点,或者双方同时通过终点。代码实现
老规矩先上运行结果：
文章图片
# 键入五个数据（兔子、乌龟、兔子休息距离、兔子休息间隔、赛道长度）
v1,v2,t,s,l=map(int,input().split())# 兔子与乌龟的距离
x1,x2=0,0# 记录兔子是否有冷确时间
cd=0# 总时间
tim=0
while x1=t and cd==0:
cd=s
tim+=1
if x1>x2:
print("R")
elif x1 时间转换 问题描述
问题描述问题分析
给定一个以秒为单位的时间t，要求用 ::的格式来表示这个时间。表示时间， 表示分钟， 而表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。
输入格式
输入只有一行，是一个整数t（0<=t<=86399）。
输出格式
输出只有一行，是以“::”的格式所表示的时间，不包括引号。
样例输入
0
样例输出
0:0:0
样例输入
5436
样例输出
1:30:36
将时间的时分秒分别相成数值中的百十个位,对秒数进行取余,分别得到每一位上的数值代码实现
得到之后进行取整，再去获取高位。
老规矩先上运行结果：
文章图片
n=int(input())
# 时
h=0
# 分
m=0
# 秒
s=0s=n%60
n=n//60
m=n%60
n=n//60
h=n%60
print(f"{h}:{m}:{s}")
完美的代价 问题描述
问题描述问题分析
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
如果将其可以转换为回文串，那么字符串中的奇数个字母必定小于等于1个,否则将无法对称代码实现
在进行交换的时候保持一边不动,移动另一边。可以使用贪心策略,每次都选出一对字符进行弹出
如果有一个字符没有匹配到,就将他到中间位置的距离记录下来,然后设置一个标记位,如果再有一次没有匹配到证明不符合规则,就进行Impossible打印。
老规矩先上运行结果：
文章图片
# 接收输入的字符串长度
n=int(input())
# 接收输入的字符串
mystr=list(input())# 记录结果
ans=0
# 标记位,出现两次匹配不到的情况就打印IM
flag=False
while len(mystr)>1:
for i in range(len(mystr)-1,0,-1):
if mystr[0]==mystr[i]:
mystr.pop(0)
ans+=(len(mystr)-i)
mystr.pop(i-1)
break
elif i==1:
mystr.pop(0)
if n%2==0 or flag:
print("Impossible")
exit(0)
flag=True
ans += len(mystr)//2
print(ans)
芯片测试 问题描述
问题描述问题分析
有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。
输入格式
输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本 身进行测试）。
输出格式
按从小到大的顺序输出所有好芯片的编号
问题分析：
由于好的芯片比坏的芯片多,所以在进行坏芯片给自己的的测试是好坏随机
所以可以得出,如果一个芯片是坏的那么这个芯片对应的测试中0的个数必定大于1的个数
也可以理解为好的芯片经过测试1的个数大于0的个数
样例输入
3
1 0 1
0 1 0
1 0 1
样例输出
1 3
题目给出好芯片的个数多,那么对于一个芯片而言如果证明他的好的指标大于芯片数一半的时候代码实现
他就是一个好的芯片.以这一条逻辑统计每一个芯片好指标的个数,然后判断好坏。
老规矩先上运行结果：
文章图片
文章图片
n=int(input())
# 存储好芯片的个数
ans=[]
ls=[list(map(int,input().split())) for x in range(n)]ls=list(zip(*ls))[::][::]
k=1
for i in ls:
if sum(i)>n/2:
ans.append(k)
k+=1flag=True
for i in ans:
if flag:
flag=False
print(i,end="")else:
print(f" {i}",end="")
【Python从入门到精通|【Python 百练成钢】分解质因数、龟兔赛跑、时间转换、完美的代价、芯片测试】
文章图片
推荐阅读
- Python从入门到精通|【Python 百练成钢】卡片游戏、铁轨问题、移动小球
- Python从入门到精通|【Python 百练成钢】高精度加法、阶乘计算、矩阵幂运算、矩阵面积交
- 算法|「推荐系统中的特征工程」02（推荐系统与特征工程）
- 计算机组成原理学习------第四章数据运算
- milvus|PaddleRec与Milvus深度结合，手把手带你体验工业级推荐系统召回速度
- 搞笑整活系列|Python基础-“百钱百鸡”入门逻辑题（刚开始的建议藏起来）
- 蓝桥杯|蓝桥python——玩具蛇
- 蓝桥杯|蓝桥python——方格分割【2017 第四题】
- CTF|2021DASCTF八月挑战赛Writeup