当前位置：首页 > article >正文

蓝桥杯python基础算法（2-2）——基础算法（A）——枚举

article 2025/2/3 3:05:26

一、时间复杂度

二、枚举

例题：百钱买鸡

习题 P160 字符计数

习题 P152 反倍数

习题 P153 洁净数

习题 P549 扫雷

一、时间复杂度

O(1) - 常数时间复杂度：无论输入规模如何，算法执行时间都是一个常数。例如访问列表中的一个元素。

O(n) - 线性时间复杂度：算法执行时间与输入规模成正比。例如遍历一个列表。

O(n²) - 平方时间复杂度：通常出现在嵌套循环中，外层循环执行 n 次，内层循环也执行 n 次，整体执行次数为 n * n。

O(log n) - 对数时间复杂度：算法执行时间随着输入规模的增长以对数的速度增长。例如二分查找（前提是列表已经排序）。

O(n log n) - 线性对数时间复杂度：常用于高效的排序算法，如归并排序。

O(2ⁿ) - 指数时间复杂度：随着输入规模 n 的增加，算法执行时间呈指数级增长，效率极低。

二、枚举

枚举（Enumeration），也称为穷举法。它的核心思想是将问题所有可能的解一一列举出来，然后根据问题的约束条件来判断哪些解是符合要求的，从而得到问题的答案。

例题：百钱买鸡

百钱买鸡问题是中国古代数学家张丘建在《算经》中提出的一个著名数学问题：“今有鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。凡百钱买鸡百只，问鸡翁、母、雏各几何？” 意思是，公鸡每只5文钱，母鸡每只3文钱，小鸡3只1文钱，用100文钱买100只鸡，问公鸡、母鸡、小鸡各可以买多少只？

1. 确定问题的解空间范围，明确所有可能的解

设公鸡数量为 x，母鸡数量为 y，小鸡数量为 z。

公鸡数量范围：由于每只公鸡 5 文钱，100 文钱最多能买 100 // 5 = 20 只公鸡，所以 0 <= x <= 20。

母鸡数量范围：每只母鸡 3 文钱，100 文钱最多能买 100 // 3 ≈ 33 只母鸡，所以 0 <= y <= 33。

小鸡数量范围：已知总共买 100 只鸡，所以 z = 100 - x - y，且 z 必须是 3 的倍数，同时要满足总花费 5x + 3y + z / 3 = 100。

2. 按照一定的顺序，系统地列举出解空间中的每一个解
for x in range(0, 21):
    for y in range(0, 34):
        z = 100 - x - y
        if z % 3 == 0 and 5 * x + 3 * y + z // 3 == 100:
            print(f"公鸡: {x} 只, 母鸡: {y} 只, 小鸡: {z} 只")

以下题目相对简单，确保能独自完成解题

习题 P160 字符计数

题目描述

给定一个单词，请计算这个单词中有多少个元音字母，多少个辅音字母。

元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。

输入描述

输入格式：

输入一行，包含一个单词，单词中只包含小写英文字母。单词中的字母个数不超过 100。

输出描述

输出两行，第一行包含一个整数，表示元音字母的数量。

第二行包含一个整数，表示辅音字母的数量。
word = input()
vowel_count = 0
consonant_count = 0

for char in word:
    if char in 'aeiou':
        vowel_count += 1
    else:
        consonant_count += 1

print(vowel_count)
print(consonant_count)

习题 P152 反倍数

给定三个整数 a,b,c 如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。

请问在 1 至 n 中有多少个反倍数。

输入描述

输入的第一行包含一个整数 n。

第二行包含三个整数 a,b,c 相邻两个数之间用一个空格分隔。

其中，1≤n≤1000000，1≤a≤n，1≤b≤n，1≤c≤n。

输出描述

输出一行包含一个整数，表示答案。
n=int(input())
a,b,c=map(int,input().split())
count=0

for i in range(1,n+1):
    if i%a!=0 and i%b!=0 and i%c!=0:
        count+=1
print(count)

习题 P153 洁净数

小明非常不喜欢数字 2，包括那些数位上包含数字 2 的数。如果一个数的数位不包含数字 2，小明将它称为洁净数。

请问在整数 1 至 n 中，洁净数有多少个？

输入描述

输入的第一行包含一个整数 n(1≤n≤10^6)。

输出描述

输出一行包含一个整数，表示答案。
n=int(input())
count=0


for i in range(1,n+1):
    if "2" not in str(i):
       count+=1
print(count)

习题 P549 扫雷

在一个 n 行 m 列的方格图上有一些位置有地雷，另外一些位置为空。

请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。

输入描述

输入的第一行包含两个整数 n,m。

第 2 行到第 n+1 行每行包含 m 个整数，相邻整数之间用一个空格分隔。如果对应的整数为 0，表示这一格没有地雷。如果对应的整数为 1，表示这一格有地雷。

其中，1≤n,m≤100 分钟后还是在当天。

输出描述

输出 n 行，每行 m 个整数，相邻整数之间用空格分隔。

对于没有地雷的方格，输出这格周围的地雷数量。对于有地雷的方格，输出 9。
n,m=map(int,input().split())
row_list=[]
for i in range(n):
    row_list.append(list(map(int,input().split())))
result=[[0]*m for _ in range(n)]

#           (x-1,y+0)
# (x+0,y-1)           (x+0,y+1)
#           (x+1,y+0)

for i in range(n):
    for j in range(m):
        if row_list[i][j]==1:
            result[i][j]=9
        else:
            result[i][j]=0
            for x in range(max(0, i - 1), min(i + 2, n)):
                for y in range(max(0, j - 1), min(j + 2, m)):
                    if row_list[x][y]==1:
                        result[i][j]+=1

for row in result:
    for num in row:
        print(num,end=" ")
    print()