无锡网站推,排版漂亮的网站,wordpress 博客论坛,潭州教育网站开发HJ6 质数因子
质数因子_牛客题霸_牛客网
题目分析
算法的核心是质因数分解#xff0c;它通过以下步骤实现#xff1a;
1. 处理2的因子
首先#xff0c;算法处理输入数n的2因子。因为2是最小的质数#xff0c;也是唯一的偶数质数#xff0c;所以首先检查n能被2整除多少…HJ6 质数因子
质数因子_牛客题霸_牛客网
题目分析
算法的核心是质因数分解它通过以下步骤实现
1. 处理2的因子
首先算法处理输入数n的2因子。因为2是最小的质数也是唯一的偶数质数所以首先检查n能被2整除多少次。使用一个while循环只要n能被2整除n % 2 0就将2打印出来作为一个因子并将n除以2。这个过程会一直继续直到n不再是偶数即不能被2整除。
2. 处理大于2的因子
一旦完成了所有的2因子n此时必然是一个奇数。接下来算法通过一个for循环从3开始检查每一个奇数是否是n的因子直到达到sqrt(n)。对于每个这样的i从3开始的奇数使用一个内部while循环检查i是否能整除n。如果是就将i打印为因子并将n除以i重复这个过程直到i不能整除n为止。这里为什么检查到sqrt(n)就足够了因为如果n有一个因子f大于它的平方根那么n必定还有一个因子小于或等于它的平方根因为f1 * f2 n如果两个因子都大于sqrt(n)它们的乘积将大于n。
3. 处理剩余的质数
完成上述步骤后如果n大于2则n本身就是一个质数。因为任何合数在上述步骤中都已被分解成更小的质数因子所以剩下的n一定是质数。最后如果n大于2直接将n打印出来。
acm模式
#include iostreamint main() {int n 0;std::cin n;while (n % 2 0) {std::cout 2 ;n (n / 2);}for (int i 3; i*i n; i 2) {while (n % i 0) {n n / i;std::cout i ;}}if (n 2) std::cout n std::endl;return 0;
}
HJ7 取近似值
取近似值_牛客题霸_牛客网
题目分析
我们可以使用C的标准库函数。我们会接收一个正浮点数然后根据它的小数部分决定是向上取整还是向下取整。在C中可以使用floor函数向下取整使用ceil函数向上取整但这里我们要根据小数点后的值决定取整的方向。
acm模式
#include iostream
#include cmathint main() {float i 0;std::cin i;float part i - floor(i);if (part 0.5) std::cout static_castint(ceil(i)) std::endl;else std::cout static_castint(floor(i)) std::endl;return 0;
}
HJ8 合并表记录
合并表记录_牛客题霸_牛客网
题目分析
要实现这个功能我们可以使用std::map来自动对index进行排序并且合并相同index的value值。std::map是一个基于红黑树的容器它可以保持键值对按键排序并且每个键是唯一的。当我们尝试插入一个已经存在的键时我们可以简单地将新的值加到已存在的值上。
#include iostream
#include mapint main() {int n; // 存储键值对的个数std::cin n;std::mapint, int records; // 使用map来自动排序并合并相同的indexfor(int i 0; i n; i) {int index, value;std::cin index value;records[index] value; // 如果index已存在value将被累加}// 遍历并输出合并后的键值对for(const auto record : records) {std::cout record.first record.second std::endl;}return 0;
}如果一定像我一样头铁也可以用unordered_map
acm模式
#include iostream
#include unordered_map
#include vector
#include algorithmint main() {int n 0, index 0, value 0;std::unordered_mapint, int umap;// std::vectorstd::pairint, int vec;std::cin n;while (n--) {std::cin index value;umap[index] value;}std::vectorstd::pairint, int vec(umap.begin(), umap.end());// vec vec(umap.begin(), umap.end());std::sort(vec.begin(), vec.end(),[](std::pairint, int a, std::pairint, int b){return a.first b.first;});for (std::pairint, int i : vec) {std::cout i.first i.second std::endl;}return 0;}
HJ9 提取不重复的整数
提取不重复的整数_牛客题霸_牛客网
题目分析
为了实现这个需求我们可以按以下步骤进行
从输入的整数中从右向左读取每一位数字。检查当前数字是否已经在新的整数中出现过如果没有则将其加入到新的整数中。继续读取下一位直到处理完整个输入整数。返回这个新构建的不含重复数字的整数。
为了方便检查数字是否已经被加入到新整数中我们可以使用一个std::setint来存储已经处理过的数字因为集合自动处理重复项。
acm模式
#include iostream
#include setint main() {int input;std::cin input;std::setint seenDigits;int result 0;while (input 0) {int digit input % 10; // 获取最右边的数字if (seenDigits.insert(digit).second) { // 如果数字尚未出现过result result * 10 digit; // 将数字添加到结果中}input / 10; // 移除已处理的最右边数字}std::cout result std::endl;return 0;
}我的题解
#include iostream
#include set
#include unordered_setint main() {int n 0, num 0;// std::setint uset;std::unordered_setint uset;std::cin n;while(n 0) {num n % 10;if (uset.find(num) uset.end()) {uset.insert(num);std::cout num;}n n / 10;}// for (int i : uset) {// std::cout i;// }return 0;
}
