📷 题解插图【GESP】C++一级练习BCQM3040,初识条件语句if,求幸运数
📅 2024-10-08·✍️ OneCoder·计算中...·⏱️ 4 分钟
#GESP#C++#基础语句
到目前为止,应该是第一道可能需要用到if语句的题目(后来发现也可以不用),也算刚刚接近GESP 1级真题水平的题目,值得一做。
BCQM3040
题目要求
描述
A同学认为自己的幸运数是不超过N的非负整数里能被K整除的最大的数,你能帮他的算幸运数吗?
输入
输入—行,包含两个整数N,K(1 ≤ N,K ≤ 2×10^9)。
输出
输出—行,包含一个整数,表示幸运数。
输入样例
3 2
输出样例
2
题目分析
要找不超过N的,能被K整除的最大的数。即 该数 % K == 0,且最大。那么我们只要从最大的N开始循环遍历往1找,判断每个数 % K 是否等于0即可。第一个满足条件的数,就是最大的数。
此外,根据题目的输入条件N, K <= 2 * 10^9,属于int类型的数据范围,因此用int类型变量去存储N,K的值即可。
代码参考-从大往小遍历
CPP
#include <iostream>
using namespace std;
int main() {
int n, k; // 定义变量n存储上限,k存储除数
cin >> n >> k; // 从标准输入读取n和k的值
// 从n开始倒序遍历到1,寻找能被k整除的最大数
for (int i = n; i >= 1; i--) {
if (i % k == 0) { // 若当前数i能被k整除,则i即为所求幸运数
cout << i; // 输出该幸运数
break; // 找到后立即退出循环
}
}
return 0; // 程序正常结束
}
为了加强练习,我还让孩子编写了一个从1开始查找的解法,区别在于从1开始,第一个满足条件的数不是最大的数,最后一个才是,因此要用一个中间变量去保存遍历中符合条件的数。因为数在逐步增大,因此每查到一个,更新该变量的值即可,直到循环完成,此时就是最大的符合条件的数。显然,该方法遍历的次数一定比之前的从大往小遍历次数多,虽然从时间复杂度上看,都是O(n)。
代码参考-从小往大遍历
CPP
#include <iostream>
using namespace std;
int main() {
int n, k;
cin >> n >> k; // 读取上限N和除数K
int max; // 用于记录当前找到的最大幸运数
for (int i = 1; i <= n; i++) {
if (i % k == 0) { // 若i能被K整除,则i是一个候选幸运数
max = i; // 更新最大幸运数(因为i递增,故每次直接覆盖即可)
}
}
cout << max; // 输出最终找到的最大幸运数
return 0;
}
其实还有一个更直接快速的方法,就是利用整数计算取整的特性直接 N / K * K,即可得到答案。
代码参考-直接计算
CPP
#include <iostream>
using namespace std;
int main() {
int n, k; // 定义两个整数变量n和k,分别表示上限N和除数K
cin >> n >> k; // 从标准输入读取n和k的值
cout << n / k * k; // 利用整数除法向下取整的特性,直接计算不超过n且能被k整除的最大数
return 0; // 程序正常结束
}
💡 OneCoder 资源指引
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
🤝 技术交流与答疑
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
📚
猜你想读 · 相关文章推荐
OneCoder (lihongzheshuai)
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com
💬 读者留言与交流
还没有留言,快来成为第一个讨论者吧!