第十五届蓝桥杯大赛青少组——赛前解析（算法）
算法：进制转换、模拟算法，枚举算法，冒泡排序，插入排序，选择排序，递推算法，递归算法，贪心算法。
1.进制转换
二进制：只包含0和1
八进制：只包含0-7
十进制：只包含0-9
十六进制：只包含0-9和 ‘A’-‘F’
十进制转二进制、八进制、十六进制
十进制数 a=5
二进制 b=bin(a)；八进制 c=oct(a)；十六进制 d=hex(a)
二进制转十进制、八进制、十六进制
二进制数 a=‘101010’
十进制 b=int(a,2)；八进制 c=oct(b)；十六进制 d=hex(b)
八进制转十进制、二进制、十六进制
八进制数 a='52'
十进制 b=int(a,8)；二进制 c=bin(b)；十六进制 d=hex(b)
十六进制转十进制、二进制、八进制
十六进制数 a='2a'
十进制 b=int(a,16)；二进制 c=bin(b)；十六进制 d=oct(b)
总结
由上所知，当二进制，八进制，十六进制之间转换时，是以十进制作为媒介。
十进制数=int(某一进制数，其位数）
二进制=bin(十进制数）数学上采用‘整数部分除2，得余数，商为0结束，将余数从下往上取；小数部分乘2，取整，直到达到精度要求结束，按照顺序取’。
八进制=hex(十进制数）数学上采用‘整数部分除8，得余数，直到无法整除结束，将余数从下往上取；小数部分乘8，取整，直到达到精度要求结束，按照顺序取’。
十六进制=oct(十进制数）数学上采用‘整数部分除16，得余数，直到无法整除结束，将余数从下往上取；小数部分乘16，取整，直到达到精度要求结束，按照顺序取’。
其他数学上的转换见:进制之间的数学转换
将二进制数 1011 转换为十进制数：
1011（二进制） = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 0 + 2 + 1 = 11（十进制）
值得注意的是以上转换会出现前缀，如果不需要前缀就要用到切片（[2:]）将前缀删除。
同时，除了十进制数为数字类型，其他都属于字符串类型，在定义时需要加引号。
2.模拟算法
- 定义：通过模拟真实问题的操作步骤，逐步解决问题。
- 示例：模拟一个简单的ATM取款机的操作流程。
- 输入：取款金额，用户账户余额
- 输出：取款后账户余额
-
def atm_withdrawal(balance, amount):if amount > balance:return "Insufficient balance"else:balance -= amountreturn balancebalance = 1000 amount = 150 print(atm_withdrawal(balance, amount)) # 输出: 850
3.枚举算法：
- 定义：通过枚举所有可能的情况来寻找问题的解。
- 示例：找出100以内的所有素数。
- 逐一检查1到100中的每一个数，判断它是否为素数。
-
def is_prime(n):if n <= 1:return Falsefor i in range(2, int(n**0.5) + 1):if n % i == 0:return Falsereturn Trueprimes = [x for x in range(2, 101) if is_prime(x)] print(primes) # 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
4.冒泡排序：
- 定义：一种简单的排序算法，通过重复地遍历待排序列，一次比较两个元素，如果它们的顺序错误就交换它们的位置。
- 示例：对数组[5, 2, 9, 1, 5, 6]进行排序。
- 经过多次比较和交换，最终数组变为[1, 2, 5, 5, 6, 9]。
-
def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrarr = [5, 2, 9, 1, 5, 6] print(bubble_sort(arr)) # 输出: [1, 2, 5, 5, 6, 9]
5.插入排序：
- 定义：一种简单的排序算法，构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 示例：对数组[5, 2, 9, 1, 5, 6]进行排序。
- 逐步将元素插入到已排序部分，最终数组变为[1, 2, 5, 5, 6, 9]。
-
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arrarr = [5, 2, 9, 1, 5, 6] print(insertion_sort(arr)) # 输出: [1, 2, 5, 5, 6, 9]
6.选择排序：
- 定义：每一轮从未排序数据中选出最小值，将其与未排序部分的第一个元素交换，直到所有元素排序完毕。
- 示例：对数组[5, 2, 9, 1, 5, 6]进行排序。
- 逐步选择最小元素并交换，最终数组变为[1, 2, 5, 5, 6, 9]。
-
def selection_sort(arr):for i in range(len(arr)):min_idx = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arrarr = [5, 2, 9, 1, 5, 6] print(selection_sort(arr)) # 输出: [1, 2, 5, 5, 6, 9]
排序一般出现在选择题，主要用到的就是内置函数sort（）和sorted（），是将数据从小到大排序 。
7.递推算法：
- 定义：通过递推关系逐步求解问题。
- 示例：斐波那契数列（Fibonacci sequence）的递推。
- F(n) = F(n-1) + F(n-2)，其中F(1) = 1, F(2) = 1。
-
def fibonacci(n):if n <= 0:return []elif n == 1:return [0]elif n == 2:return [0, 1]fib_sequence = [0, 1]for i in range(2, n):fib_sequence.append(fib_sequence[-1] + fib_sequence[-2])return fib_sequenceprint(fibonacci(10)) # 输出: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
8.递归算法：
- 定义：函数直接或间接调用自身，以分解问题为子问题的方式解决问题。
- 示例：求解阶乘n!。
- n! = n × (n-1)!，其中0! = 1。
-
def factorial(n):if n == 0:return 1else:return n * factorial(n - 1)print(factorial(5)) # 输出: 120
9.贪心算法：
- 定义：每一步都做出在当前看来最优的选择，从而希望得到全局最优解。
- 示例：找零问题，给定面值为1、2、5元的硬币，找出组成金额最少的硬币数量。
- 对于金额11，最优解为5+5+1，共使用3枚硬币。
-
def min_coins(coins, amount):coins.sort(reverse=True)count = 0for coin in coins:while amount >= coin:amount -= coincount += 1return countcoins = [1, 2, 5] amount = 11 print(min_coins(coins, amount)) # 输出: 3