Python经典编程题40题（二）
题目
给你一个list L, 如 L=[2,8,3,50], 对L进行降序排序并输出, 如样例L的结果为[50,8,3,2]
输入示例
输入：L = [4, 2, 25, 7777777, 100, 3, 77777777, 77777777, 77777777, 77777777]
输出示例
输出：[77777777, 77777777, 77777777, 77777777, 7777777, 100, 25, 4, 3, 2]
算法
sort方法（会覆盖原函数），这道题要设置reverse进行倒序排序
L = [4, 2, 25, 7777777, 100,
3, 77777777, 77777777, 77777777, 77777777]
L.sort(reverse=True)
print(L)第22题：买苹果
题目
小明的妈妈买了N个苹果，想把它们都分给她的M个孩子。为了公平起见， 她想让所有的孩子都分到一样多的苹果。那么她至少要再买多少个苹果呢？ 如：N=3, M=1, 则输出0 N=3，M=2，则输出1
输入示例
输入：N = 3 M = 1
输出示例
输出：0
算法
分情况，若刚好够分，则直接输出0，否则，用总共需要购买的苹果树减去N（已经有的苹果数）
N = 3
M = 1
if N%M==0:
print('0')
else:
print(M*(N//M+1)-N)第23题：Py扔铅球
题目
Py不但是编程大牛，而且是运动健将。比如说扔铅球，1000m，现在Py参加校园扔铅球比赛， 给你Py的身高a（双精度数），球落地点与Py头部的连线与水平线的夹角 b（弧度）， 要你编写一个程序计算Py扔铅球的水平距离。 a，b都是浮点数，注意b是弧度，其中， 140 < a < 200, 0 < b < 1.5. 输出你求出的水平距离，保留到小数点后三位。 如，a = 165.5, b=1.1, 则输出84.234
输入示例
输入：a = 165.5 b = 1.1
输出示例
输出：84.234
算法
利用math里面的tan函数，注意tan函数输入的值是弧度值，根据tan的定义，
身高/水平距离=tan(b)，可以反解出水平距离
import math
a = 165.5
b = 1.1
print('%.3f'%(a/math.tan(b)))第24题：回文数 I
题目
若一个数（首位不为0）从左到右读与从右到左读都是一样，这个数就叫做回文数，例如12521就是一个回文数。 给定一个正整数，把它的每一个位上的数字倒过来排列组成一个新数，然后与原数相加，如果是回文数则停止，如果不是，则重复这个操作，直到和为回文数为止。给定的数本身不为回文数。 例如：87则有： STEP1: 87+78=165 STEP2: 165+561=726 STEP3: 726+627=1353 STEP4: 1353+3531=4884 现在给你一个正整数M（12 <= M <= 100),输出最少经过几步可以得到回文数。如果在8步以内（含8步）不可能得到回文数，则输出0。 例如：M=87，则输出4.
输入示例
输入：M = 12
输出示例
输出：1
算法
回文数的判断+while循环的使用，代码很简单，只是看起来长了点
def is_huiwen(x):
y=str(x)
y_reverse=y[::-1]
if y==y_reverse:
return True
else:
return False
M=12
times=0
while is_huiwen(M)==False:
times+=1
M_re=int(str(M)[::-1]) #先将M转成字符串，再翻转，再转成数字
M+=M_re
if times<=8:
print(times)
else:
print('0')
#输出1第25题：数数
题目
给你一个正整数n(0 < n < 1000000), 请你输出0到n之间“1”出现的次数。 例如 n = 4时， [1, 2, 3, 4]出现了1个"1",因此输出1 n = 12时，[1,2,3,4,5,6,7,8,9,10,11,12]出现了5个"1"， 因此输出5
输入示例
输入：n = 3
输出示例
输出：1
算法
找1，然后计数
n=11
ans=0
def find_1(x): #找一个数中含1的个数
times_1=0
while x!=0:
if x%10==1:
times_1+=1
x//=10
return times_1
for i in range(1,n+1):
ans+=find_1(i)
print(ans)第26题：再谈数数
题目
给定两个正整数a, b (1<=a <= b<=10^5), 请你数出在a到b之间，十个阿拉伯数字分别出现了多少次。比如，当a=11, b=20时，a和b之间的数有[11,12,13,14,15,16,17,18,19,20]，那么0-9这10个数出现的次数分别是1,10,2,1,1,1,1,1,1,1。现在给你a和b，请你输出十个阿拉伯数字分别出现的次数；分十行输出，第一行表示0出现的次数，第二行表示1出现的次数，....,最后一行表示9出现的次数。
输入示例
输入：a = 11 b = 20
输出示例
输出：1, 10, 2, 1, 1, 1, 1, 1, 1, 1 (按行输出)
算法
利用一个列表来存储答案，根据下标进行索引
a = 11
b = 20
ans=[0 for i in range(10)] #构造全0列表，作为答案的存储载体
for i in range(a,b+1):
while i!=0: #算每个位数出现
ans[i%10]+=1
i//=10
for i in ans:
print(i)第27题：Py数
题目
Py从小喜欢奇特的东西，而且天生对数字特别敏感，一次偶然的机会，他发现了一个有趣的四位数2992， 这个数，它的十进制数表示，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22， 同时它的十二进制数表示1894，其四位数字之和也为22，啊哈，真是巧啊。 Py非常喜欢这种四位数，由于他的发现，所以这里我们命名其为Py数。 现在给你一个十进制4位数n，你来判断n是不是Py数，若是，则输出Yes，否则输出No。
输入示例
输入：n = 1234
输出示例
输出：No
算法
分别计算其十进制、十二进制和十六进制下的各数字之和，然后再比较即可
n=1234
def get_10(n):
he=0
while n!=0:
he+=n%10
n//=10
return he
def get_16(n):
he=0
while n!=0:
he+=n%16
n//=16
return he
def get_12(n):
he=0
while n!=0:
he+=n%12
n//=12
return he
if get_10(n)==get_12(n) and get_12(n)==get_16(n):
print('Yes')
else:
print('No')
#No第28题：考古学家的困境
题目
一个考古学家正在发掘古代的一座城市时，不小心被一个部分毁坏的石墙绊倒了。 那个石墙上有数行奇异的数。这些数的前几位完整无缺，但不幸地，其余位的数字由于侵蚀作用而无法辨认。 尽管如此，他注意到每一行完好的数字都像是2的幂的前几位，他就猜想这个石墙上原先的所有数都是2的幂。 为了验证自己的想法，他选择了能看清楚的一些数写成列表，并把列表交给你， 请你求出最小的2的幂使幂的前若干位与他提供的列表中的数一致。 所以你必须写一个程序，对于给定的整数N(1 <= N <= 100)，求出最小的指数E使这个数的前若干位与N相同。 注意：N的长度必须小于2^E的长度的一半。如N＝1，当E等于4时，虽然2^4=16, 但因为1的长度等于16的长度的一半，所以不满足题上的条件，而只有在E等于7时，2^7=128才满足题意。 因此，N = 1时， 输出7
输入示例
输入：N = 1
输出示例
输出：7
算法
题目有点长，但是很好解，如代码
N=1 # 1<=N<=100
if N>=1 and N<10: #计算N的位数
wei=1
elif n==100:
wei=3
else:
wei=2
mi=1
while True:
get_mi=pow(2,mi)
get_mi_str=str(get_mi) #转换为str好进行操作
if get_mi_str[:wei]==str(N) and len(get_mi_str)>2*wei: #满足两个条件
print(mi)
break
mi+=1第29题：最小公倍数I
题目
给你一个正整数list L, 如 L=[2,8,3,50], 求列表中所有数的最小公倍数(不用考虑溢出问题）。 如L=[3,5,10], 则输出30
输入示例
输入：L = [3, 6, 22]
输出示例
输出：66
算法
两数的乘积=两数最小公倍数*两数最大公约数
def find_min_bei(x,y): #求两个数的最小公倍数
ji=x*y
for i in range(min(x,y),0,-1): #不包括0
if x%i==0 and y%i==0:
return ji//i
L=[3,6,22]
gongbei=1
for i in range(len(L)):
gongbei=find_min_bei(gongbei,L[i])
print(gongbei)第30题：整数解
题目
给你两个整数a和b（-10000<a,b<10000），请你判断是否存在两个整数，他们的和为a，乘积为b。 若存在，输出Yes,否则输出No
输入示例
输入：a=9,b=15
输出示例
输出：No
算法
假设两数分别是x和y，则有x*y=b,x+y=a；那么可以得到x*(a-x)=b，可以通过一层循环进行求解
a=9
b=15
flag=0
for i in range(-10000,10000+1):
if i*(a-i)==b:
flag=1
if flag:
print('Yes')
else:
print('No')第31题：一马当先
题目
下过象棋的人都知道，马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
输入示例
输入：n = 1 m = 2
输出示例
输出：1
算法
宽搜即可，开一个数组判断是否访问过（防止无限循环），开一个数组记下步数，若终点未经过，则输出-1。
import queue
q = queue.Queue()
dx = (1, 1, 2, 2, -1, -1, -2, -2)
dy = (2, -2, 1, -1, 2, -2, 1, -1)
n = 1
m = 2
vis = [[0] * (m + 1) for i in range(n + 1)]
dis = [[0] * (m + 1) for i in range(n + 1)]
q.put((0, 0))
vis[0][0]=1
while not q.empty():
x, y = q.get()
vis[x][y] = 1
for i in range(8):
xx = x + dx[i]
yy = y + dy[i]
if (xx >= 0 and xx <= n) and (yy >= 0 and yy <= m) and not vis[xx][yy]:
q.put((xx, yy))
dis[xx][yy]=dis[x][y]+1
print(dis[n][m] if dis[n][m] != 0 else -1)第32题：分拆素数和
题目
把一个偶数拆成两个不同素数的和，有几种拆法呢？ 现在来考虑考虑这个问题，给你一个不超过10000的正的偶数n， 计算将该数拆成两个不同的素数之和的方法数，并输出。 如n=10，可以拆成3+7，只有这一种方法，因此输出1.
输入示例
输入：n = 4
输出示例
输出：0
算法
先找出n以内的素数，然后对素数列表进行穷举相加即可。
本来考虑使用素数筛来做的，因为普通素数求法时间复杂度是O(n^2)，素数筛是O(nlogn)，不过题目规模较小（n<10000），就不需要了。
def getsu(a): #求素数
lista=[]
for i in range(2,a+1):
flag=0
for j in range(2,i):
if i%j==0:
flag=1
break
if(not flag):
lista.append(i)
return lista
n=10
res=0
su_list=getsu(n)
for i in su_list:
for j in su_list:
if i+j==n and i!=j:
#print(i,j)
res+=1
print(res//2)第33题：那些年我们集过的卡片
题目
不知道大家的童年有没有过和我相似的经历。我记得小时候经常买干脆面，不为别的，只是因为里面有一张人物卡片。 其实有很多这样的活动都有一个相同的模式：N 种人物卡片，每次买一包干脆面随机得到一张。当你集齐这 N 种人物时，就会有相应的奖励。 那时候还不懂怎么计算概率，白白给人家送了好多钱，吃了好多干脆面。 现在的任务是，给你一个正整数 N (1 <= N <= 10^4)，请你帮我从期望的角度计算平均需要买多少包干脆面才能集齐这 N 种人物。 提醒：由于结果可能不是整数，所以结果只保留到小数点后两位。
输入示例
输入：N = 1
输出示例
输出：1.00
算法
- N=1，1种卡片，怎么买都可以买到，期望就是 1
- N=2，2种卡片，拿到第1种以后，拿到第2种的概率就是 1/2, 理论上还需要买2包。期望和 = 3/3 + 2/1
- N=3，3种卡片， 拿到第1种以后，拿到第2种的概率就是2/3, 理论上需要买 3/2 包，再拿到第3种的概率就是 1/3 ，理论上需要买 3/1 包。 期望和 = 3/3 + 3/2 + 3/1
- 以此类推，N时，期望为1+(N-1)/N+(N-2)/N+...+1/N。
N=4
res=0.0
for i in range(N,0,-1):
res+=(N*1.0)/i
print('{:.2f}'.format(res))第34题：切西瓜
题目
小Py要吃西瓜，想知道切了n刀后，最多能切出多少块？请你们帮助下小Py. 给你一个正整数n（0 < n < 10^3),你输出一个数字，代表最多能切多少块。 如n=1, 输出2。
输入示例
输入：n = 1
输出示例
输出：2
算法
这道题本质上就是求n个平面能把一个空间划分为几个部分，有公式 �3+5�+66 。
print((n*n*n+5*n+6)//6)第35题：超级楼梯
题目
有一楼梯共n级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第n级，共有多少种走法？ 现在给你一个正整数n，求走法数
输入示例
输入：n = 2
输出示例
输出：1
算法
这其实就是一个斐波拉契数列。也可以用动态规划的思想来看，第n阶楼梯，可以从n-1阶和n-2阶走来，那么第n阶楼梯的走法就是前两阶楼梯的走法数相加。
斐波拉契数列可以用递归来做，也可以用递推来做，递推效率更高，下面是递推写法：
l = []
for i in range(n):
if i == 0 or i == 1:
l.append(1)
else:
l.append(l[i-1]+l[i-2])
# for i in range(n):
# print(l[i])
print(l[n-1]) #因为下标从0开始第36题：最大非连续子序列
题目
给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个非连续子序列，使其和最大，输出最大子序列的和。 这里非连续子序列的定义是，子序列中任意相邻的两个数在原序列里都不相邻。 例如，对于L=[2,-3,3,50]， 输出52（分析：很明显，该列表最大非连续子序列为[2,50]).
输入示例
输入：L = [2, -3, 3, 50]
输出示例
输出：52
算法
这是一道非常典型且基础的动态规划题目。当前的状态量，为1~n-2的状态值转移得来，那么我们可以通过两层循环，外层表示状态遍历，内层表示状态转移。
L = [2, -3, 3, 50,30]
l=[L[i] for i in range(len(L))]
for i in range(2,len(L)): #下标为0和1处，不能转移，所以从2开始
q=l[0]
for j in range(i-1): #到自身前两位为止
q=max(q,l[j])
if q>0: #如果前面的状态有大于0的，就更新当前状态
l[i]=l[i]+q
#print(q,L[i],l[i])
#遍历找出最大的状态值
a=l[0]
for i in l:
if i>a:
a=i
print(a)第37题：最大连续子序列
题目
给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个连续子序列，使其和最大，输出最大子序列的和。 例如，对于L=[2,-3,3,50]， 输出53（分析：很明显，该列表最大连续子序列为[3,50]).
输入示例
输入：L = [2, -3, 3, 50]
输出示例
输出：53
算法
这道题也是一道动态规划的基础题，因为题目要求是连续序列，所以转移只能来自前一个状态量，那么只需要一层循环就可以结束。
L = [2, -3, 3, 50]
l=[L[i] for i in range(len(L))]
for i in range(1,len(L)):
if l[i-1]>0: # 若前一个状态量大于0，可以转移到本状态（使本状态的值更高）
l[i]=l[i-1]+l[i]
a=l[0]
for i in l:
if i>a:
a=i
print(a)第38题：异或求和
题目
给你一个正整数N（1 <= N <= 100000000000000000),求1^2^3^...^N的值。A^B表示A和B按位异或。 如N=3， 则输出0.
输入示例
输入：N = 3
输出示例
输出：0
算法
找规律题，将N除以4取余，根据余数得到不同的结果。这题不能暴力相异做，肯定会卡这种算法的。
if N%4==0:
print(N)
elif N%4==1:
print('1')
elif N%4==2:
print(N+1)
elif N%4==3:
print('0')第39题：分解 n!
题目
给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式. 质因数分解形式为: n=p1^m1*p2^m2*p3^m3…… *，这里 p1 < p2 < p3 < …… 为质数。如：n=6,则输出：6=2^4*3^2*5 n=7，则输出：7=2^4*3^2*5*7
输入示例
输入：n = 7
输出示例
输出：7=2^4*3^2*5*7
算法
直接遍历即可，因为数据范围较小。
n=7
l=[0 for i in range(1000010)]
# print(len(l))
def findyin(a):
m = int(a ** 0.5)
#print(m)
for i in range(2,m+1):
while a%i==0:
l[i]+=1
a//=i
if a>1:
l[a]+=1
for i in range(2,n+1):
findyin(i)
if n==1:
print("1=1")
else:
a=str()
a=a+str(n)+"="
for i in range(2,1000010):
if l[i]==1:
a=a+str(i)+"*"
if l[i]>1:
a=a+str(i)+"^"+str(l[i])+"*"
print(a[0:len(a)-1])第40题：全排列
题目
给你一个仅有小写字母组成的字符串s（len(s) < 10)，请你输出s内的所有字母的全排列，每行输出一个， 按照字典序升序输出。 如：s="bbjd",则输出： bbdj bbjd bdbj bdjb bjbd bjdb dbbj dbjb djbb jbbd jbdb jdbb
输入示例
输入：s = "bbjd"
输出示例
输出：bbdj bbjd bdbj bdjb bjbd bjdb dbbj dbjb djbb jbbd jbdb jdbb
算法
利用全排列函数即可，注意输出前要排序（按照字典序）
from itertools import permutations
ans = set()
for item in permutations(s):
ans.add("".join(item))
ans = list(ans)
ans.sort()
for i in ans:
print(i)
发布于 2021-12-05 00:06