真题解析│蓝桥杯省赛真题“送分题”之第几个幸运数.pdf

### 蓝桥杯省赛真题解析：“送分题”之第几个幸运数 #### 题目背景与概述 本题目源自2018年蓝桥杯软件类省赛（C/C++大学A组），是一道典型的算法题。题目要求考生帮助小明计算他的编号——59084709587505，是第几个幸运数字。在X星球上，国王只喜欢数字3、5和7，并规定只有当游客编号仅包含这些因子时，才能获得奖品。 #### 题目分析 ##### 幸运数字定义 根据题目描述，幸运数字是指仅包含因子3、5和7的正整数。例如，前10个幸运数字依次为3、5、7、9、15、21、25、27、35、45。 ##### 题目要求 本题的目标是找出给定数字59084709587505是第几个幸运数字。这涉及到对特定数字模式的理解以及高效算法的设计。 #### 解题思路 针对这类问题，我们可以采用多种方法来求解： 1. **暴力搜索法** - 枚举所有可能的组合3^i * 5^j * 7^k。 - 计算出小于目标数字的所有幸运数字数量。 2. **硬算+排序法** - 生成所有可能的幸运数字。 - 对这些数字进行排序。 - 查找给定数字在排序后的数组中的位置。 3. **优先队列+Set去重法** - 使用优先队列来维护当前最小的幸运数字。 - 利用Set结构来避免重复。 #### Python实现示例 ##### 示例1：暴力搜索法 ```python cnt = 0 for i in range(50): for j in range(50): for k in range(50): r1 = 3 ** i r2 = 5 ** j r3 = 7 ** k if r1 * r2 * r3 < 59084709587505: cnt += 1 print(cnt) ``` ##### 示例2：硬算+排序法 ```python n = 59084709587505 a = [1] # 放3、5、7的倍数 k = 0 while True: for i in range(3, 8, 2): # 遍历3、5、7 tmp = i * a[k] # 产生一个新数 if tmp not in a: # 去重 a.append(tmp) # 放进去 a.sort() # 排序 if tmp > 2 ** 64: # 随便取一个够大的范围 print(a.index(n)) # 打印 exit(0) k += 1 ``` ##### 示例3：优先队列+Set去重法 ```python import queue q = queue.PriorityQueue() s = set() q.put(1) s.add(1) cnt = 0 while True: n = q.get() if n == 59084709587505: break cnt += 1 for i in range(3, 8, 2): # 3、5、7 t = n * i # 生成一个新数 if t not in s: # 去重 q.put(t) s.add(t) print(cnt) ``` #### C++实现示例 ```cpp #include<bits/stdc++.h> using namespace std; int main(void){ long long n = 59084709587505; int cnt = 0; for(int i=0;pow(3,i)<n;i++) // 注意不是 <= for(int j=0;pow(5,j)<n;j++) for(int k=0;pow(7,k)<n;k++) if(pow(3,i)*pow(5,j)*pow(7,k)<n) cnt++; cout<<cnt; return 0; } ``` #### 总结 通过以上分析和示例代码，我们了解了如何解决蓝桥杯中的这道“送分题”。主要涉及了暴力搜索、硬算+排序以及优先队列+Set去重等几种不同的算法思想。每种方法都有其适用场景和优缺点，在实际比赛中可以根据具体情况进行选择。此类题目旨在考察参赛者的算法设计能力和编程技巧，对于提升解决问题的能力具有重要意义。