[蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)

这篇具有很好参考价值的文章主要介绍了[蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新.....

目录

一、算法基础

1.Huffuman树

2.Sine之舞

3.数列排序

4.数列排序

5.特殊回文数

6.回文数

7.特殊的数字

8.杨辉三角形

9.高精度加法

10.Fibonacci数列

11.报时助手

12.回形取数

13.矩阵乘法

二、算法提高

1.印章

2.拿金币

3.B君的寄望

4.数字游戏

5.kAc给糖果你吃

6.无聊的逗

7.跳马

8.最大分解

9.粘木棍

10.数的潜能

大功告成!编写不易,大家成功后点个关注or赞谢谢~


一、算法基础

1.Huffuman树

问题描述:Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:
  1. 找到{pi}中最小的两个数,设为papb,将papb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb
  2. 重复步骤1,直到{pi}中只剩下一个数。
  在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。
  本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。

  例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下:
  1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。
  2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。
  3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。
  4. 找到{10, 17}中最小的两个数,分别是10和17,从{pi}中删除它们并将和27加入,得到{27},费用为27。
  5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。

'''
输入格式
  输入的第一行包含一个正整数n(n<=100)。
  接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。

输出格式
  输出用这些数构造Huffman树的总费用。

样例输入
5
5 3 8 2 9

样例输出
59
'''

n = int(input())
tab = input().split()
all_num = 0 #总成本
while len(tab) > 1: #需要进行n轮
    # 找出最小的两个数
    min_1 = int(tab[0])
    for i in range(1, len(tab)):
        if int(tab[i]) < min_1:
            min_1 = int(tab[i])
    tab.remove(str(min_1)) #去除第一个最小数

    min_2 = int(tab[0])
    for j in range(1, len(tab)):
        if int(tab[j]) < min_2:
            min_2 = int(tab[j])
    tab.remove(str(min_2)) #去除第二个最小数

    all_num += min_1 + min_2 #累加成本
    
    tab.append(str(min_1 + min_2)) #将第一轮的成本加入列表中

print(all_num)

2.Sine之舞

问题描述:最近FJ为他的奶牛们开设了数学分析课,FJ知道若要学好这门课,必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏,寓教于乐,提高奶牛们的计算能力。不妨设
  An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)
  Sn=(...(A1+n)A2+n-1)A3+...+2)An+1
  FJ想让奶牛们计算Sn的值,请你帮助FJ打印出Sn的完整表达式,以方便奶牛们做题。

'''
输入格式
  仅有一个数:N<201。

输出格式
  请输出相应的表达式Sn,以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入
3

样例输出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1
'''

n = int(input())
A_n = ["sin(1)"]
for i in range(2,n+1):
    if i%2 == 0:
        A_n.append(A_n[i-2][:-(i-1)])
        A_n[i-1] += "-"+"sin("+str(i)+")"*i
    else:
        A_n.append(A_n[i-2][:-(i-1)])
        A_n[i-1] += "+"+"sin("+str(i)+")"*i
S_n = ""
for j in range(1,n):
    if j%2 != 0:
        S_n += A_n[j-1] + "+" + str(n+j-1) + ")"
    else:
        S_n += A_n[j-1] + "+" + str(n-j+1) + ")"
S_n  = "("*(n-1) + S_n + A_n[n-1] + "+" + "1" 
print(S_n) 

3.数列排序

问题描述:给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<=n<=200

'''
输入格式
  第一行为一个整数n。
  第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

输出格式
  输出一行,按从小到大的顺序输出排序后的数列。


样例输入
5
8 3 6 4 9

样例输出
3 4 6 8 9
'''

n = int(input())
s = input().split()
for i in range(n):
    for j in range(n-i-1):
        if int(s[j])>int(s[j+1]):
            tmp = s[j+1]
            s[j+1] = s[j]
            s[j] = tmp
for i in range(n):
    print(s[i],end=" ")

4.数列排序

问题描述:给定n个十六进制正整数,输出它们对应的八进制数。

'''
输入格式
  输入的第一行为一个正整数n (1<=n<=10)。
  接下来n行,每行一个由0~9、大写字母A~F组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。

输出格式
  输出n行,每行为输入对应的八进制正整数。
  【注意】
  输入的十六进制数不会有前导0,比如012A。
  输出的八进制数也不能有前导0。

样例输入
  2
  39
  123ABC

样例输出
  71
  4435274
'''

n = int(input())
record = []
for i in range(n):
	record.append(input())
for i in range(n):
	nn = int(record[i],16)
	ss = oct(nn)
	print(ss[2:])

5.特殊回文数

问题描述:123321是一个非常特殊的数,它从左边读和从右边读是一样的。输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。

'''
输入格式
  输入一行,包含一个正整数n。

输出格式
  按从小到大的顺序输出满足条件的整数,每个整数占一行

样例输入
 52

样例输出
 899998
 989989
 998899
'''

n = int(input())
for i in range(10000,1000000):
    z = str(i)
    if z==z[::-1]:
        m=sum(int(j) for j in z)
        if m==n :
             print(z)

6.回文数

问题描述:1221是一个非常特殊的数,它从左边读和从右边读是一样的,编程求所有这样的四位十进制数。

'''
输出格式
  按从小到大的顺序输出满足条件的四位十进制数。
'''

for i in range(1000,10000):
	arr = str(i)
	a,b,c,d = int(arr[0]) ,int(arr[1]) ,int(arr[2]) ,int(arr[3])
	if(a^d == 0 and b^c == 0): #采用异或运算符,不懂得可以自己去搜索一下
		print(i)

7.特殊的数字

问题描述:153是一个非常特殊的数,它等于它的每位数字的立方和,即153=1*1*1+5*5*5+3*3*3。编程求所有满足这种条件的三位十进制数。

'''
输出格式
  按从小到大的顺序输出满足条件的三位十进制数,每个数占一行。
'''

for i in range(100, 1000):
    if ((int(str(i)[0]) * int(str(i)[0])* int(str(i)[0])  + int(str(i)[1]) * int(str(i)[1])  * int(str(i)[1])+ int(str(i)[2]) * int(str(i)[2])* int(str(i)[2])) == i):
        print(i)

8.杨辉三角形

问题描述:杨辉三角形又称Pascal三角形,它的第i+1行是(a+b)i的展开式的系数。 它的一个重要性质是:三角形中的每个数字等于它两肩上的数字相加。 下面给出了杨辉三角形的前4行:

   1 

  1 1 

 1 2 1

1 3 3 1

'''
输入格式
输入包含一个数n

输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出,中间使用一个空格分隔。请不要在前面输出多余的空格。

样例输入
4

样例输出
1
1 1
1 2 1
1 3 3 1
'''

numRows = int(input())
ret = []
for i in range(numRows):
    row = []
    for j in range(i+1):
        if(j == 0 or j == i):
            row.append(1)
        else:
            row.append(ret[j]+ret[j-1])
    for x in range(i+1):
        print(row[x],end=" ")
    print("\t") #隔空输出
    ret = row

9.高精度加法

问题描述:输入两个整数ab,输出这两个整数的和。ab都不超过100位。

由于ab都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。
  定义一个数组AA[0]用于存储a的个位,A[1]用于存储a的十位,依此类推。同样可以用一个数组B来存储b
  计算c = a + b的时候,首先将A[0]与B[0]相加,如果有进位产生,则把进位(即和的十位数)存入r,把和的个位数存入C[0],即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加,这时还应将低位进上来的值r也加起来,即C[1]应该是A[1]、B[1]和r三个数的和.如果又有进位产生,则仍可将新的进位存入到r中,和的个位存到C[1]中。依此类推,即可求出C的所有位。
  最后将C输出即可。

'''
输入格式
  输入包括两行,第一行为一个非负整数a,第二行为一个非负整数b。两个整数都不超过100位,两数的最高位都不是0。

输出格式
  输出一行,表示a + b的值。

样例输入
20100122201001221234567890
2010012220100122

样例输出
20100122203011233454668012
'''

a = str(input())[::-1]
b = str(input())[::-1]

i = 0
read = 0
num = ""
j = min(len(a),len(b))
hashtab = [0]*(max(len(a),len(b))+1)

#补全
if len(a) > len(b):
    while j < len(a):
        hashtab[j] = a[j]
        j += 1
else:
    while j < len(b):
        hashtab[j] = b[j]
        j += 1

#相加
while i < min(len(a),len(b)):
    if int(a[i])+int(b[i]) < 10:
        hashtab[i] = str(int(a[i])+int(b[i]) + int(hashtab[i]))
    else:
        hashtab[i] = str((int(a[i]) + int(b[i])) % 10 + int(hashtab[i]))
        hashtab[i+1] = str((int(a[i]) + int(b[i])) // 10 + int(hashtab[i+1]))
    i += 1

#判断最高位是否进位
for o in range(0,len(hashtab)):
    if int(hashtab[o]) >= 10:
        hashtab[o + 1] = str(int(hashtab[o]) // 10 + int(hashtab[o + 1]))
        hashtab[o] = str(int(hashtab[o]) % 10 )

#输出
while read < len(hashtab):
    num += str(hashtab[read])
    read += 1
    
#判断高位是否为0.如果是的话不输出
if num[-1] == "0":
    num = num[::-1]
    print(num[1:])
else:
    print(num[::-1])

10.Fibonacci数列

问题描述:Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。

'''
输入格式
  输入包含一个整数n。

输出格式
  输出一行,包含一个整数,表示Fn除以10007的余数。

样例输入
10

样例输出
55
'''

n = int(input())
f_1 = 1 #想最初的两个1,2求出来,后面我们直接从F(3)开始运算
f_2 = 1
if n==1:
	num = 1
if n==2:
	num = 1
m = 3
while m < n+1:
	num = (f_1 + f_2) % 10007 #由于提示不用算出每个数,每次只用算出每个数对10007的余数就行
	mid = f_1
	f_1 = f_2 %10007
	f_2 = (mid + f_1)%10007 #可以减少运算,否则可能运算超时
	m += 1
print(num) 

11.报时助手

问题描述:给定当前的时间,请用英文的读法将它读出来。
  时间用时h和分m表示,在英文的读法中,读一个时间的方法是:
  如果m为0,则将时读出来,然后加上“o'clock”,如3:00读作“three o'clock”。
  如果m不为0,则将时读出来,然后将分读出来,如5:30读作“five thirty”。
  时和分的读法使用的是英文数字的读法,其中0~20读作:
  0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
  30读作thirty,40读作forty,50读作fifty。
  对于大于20小于60的数字,首先读整十的数,然后再加上个位数。如31首先读30再加1的读法,读作“thirty one”。
  按上面的规则21:54读作“twenty one fifty four”,9:07读作“nine seven”,0:15读作“zero fifteen”。

'''
输入格式
  输入包含两个非负整数h和m,表示时间的时和分。非零的数字前没有前导0。h小于24,m小于60。

输出格式
  输出时间时刻的英文。

样例输入
0 15

样例输出
zero fifteen
'''

Time = input().split()
# 创建一个字典把特殊的读法放进去
dict = {0:'zero', 1: 'one', 2:'two', 3:'three', 4:'four', 5:'five', 6:'six', 7:'seven', 8:'eight', 9:'nine', 10:'ten', 11:'eleven', 12:'twelve', 13:'thirteen', 14:'fourteen', 15:'fifteen', 16:'sixteen', 17:'seventeen', 18:'eighteen', 19:'nineteen', 20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',30:'thirty',40:'forty',50:'fifty'}

read_time = ''
read_time += dict[int(Time[0])] # 将h读出来

if int(Time[1]) == 0:
    read_time += " o'clock"
elif 0<int(Time[1])<=24:
    read_time +=" "
    read_time += dict[int(Time[1])]
else:
    read_time += " "
    read_time += dict[int(Time[1])//10*10]
    read_time += " "
    read_time += dict[int(Time[1])%10]

print(read_time)

12.回形取数

问题描述:回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度。一开始位于矩阵左上角,方向向下。

'''
输入格式
  输入第一行是两个不超过200的正整数m, n,表示矩阵的行和列。接下来m行每行n个整数,表示这个矩阵。

输出格式
  输出只有一行,共mn个数,为输入矩阵回形取数得到的结果。数之间用一个空格分隔,行末不要有多余的空格。

样例输入
3 3
1 2 3
4 5 6
7 8 9

样例输出
1 4 7 8 9 6 3 2 5
'''

mn = input().split()
m = int(mn[0])
n = int(mn[1])

rect = []
for x in range(0,int(mn[0])):
    apend_rect = input().split()
    rect.append(apend_rect)

result = ""

#总共需要取n//2+n%2
for z in range(0,min(m,n)//2+min(m,n)%2):
    if m < 2 or n < 2:
        if m==1 and n ==1:
            result += " " + rect[0][0]
        elif m < 2:
            for i in range(0, n):
                result += " " + rect[0][i]
        else:
            for i in range(0, m):
                result += " " + rect[i][0]

    else:
        result += " " + rect[0][0]
        # 取外圈的数
        i, j = 0, 0
        for y in range(0, m * n - (m - 2) * (n - 2)):
            # 从左上角向下取
            if i < m - 1 and j == 0:
                i += 1
                result += " " + rect[i][j]
            # 从左下角向右取
            elif i == m - 1 and j < n - 1:
                j += 1
                result += " " + rect[i][j]
            # 从右下角向上取
            elif i > 0 and j == n - 1:
                i -= 1
                result += " " + rect[i][j]
            # 从右上角向左取
            else:
                while j > 1:
                    j -= 1
                    result += " " + rect[i][j]
        #取内圈作为下一次外圈的输入
        m -= 2
        n -= 2
        if m > 0 or n > 0:
            rect_new = []
            a = 1
            while a < m+1:
                rect_new_small = []
                b = 1
                while b < n+1:
                    rect_new_small.append(rect[a][b])
                    b += 1
                rect_new.append(rect_new_small)
                a += 1

            rect = rect_new

print(result[1:])

13.矩阵乘法

问题描述:给定一个N阶矩阵A,输出A的M次幂(M是非负整数)
 

'''
输入格式
  第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数
  接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值

输出格式
  输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

样例输入
2 2
1 2
3 4

样例输出
7 10
15 22
'''

mn = input().split()
N = int(mn[0])
M = int(mn[1])

#导入矩阵
rect = []
for x in range(0,N):
    apend_rect = input().split()
    rect.append(apend_rect)

rect_new = [[ 0 for _ in range(0,N)] for _ in range(0,N)]
rect_mid = rect

if M == 0:
    for i in range(0,N):
        rect_new[i][i] = 1
        result = ""
        for j in range(0,N):
            result += " " + str(rect_new[i][j])
        print(result[1:])
else:
    if M == 1:
        rect_new = rect
    else:
        for i in range(0,M-1):
            rect_new = [[0 for _ in range(0, N)] for _ in range(0, N)]
            a = 0 #a为行计算,b为列计算
            while a < N:
                b = 0
                while b < N:
                    for j in range(0,N):
                        rect_new[a][b] += int(rect_mid[a][j]) * int(rect[j][b])
                    b += 1
                a += 1
            rect_mid = rect_new

    for i in range(0,N):
        result = ""
        for j in range(0,N):
            result += " " + str(rect_new[i][j])
        print(result[1:])

二、算法提高

1.印章

问题描述:共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。

'''
输入格式
  一行两个正整数n和m

输出格式
  一个实数P表示答案,保留4位小数。

样例输入
2 3

样例输出
0.7500
'''

nm = list(map(int,input().split()))
n = nm[0]
m = nm[1]
rect = [[0 for _ in range(0,n)] for _ in range(0,m)]
#拥有一张时,拥有一张的概率必为1
rect[0][0] = 1
for i in range(1,m):
    rect[i][0] = (1/n)**i
for i in range(1,m):
    for j in range(1,n):
        #第i-1张已经拥有j种+i-1张没有拥有第j种的概率
        rect[i][j] = rect[i-1][j]*((j+1)/n) + rect[i-1][j-1]*((n-j)/n)
print("%.4f" % rect[-1][-1])

2.拿金币

问题描述:有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

'''
输入格式
  第一行输入一个正整数n。
  以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式
  最多能拿金币数量。

样例输入
3
1 3 3
2 2 2
3 1 2

样例输出
11
'''

n = int(input())
rect = []
for i in range(0, n):
  rect.append(input().split())
rect[0][0] = int(rect[0][0]) #第一个只能(1,1)的自身
for i in range(1,n):
    rect[0][i] = int(rect[0][i]) + int(rect[0][i-1])
for i in range(1, n):
    rect[i][0] = int(rect[i][0]) + int(rect[i-1][0])
for i in range(1, n):
    for j in range(1, n):
        #(i,j)就是自身加上左边以及上面两个的最大值
        rect[i][j] = int(rect[i][j]) + max(int(rect[i-1][j]),int(rect[i][j-1]))
#累加后最后一个就为最大值
print(rect[-1][-1])

3.B君的寄望

问题描述:B君在执行爬山计划的时候迷了路,但他身上有个哨子,而哨声分为长和短,中间要有间隔,短音1s,长音2s,间隔1s,给你总时间,问有几种吹法,最后一个哨声要刚好在第n秒时结束。

'''
输入格式
  每组测资只有一个整数,1~1000

输出格式
  输出一个整数,代表哨声吹法种数

样例输入
1

样例输出
1
'''

n = int(input())
if n < 5:
    if n == 2 or n == 4:
        print(0)
    if n == 1:
        print(1)
    if n == 3:
        print(2)
else:
    rect = [[0,0] for _ in range(0,n)]
    rect[0][0] = 1
    rect[0][1] = 0
    rect[1][0] = 0
    rect[1][1] = 1
    rect[2][0] = 1
    rect[2][1] = 0
    rect[3][0] = 1
    rect[3][1] = 1
    for i in range(4,n):
        rect[i][0] = rect[i - 2][0] + rect[i - 2][1]
        rect[i][1] = rect[i - 3][0] + rect[i - 3][1]
    print(rect[-1][-1]+rect[-1][-2])

4.数字游戏

问题描述: 给定一个1~N的排列a[i],每次将相邻两个数相加,得到新序列,再对新序列重复这样的操作,显然每次得到的序列都比上一次的序列长度少1,最终只剩一个数字。
  例如:
  3 1 2 4
  4 3 6
  7 9
  16
现在如果知道N和最后得到的数字sum,请求出最初序列a[i],为1~N的一个排列。若有多种答案,则输出字典序最小的那一个。数据保证有解。

'''
输入格式
  第1行为两个正整数n,sum

输出格式
  一个1~N的一个排列

样例输入
4 16

样例输出
3 1 2 4
'''

###首先声明这道题真的真的真的太难了....只得了三十分,其他结果没问题,但是运算超时....

In = input().split()
n = int(In[0]) #行数
num = int(In[1]) #最终总数
rect = [] #记录最终的排序
#计算三角函数第n行的每个数
def trangle(x):
    trangle_rect = [[1],[1,1]]
    for i in range(2,x):
        mid = []
        for j in range(0,i+1):
            if j==0 or j==i:
                mid.append(1)
            else:
                mid.append(trangle_rect[i-1][j] + trangle_rect[i-1][j-1])
        trangle_rect.append(mid)
    return trangle_rect[-1]

trangle_n = trangle(n)
mid = [] #记录过程中的数组
def trackback(n,s): #n=几行,starIndex=起始位置
    #判断是否成功
    if len(mid) > n:
        return
    game_over(s)
    #回溯
    for j in range(1,n+1):
        mid.append(j)
        trackback(n,j)
        mid.pop()

#代码冗长单独写一个判断是否成功的函数
def game_over(s):
    all_num = 0
    #判断如果长度不同直接返回
    if len(mid) == n:
        for i in range(0,n):
            all_num += int(trangle_n[i]) * int( mid[i])
        if all_num == num:
            mid_set = set(mid)
            #判断是否有重复的数
            if len(mid_set) != len(mid):
                return
            else:
                rect.append(mid[:])
                return

trackback(n,0)

for i in range(0,n):
    print(rect[0][i],end=" ")

5.kAc给糖果你吃

问题描述:kAc有n堆糖果,每堆有A[i]个。kAc说你只能拿m次糖果,聪明的你当然想要拿最多的糖果来吃啦啦啦~//第二天,kAc问你还想吃糖果么?(嘿嘿嘿)说着眼角路出奇怪的微笑...
 

'''
输入格式
  第一行两个数字n和m,第二行有n个数字A[i]。

输出格式
  输出一行表示最多能拿几个糖果。

样例输入
2 2
1 2

样例输出
3
'''

n ,m = map(int,input().split())
A = list(map(int,input().split()))
result = 0
#利用循环每次找到最大的一个,然后移除
#利用贪心,每次都找到局部最大的,再到总体最大
for i in range(m):
    mid= max(A)
    result += mid
    A.remove(mid)
print(result)

6.无聊的逗

问题描述:逗志芃在干了很多事情后终于闲下来了,然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍,然后选出其中一些粘成一根长的,然后再选一些粘成另一个长的,他想知道在两根一样长的情况下长度最长是多少。

思路:

  1. 我的思路是动态规划寻找等和子集,这道题其实就可以理解为寻找等和子集,如果不能找到,那就删除一个数再寻找
  2. 我的代码是先查找所给出的数组能否找到一个等和子集
  3. 然后再每次删除数组中的一个数然后再寻找是否能找到等和子集
  4. 将所有情况都记录下来,最终输出最大的等和子集
'''
输入格式
  第一行一个数n,表示n个棍子。第二行n个数,每个数表示一根棍子的长度。

输出格式
  一个数,最大的长度。

样例输入
4
1 2 3 1

样例输出
3
'''

n = int(input())
N = list(map(int,input().split()))

#动态规划寻找等和子集的和函数
def find_all(nums):
    n = len(nums)
    if n < 2:
        return

    total = sum(nums)
    maxNum = max(nums)
    if total & 1:
        return

    target = total // 2
    if maxNum > target:
        return

    dp = [[False] * (target + 1) for _ in range(n)]
    for i in range(n):
        dp[i][0] = True

    dp[0][nums[0]] = True
    for i in range(1, n):
        num = nums[i]
        for j in range(num, target + 1):
            if j >= num:
                dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
            else:
                dp[i][j] = dp[i - 1][j]

    if dp[n - 1][target] == True:
        return target

#找到等和函数中最大的数
def maxnum(n,N):
    result = []
    #这一步先找给出的数列中可不可以直接分为等和函数
    a = find_all(N)
    if a != None:
        result.append(a)
    #依次减去每一个数后查看是否能找到等和子集
    for i in range(n):
        mid = N[0:i] + N[i+1:n]
        a = find_all(mid)
        if a != None:
            result.append(a)
    #输出等和子集中最大的一个
    print(max(result))

maxnum(n,N)

7.跳马

问题描述:一个8×8的棋盘上有一个马初始位置为(a,b),他想跳到(c,d),问是否可以?如果可以,最少要跳几步?

思路:DFS

'''
输入格式
  一行四个数字a,b,c,d。

输出格式
  如果跳不到,输出-1;否则输出最少跳到的步数。

样例输入
1 1 2 3

样例输出
1
'''

a,b,c,d = map(int,input().split())
#因为马走'日'字,所以可以跳8个方向,一次列出来
hourse = [[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2]]
#记录最小步数
min_step = float("inf")
#创建一个棋盘,为什么是9X9呢,因为可以与坐标对应且记录是否已经走过
visited = [[0 for _ in range(9)] for _ in range(9)]

#开始定义DFS函数
def DFS(x,y,step):
    global min_step,visited
    #此处剪枝操作,只要比记录过的最小步数大的就不再遍历,减少搜索次数
    if step > min_step:
        return
    #终止条件,只要到了预期的坐标就结束
    if x ==c and y ==d:
        min_step = step
        return
    #分别便利hourse里面的8个坐标,搜索每一个都可以到的位置
    for i in range(8):
        x_new = x + hourse[i][0]
        y_new = y + hourse[i][1]
        if x_new > 0 and x_new <= 8 and y_new > 0 and y_new <= 8:
            #记录走过的地方,不重复
            if visited[x_new][y_new] == 0:
                visited[x_new][y_new] = 1
                DFS(x_new,y_new,step+1)
                visited[x_new][y_new] = 0

#初始化(a,b)为已访问
visited[a][b] = 1
DFS(a,b,0)
#如果没有返回步数则走不到,返回-1
if min_step == float("inf"):
    print(-1)
else:
    print(min_step)

8.最大分解

问题描述:给出一个正整数n,求一个和最大的序列a0,a1,a2,……,ap,满足n=a0>a1>a2>……>ap且ai+1是ai的约数,输出a1+a2+……+ap的最大值

思路:贪心+递归 

'''
输入格式
  输入仅一行,包含一个正整数n

输出格式
  一个正整数,表示最大的序列和,即a1+a2+……+ap的最大值

样例输入
10

样例输出
6
'''

n = int(input())
nums = []
flag = 0

def digui(n):
    #设置一个标志位,当最后一个数到1时就开始不再搜索
    global flag
    begin = n-1
    while begin > 0:
        if flag == 1:
            return
        # 约数就是后一个数能不能被前一个数整除
        if n % begin == 0:
            if begin == 1:
                flag = 1
            nums.append(begin)
            #现在就以ai为开头继续往下搜索
            digui(begin)
        begin -= 1

digui(n)
result = 0
for i in range(len(nums)):
    result += nums[i]
print(result)

9.粘木棍

问题描述:有N根木棍,需要将其粘贴成M个长木棍,使得最长的和最短的的差距最小。

思路:DFS

'''
输入格式
  第一行两个整数N,M。
    一行N个整数,表示木棍的长度。

输出格式
  一行一个整数,表示最小的差距

样例输入
3 2
10 20 40

样例输出
10
'''

n,m = map(int,input().split())
nums = list(map(int,input().split()))
double = [0 for _ in range(m)]
seen = []
target = float("inf")
def DFS(flag): #flag记录已经算过多少个数,target最小值
    global target
    if flag == n:
        if m != 1 and 0 in double:
            return
        if max(double)-min(double) > target:
            return
        target = max(double)-min(double)
        return
    for i in range(m):
        for j in nums:
            if j in seen:
                None
            else:
                seen.append(j)
                double[i] += j
                DFS(flag+1)
                seen.pop()
                double[i] -= j

DFS(0)
print(target)

10.数的潜能

问题描述:将一个数N分为多个正整数之和,即N=a1+a2+a3+…+ak,定义M=a1*a2*a3*…*ak为N的潜能。给定N,求它的潜能M。由于M可能过大,只需求M对5218取模的余数。

思路:两张方法:DFS和数学归纳法

'''
输入格式
  输入共一行,为一个正整数N。

输出格式
  输出共一行,为N的潜能M对5218取模的余数。

样例输入
10

样例输出
36
'''

'''递归'''
'''
n = int(input())

result = 0
mid = []

def DFS(nums):
    global result,mid
    if nums > n:
        return
    if nums == n:
        mid_result = 1
        for i in range(len(mid)):
            mid_result = mid_result * mid[i]
        if mid_result >= result:
            result = mid_result
        return
    for j in range(2):
        nums += j+2
        mid.append(j+2)
        DFS(nums)
        nums -= j+2
        mid.pop()
if n == 1:
    print(1)
else:
    DFS(0)
    print(result)
'''

'''归纳'''
'''
n = int(input())

f = 3
if n==1:
    print(1)
elif n==2:
    print(2)
elif n==3:
    print(3)
else:
    for i in range(4,n+1):
        if (i-1)%3 == 0:
            f = f//3*4
        else:
            f = f//2*3
    print(f%5218)
'''

自己写的所以有点复杂,但是至少能完成嘿嘿。如果各位有优化欢迎评论区讨论!!文章来源地址https://www.toymoban.com/news/detail-404546.html

大功告成!编写不易,大家成功后点个关注or赞谢谢~~


到了这里,关于[蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • python蓝桥杯基础练习17题

    跟学链接:Python蓝桥杯真题——基础练习(一) 资源限制 Python时间限制:5.0s 问题描述 输入A、B,输出A+B。 输入格式 输入的第一行包括两个整数,由空格分隔,分别表示A、B。 输出格式 输出一行,包括一个整数,表示A+B的值。 样例输入 12 45 样例输出 57 数据规模与约定 -

    2023年04月08日
    浏览(33)
  • 蓝桥杯之算法模板题 Python版

    记录一下算法模板题,这样方便查阅和学习,希望好好加油 dp, LIS ** 01背包 动态转移方程 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)(jv) f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w ) ( j v ) 完全背包 一般就是

    2023年04月08日
    浏览(43)
  • Python 数学建模算法与应用(持续更新)

    目录 第一章  python使用入门 1.1 Python核心工具库 1. Numpy 2. SciPy 3. Matplotlib 4. IPython 5. SymPy 6. Pandas 1.2  Python基本数据类型 1. Numpy (1)强大的多维数组对象 (2)复杂的函数功能 (3)集成c/c++和FORTRAN代码的工具 (4)有用的线性代数、傅里叶变换和随机数功能等。 import numpy as

    2024年02月09日
    浏览(49)
  • 【蓝桥杯】DP和枚举(持续更新~~~)

    😽 PREFACE 🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝 📢系列专栏: 蓝桥杯 🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用 💪 种一棵树最好是十年前其次是现在 DP就是动态规划,其类型有以下两个特征: 重叠子问题:子问题是原大问题的小版本,计算步骤完全

    2023年04月08日
    浏览(40)
  • 算法面试-深度学习基础面试题整理-AIGC相关(2023.9.01开始,持续更新...)

    1、stable diffusion和GAN哪个好?为什么 ? Stable diffusion是一种基于随机微分方程的生成方法,它通过逐步增加噪声来扰动原始图像,直到完全随机化。然后,它通过逐步减少噪声来恢复图像,同时使用一个神经网络来预测下一步的噪声分布。Stable Diffusion的优点是可以在连续的潜

    2024年02月10日
    浏览(47)
  • yolov8训练心得 持续更新

    目录 yolov8的改进点: 优化器 lion优化器,学习率0.0001,训练效果: 学习率衰减

    2024年02月15日
    浏览(39)
  • 爆肝更新 Python 100道基础入门练习题(附答案)

    前言 大家早好、午好、晚好吖 ❤ ~ 更多精彩内容、资源皆可点击文章下方名片获取此处跳转 实例001:数字组合 题目: 有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少? 程序分析: 遍历全部可能,把有重复的剃掉。 实例002:“个税计算”

    2024年02月07日
    浏览(43)
  • 【Ctfer训练计划】——命令执行的解题技巧(持续更新中)

    作者名:Demo不是emo  主页面链接: 主页传送门 创作初心: 一切为了她 座右铭: 不要让时代的悲哀成为你的悲哀 专研方向: web安全,后渗透技术 每日emo: 真的还有相见的机会吗   目录 一、绕过  1、cat限制绕过 2、$限制绕过 3、点号限制绕过(2023.1.4) 4、空格限制绕

    2024年02月03日
    浏览(30)
  • VCS与Verdi联仿,简要万能工程模板,持续更新中...

    一、背景 学习verilog,故用vcs来编译verilog,用verdi来查看波形。 提供一套简要verilog工程模板去执行教程中代码,并分析波形。 二、编写工程模块 建立工程在temp文件夹下新建文件夹/rtl、/sim、/tb,如下: 在/rtl文件夹下新建两个.v文件: template.v和timescale.v ,为模板rtl代码。

    2024年02月12日
    浏览(40)
  • Python基础算法训练——循环训练(21~25)

    21. 宇宙大爆炸 【题目描述】 现在宇宙从第 0 秒开始膨胀,每秒会膨胀一圈。 第 1 秒时,宇宙的形状为 * 第 2 秒时,宇宙的形状为 *** *** *** ……………… 现在请你输出宇宙大爆炸后第 n 秒的形状。 【输入】 一个整数 n (1≤n≤100)。 【输出】 输出宇宙在第 n 秒的形状。 【输

    2024年02月11日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包