In The End

个人博客

0%

算法课作业：排序,贪心,分治,区间dp

发表于 更新于

排序实践题

题目

使用python 对【2,33,12,34,22,56,32,45,43】进行冒泡排序，要求输出详细的排序过程。

题解

冒泡排序不多说了

a[j],a[j-1]=a[j-1],a[j]是python特有的简易的交换方式

1
2
3
4
5
6
7
a=[5,4,2,3,4,9,10,1]

for i in range(0,len(a)-1):
   for j in range(len(a)-1,i,-1):
       if a[j]<a[j-1]:
         a[j],a[j-1]=a[j-1],a[j]
   print(a)

贪心法练习

题目

使用Python语言和贪心法实现。
给定一个正整数(<=255位),从中删去n位后，使得剩下的数字组成的新数最小。

题解

首先我们思考一个性质，高位的数字对大小的影响比所有低位的数字加起来都要大，比如将2000肯定没有1999小，所以我们肯定得首先删除高位的大的数字

再者，最后剩下的数字的位数是固定的，我们总是想贪心地让尽可能小的数字顶在前面，比如213我们肯定想删掉那个2使数字变成13

继续考虑1234删一个数字的情况，我们肯定会删掉最后的4，所以当都是小的数字在前面的时候，我们只能拿掉最后面的数字了

所有总结一下算法就是，我们从数字高位向低位扫，如果发现有逆序的（就是高位的数字比低位大），我们就把高位的数字删掉，将低位的数字变成删除后数字的高位。如果扫描一遍没有发现逆序，就把最末尾的数字删掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
m=str(input())
n=int(input())

while n!=0:
   flag=True
   for i in range(len(m)-1):
       if m[i]>m[i+1]:
           m=m.replace(m[i],'',1)
           flag=False
           break
   if flag:
       m=m.replace(m[len(m)-1],'',1)
   n-=1
print(m)

分治法练习

题目

大整数乘法问题。输入样例：72106547548473106236 982161082972751393，输出结果。要求：用Python语言实现，使用分治法，不要用整数类型的变量和变量相乘

题解

两个数字长度不一样用分治法感觉不太方便

这里直接写了时间和空间复杂度都更优的算法

就是利用乘法的进位性质，逐位乘然后加法就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def multiply(a: str, b: str) -> str:
   if a == '0' or b == '0': return '0'
   ans = 0
   len1 = len(a)
   len2 = len(b)
   for i in range(len1):
       for j in range(len2):
           current = int(a[-i - 1]) * int(b[-j - 1]) * int(10 ** (i + j))
           ans += current
   return str(ans)

a=str(input())
b=str(input())

print(multiply(a,b))

动态规划算法练习

题目

Python语言实现石子合并问题。在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。

规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

题解

区间dp的题目，跟矩阵连乘是差不多的道理

这里我拿最大值举例子了，最小值一样的道理

区间dp的关键就在于划分区间，每个区间都取到最大那么总区间就是最大了

首先我们定义一个状态dp[i][j]作为从i合并到j的最大值，那么如何求出这个最大值呢，我们需要找到一个k（因为i到j的石子需要两个区间合并过来，所以一定有一个切分点，我们使用k从i枚举到j-1来逐个枚举切分点），所以最大值的公式就是dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum(i,j))。然后i，j的枚举顺序得从小区间枚举到大区间（因为大区间合并的时候需要小区间的信息），就是我们先得算石子两堆合并，然后再利用已知的两堆合并完的信息求出三堆合并以此类推……

为什么要用2*n长度的list，因为一开始是环形的，如果用n长度的数组还得取模，比较麻烦，所以干脆将数组原样复制一遍拉长一倍

上面的算法用到了很多次求出i到j的总石子数，如果每次都求和太麻烦了，这里使用了前缀和的小技巧，将1到x的和存在s[x]内，这样如果我们求从i到j的总和，只需要求s[j]-s[i-1]就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
n=int(input())
# 因为要求前缀和的数组的关系,基于个人习惯下标从1开始,所以多开一个位置
s=[0 for i in range(2*n+1)] #前缀和数组

# 求出i+j
def sum(i:int,j:int)->int:
    return s[j]-s[i-1]

str=input()
stone=[int(i) for i in str.split()] # 记录石子的数组
stone.insert(0,0)
#将石子的list扩大一倍,将环形转为线性
for i in range(1,n+1):
    stone.append(stone[i])
    s[i]=s[i-1]+stone[i]
for i in range(n+1,2*n+1):
    s[i]=s[i-1]+stone[i]

# 两个用于区间dp的二维数组
mi=[[0 for i in range(300)] for j in range(300)]
mx=[[0 for i in range(300)] for j in range(300)]

for x in range(1,n):
    for i in range(1,2*n):
        j=i+x
        #为什么要加等于呢,因为我们把链复制了一遍,如果等于就是起点与终点重合了
        if j>=2*n:
            break
        mi[i][j]=1<<30
        mx[i][j]=0 #这一句可以不要,不过为了逻辑上好理解加上去吧
        # 下面就是两个状态转移公式
        for k in range(i,j):
            mi[i][j]=min(mi[i][j],mi[i][k]+mi[k+1][j]+sum(i,j))
            mx[i][j]=max(mx[i][j],mx[i][k]+mx[k+1][j]+sum(i,j))

max_ans=0
min_ans=1<<30

for i in range(1,n+1):
    min_ans=min(min_ans,mi[i][i+n-1])
    max_ans=max(max_ans,mx[i][i+n-1])

print(min_ans)
print(max_ans)