蓝桥输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums = list(map(int, input().split()))
#这行代码接收用户的输入，并将输入转换为整数列表。
#首先，input()函数接收用户的输入，然后
#split()方法将这个输入拆分成一个字符串列表。
#接着，map()函数应用int()函数到列表的每个元素，
#将每个字符串元素转换为整数。最后，li()函数
#将映射对象转换为列表。
print(' '.join(map(str, nums)))
#这行代码将整数列表转换回字符串，并以空格分隔每个元素，
#然后将整个字符串打印出来。首先，map()函数应用
#str()函数到列表的每个元素，将每个整数元素转换
#为字符串。然后，join()方法使用空格字符作为分隔符，
#将字符串列表连接成一个字符串。
#最后，print()函数打印这个字符串。
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#最大公约数
#约数︰如果整数a能被整数b整除，那么a叫做b的倍数，
#b叫做a的约数。
#给定两个整数a,b，两个数的所有公共约数中的最大值
#即为最大公约数(Greatest Common Divisor , GCD)。
#例:12与16的最大公约数是4

#如何计算两个数的最大公约数:
#欧几里得:辗转相除法(欧几里得算法)
#《九章算术》:更相减损术
#欧几里得算法: gcd(a, b) = gcd(b, a mod b)
#例: gcd(60, 21) = gcd(21, 18)= gcd(18, 3)= gcd(3, 0)= 3

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,(a%b))
def gcd2(a,b):
    while b>0:
        c=a%b
        a=b
        b=c
    return a
print(gcd(12,16))
print(gcd2(12,16))
#应用:实现分数计算
#利用欧几里得算法实现一个分数类，支持分数的四则运算。
class Fraction:
    def __init__(self,a,b):
        self.a=a
        self.b=b
        x=self.gcd2(a,b)
        self.a /= x
        self.b /= x



    def gcd2(self,a, b):
        while b > 0:
            c = a % b
            a = b
            b = c
        return a
    def lcm(self,a,b):
        x=gcd2(a,b)
        return x*(a/x)*(b/x)
    def __add__(self, other):#加
        a=self.a
        b=self.b
        c=other.a
        d=other.b
        denominator=self.lcm(b,d)
        numerator=a*(denominator)/b+c*(denominator)/d
        return Fraction(numerator,denominator)
    def __sub__(self, other):#减
        a = self.a
        b = self.b
        c = other.a
        d = other.b
        denominator = self.lcm(b, d)
        numerator = a * (denominator) / b - c * (denominator) / d
        return Fraction(numerator, denominator)
    def __mul__(self, other):#乘
        a = self.a
        b = self.b
        c = other.a
        d = other.b
        denominator = b*d
        numerator = a*c
        return Fraction(numerator, denominator)
    def __truediv__(self, other):#除
        a = self.a
        b = self.b
        c = other.b
        d = other.a
        denominator = b * d
        numerator = a * c
        return Fraction(numerator, denominator)
    def __str__(self):
        return "%d/%d" %  (self.a,self.b)

a=Fraction(4,12)
b=Fraction(6,24)
print(a+b)
print(a-b)
print(a*b)
print(a/b)

#RSA加密算法

#密码与加密
#传统密码:加密算法是秘密的
#现代密码系统:加密算法是公开的，密钥是秘密的
#   对称加密
#   非对称加密(RSA属于，加密解密各一个密钥）

#RSA非对称加密系统:
#公钥:用来加密，是公开的
#私钥:用来解密，是私有的

#RSA加密算法过程
#1.随机选取两个质数p和q
#2.计算n=pq
#3.选取一个与中(n)互质的小奇数e,中(n)=(p-1)(q-1)
#4.对模φ(n),计算e的乘法逆元d, 即满足(e*d) mod φ(n) = 1
#5.公钥(e, n)  私钥(d, n)
#加密过程: c= (m^e) mod n
#解密过程: m= (c^d) mod n
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#贪心算法
#贪心算法(又称贪婪算法)是指，在对问题求解时，
#总是做出在当前看来是最好的选择。也就是说
#不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
#贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解
#就是最优解。要会判断一个问题能否用贪心算法来计算。

#找零问题
#假设商店老板需要找零n元钱，钱币的面额有:100元、
#50元、20元、5元、1元，如何找零使得所需钱币的数量最少?
t=[100,50,20,5,1]
def change_money(t,n):
    m=[0 for _ in range(len(t))]
    for i,money in enumerate(t):#enumerate(t)用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标
        m[i]=n//money
        n=n%money
    return m,n
print(change_money(t,376))

#背包问题
#一个小偷在某个商店发现有n个商品，第i个商品价值vi元，
#重wi千克。他希望拿走的价值尽量高，但他的背包最多
#只能容纳W千克的东西。他应该拿走哪些商品?
#O-1背包:对于一个商品，小偷要么把它完整拿走，要么留下。
#不能只拿走—部分，或把一个商品拿走多次。(商品为金条)
#分数背包∶对于一个商品，小偷可以拿走其中任意一部分。
#(商品为金砂)
goods=[(60,10),(100,20),(120,30)]
goods.sort(key=lambda x:x[0]/x[1],reverse=True)
    #key=lambda x: x[0]/x[1]: 这是sort方法的key参数，它指定了一个函数，该函数用于从每个元素中提取一个用于排序的值。
    #这里使用了一个lambda函数，该函数接受一个元素（在这里命名为x），并返回该元素第一个元素与第二个元素的商。
    #reversed=True: 这告诉sort方法按照降序排序，而不是默认的升序。
def fractional_backpack(goods,W):#分数背包∶对于一个商品，小偷可以拿走其中任意一部分。
    m = [0 for _ in range(len(goods))]
    total_value=0
    for i,(value,weight) in enumerate(goods):
        if W>=weight:
            m[i]=1
            W-=weight
            total_value+=value
        else:
            m[i]=W/weight
            W=0
            total_value+=m[i]*value
            break
    return m,total_value

print(fractional_backpack(goods,50))
#拼接最大数字问题
#有n个非负整数，将其按照字符串拼接的方式拼接为一个整数。
#如何拼接可以使得得到的整数最大?
#例:32,94,128,1286,six.py,71
#可以拼接除的最大整数为94716321286128
li=[32,94,128,1286,6,71]


def number_join(li):
    # 定义一个内部函数 xy_cmp，用于比较两个数字的大小
    def xy_cmp(x, y):
        if x + y < y + x:  # 如果 x+y 小于 y+x，返回 1
            return 1
        elif x + y > y + x:  # 如果 x+y 大于 y+x，返回 -1
            return -1
        else:  # 如果 x+y 等于 y+x，返回 0
            return 0

            # 从 functools 模块导入 cmp_to_key 函数，用于将比较函数转换为排序键函数

    from functools import cmp_to_key

    # 将列表 li 中的每个元素转换为字符串
    li = list(map(str, li))
    # map(str, li) 会将 li 中的每个元素转换成字符串。
    # list() 函数将 map 返回的迭代器转换为列表。

    # 使用自定义的比较函数 xy_cmp 对列表进行排序
    li.sort(key=cmp_to_key(xy_cmp))

    # 使用 join 方法将排序后的列表转换为字符串并返回
    return "".join(li)

print(number_join(li))

#活动选择问题
#假设有n个活动，这些活动要占用同一片场地，
#而场地在某时刻只能供一个活动使用。
#每个活动都有一个开始时间s和结束时间f(题目中时间以整数表示),表示活动在[si,fi)区间占用场地。
#问:安排哪些活动能够使该场地举办的活动的个数最多?
#贪心结论:最先结束的活动一定是最优解的一部分。
#证明:假设a是所有活动中最先结束的活动，b是最优解中最先
#结束的活动。如果a=b，结论成立。
#如果a≠b，则b的结束时间一定晚于a的结束时间，则此时用a替
#换掉最优解中的b,a一定不与最优解中的其他活动时间重叠，因
#此替换后的解也是最优解。
activities=[(1,4),(5,9),(6,10),(8,11),(3,5),(8,12),(2,14),(12,16),(0,6),(5,7),(3,9)]
#保证活动是按结束时间排好序
activities.sort(key=lambda x:x[1])
def activities_selection(a):
    res=[a[0]]
    for i in range(1,len(a)):
        if a[i][0]>=res[-1][1]:#不冲突
            res.append(a[i])
    return res

print(activities_selection(activities))
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#栈和队列的应用——迷宫问题
#给一个二维列表,表示迷宫（0表示通道,1表示围墙）
#给出算法,求一条走出迷宫的路径
#栈——深度优先搜索
#回溯法
#思路:从一个节点开始,任意找下一个能走的点,
#当找不到能走的点时,退回上一个点寻找是否有其他方向的点。
#使用栈存储当前路径
#路径不一定为最短
maze=[
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]


dirs=[
    lambda x,y:(x+1,y),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x,y+1),
]
def maze_path_DFS(x1,y1,x2,y2):
    stack=[]
    stack.append((x1,y1))
    while(len(stack)>0):
        curNode=stack[-1]#当前节点
        #四个方向，当前x,y
        #上x+1,y;下x-1,y;左x,y-1;右x,y+1
        if curNode[0]==x2 and curNode[1]==y2:
            for p in stack:
                print(p)
            return True
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            #如果下个节点能走
            if maze[nextNode[0]][nextNode[1]]==0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] =2#标记已经走过了
                break
        else:
            maze[nextNode[0]][nextNode[1]] =2#标记已经走过了
            stack.pop()
    else:
        print("没有路径")
        return False

maze_path_DFS(1,1,8,8)
#队列————广度优先搜索
#思路:从一个节点开始，寻找所有接下来能继续走的点，
#继续不断寻找,直到找到出口。
#使用队列存储当前正在考虑的节点

maze=[
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]

dirs=[
    lambda x,y:(x+1,y),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x,y+1),
]

def maze_path_BFS(x1,y1,x2,y2):
    from collections import deque
    def print_p(path):
        curNode = path[-1]
        realpath = []
        while curNode[2] != -1:
            realpath.append(curNode[0:2])
            curNode = path[curNode[2]]
        realpath.append(curNode[0:2])
        realpath.reverse()  # 倒序
        for node in realpath:
            print(node)
    queue=deque()
    queue.append((x1,y1,-1))
    path=[]
    while len(queue)>0:
        curNode=queue.popleft()
        path.append(curNode)
        if curNode[0]==x2 and curNode[1]==y2:
            #终点
            print_p(path)
            return True
        for dir in dirs:
            nextNode=dir(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]]==0:
                queue.append((nextNode[0],nextNode[1],len(path)-1))#后续节点进队，记录哪个节点
                maze[nextNode[0]][nextNode[1]] =2#标记为已经走过

    else:
        print("没有路径")
        return False
maze_path_BFS(1,1,8,8)
#LanQiao
蓝桥输入输出
https://ianwusb.blog/2024/04/12/蓝桥输入输出/
作者
Ianwusb
发布于
2024年4月12日
许可协议