C++每日一练:贝博士的机械零件(补全题目)奇偶排序(巧妙快排)寻因找祖

本文主要是介绍C++每日一练:贝博士的机械零件(补全题目)奇偶排序(巧妙快排)寻因找祖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、贝博士的机械零件
    • 1、题目
    • 2、解法
  • 二、奇偶排序(巧用快排)
  • 三、寻因找祖


前言

今天的题目中寻因找祖最难了,明显的数学题,笔者这数学文盲水平肯定不会,用暴力搞了一波,只有50%。就去考察学习了一下,记录学习过程以备复习。贝博士的机械零件在笔者这里题目都不显示,费了点劲把题目补全了。给有需要的童鞋参考一下。奇偶排序遇到很多次了,这回突发奇想,用了快排思想优雅地解了一把,总算可以稍稍找回点不会数学的自信。
在这里插入图片描述


提示:以下是本篇文章正文内容,下面案例可供参考

一、贝博士的机械零件

这题目是空白的,就放最前面,让找题目的看官方便。

1、题目

题目描述
贝博士是个大忙人,他在设计和制造一台非常复杂的机械式计算机。 最近贝博士有一点烦恼,因为机械零件的种类繁多,磨损又快,经费不太够用了。不过,他发现有一些机械零件在磨损以后,可以用若干同一型号的磨损旧零件重新回炉熔化以后再铸造出一个该型号的新零件,符合这样的特点的机械零件称为可翻新零件。 于是贝博士请来了他的助手艾小姐,请她统计一下有多少种型号的可翻新零件,每一种目前有多少存量又能以多少个旧零件重新回炉铸造出一个新零件,要求计算出对应于每一种机械零件他最终能使用的零件个数。

输入描述:
第一行输入两个数p和q,表示某型号的零件存量为p,且可以用q个旧零件重新回炉铸造出一个新零件。

输出描述:每一种可翻新机械零件最终可以使用的个数。

示例:输入:6 6 输出:7
补全代码框架,参考了示例给出的数据,猜测应该是两个数字在一行,所以直接用getline,去除两端的空格。然后用stringstream流直接赋值给p、q了,伪照其它题目的写法,给写了个函数调用,输出结果:

#include <iostream>
#include <sstream>
#include <string>using namespace std;
int solution(int p, int q){int res;return res;
}int main(){string line;getline(cin>>ws, line);stringstream ss(line);int p, q;ss >> p >> q;int result = solution(p, q);cout << result << endl;return 0;
}

以上为原题,因笔者这里不显示,所以给可能也不能显示原题的同学参考。其实也就是个读取输入的办法。

2、解法

int solution(int p, int q){int res = p;while(p>=q){p -= q;p += 1;res += 1;}return res;
}

解法这里就只写solution函数了,逻辑非常简单,先让结果加上p个可用零件。然后用p减去q个零件,因为用了q个就可以合成一个,所以p又要加上一,结果也加一。如此循环一波,到了p小于q的情况,就不能合成零件了。直接输出结果变量res就行了。

二、奇偶排序(巧用快排)

这题自然是很简单的,以前都是以选择排序的方法过的,最多优化一下,在第一波排奇数的时候把偶数也给另找个容器存了,最后一次性把偶数倒入。时间、空间也都够用,今天又遇到这题就想着不能老用一个法子解这么简单的问题。换个思路,考虑到大多排序都和冒泡有关。结合了冒泡和快排的思想写了一个仿快排的解法,挺优雅的哦~

题目描述
一个数组里有奇数有偶数(乱序),调整数组顺序使奇数位于偶数前面。(测试用例仅做参考,我们会根据代码质量进行评分)

输入描述:第一行输入整数n。 第二行输入n个整数。

输出描述:输出排序后的n个整数。

std::vector<int> solution(int n, std::vector<int>& vec){// TODO:int j=0, k;for (int i=0; i<n; ++i){while(j<n && vec[j]%2!=0){j++;}k=j+1;while(k<n && vec[k]%2==0){k++;}while(k>j && vec[k]%2!=0){int tmp = vec[k-1];vec[k-1] = vec[k];vec[k] = tmp;k--;}}return vec;
}

和快排一样,采用了二个指针,从左往右排,j 表示了第一个找到的偶数,k 表示了 j 之后的第一个奇数。找到后先将当前记录为 t ,然后冒泡往 i 方向移,直到替换了 i ,之后就可以交换指针,因为 上面的 k 是 j 后的第一个奇数,j 直接得到 t 的值,交换指针可以加快排序速度。如此循环一次解决。从时间复杂度来看还是挺有效率的,空间复杂度更是最小的了。是不是非常有创意~ 同意这个创意不错的就给点个赞、加收藏、评论一波,来个三连!

三、寻因找祖

题目描述:寻找因子个数为n的最小整数x.

输入描述:输入整数n。(1<=n<=1000)

输出描述:输出x。

以下代码及解题思路来自:https://blog.csdn.net/Cey_Tao/article/details/126747772
感谢这位大侠的无私奉献!

可以先了解下唯一分解定理关于因子个数的部分,也叫算数基本定理,平常也会直接说是质因数分解:
在这里插入图片描述

任何一个正整数都可以分解成多个质数相乘的形式,这个分解过程就叫质因数分解,比如: 60 = 2 * 2 * 3 * 5 = 22 * 31 * 51 ,将所有质因数的指数 +1 再相乘即为因子个数,60 的因子数为 (2 + 1) * (1 + 1) * (1 + 1) = 12

于是据此可以想到,根据质因数来构建一个 因子数为 n 的整数,比如 2 * 2 = 4 是因子数为 3 的整数,2 * 2 * 2 = 8 是因子数为 4 的整数,而 2 * 3 = 6 因子数也为 4 且比 8 更小,所以我们要做的就是找出最优的质因数组合,使结果最小

这一过程可以用递归来实现,每次递归选用一个质数并指定其指数,使最终的因子数为 n,在多种组合中找出最优(最小)解

可以很容易想到,2n-1 一定满足 n 个因子数,但可能不是最优解,所以可以用 2n-1 作为上界,来不断缩小解

由于指数会很大,所以选用 double 来运算,最终答案一定不是一个超大的数,不然没法输出,所以不用担心 double 的精度问题,double 主要用来比较大小。

有一个貌似正确的错误思路,就是对 n 进行质因数分解,再根据分解结果分配质数和指数

比如 n = 12 = 2 * 2 * 3 = (1 + 1) * (1 + 1) * (2 + 1),所以需要三个质数且指数分别 1,1,2,按贪心思想较小的指数分配较大的指数,所以的到 22 * 31 * 51 = 60,因子数为 12 的最小整数就是 60

多数情况下这个做法是可以得出正确答案的,但也有个例,比如 n = 8 = 2 * 2 * 2 = (1 + 1) * (1 + 1) * (1 + 1),分配质数为 21 * 31 * 51 = 30,但 30 并不是最优解,23 * 31 = 24 才是

// 质数表,50 以内的质数就够了(小学背过)
double p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
// dfs(n, idx) 表示:构建因子数为 n,起始质数为 p[idx]
double dfs(long long n, long long idx) {if (n <= 2) return n;double ret = pow(p[idx], n - 1);	// 以当前质数 p[idx] 的 n - 1 次方作为最大可行的答案for (long long i = 2; i < n; i ++) {// 枚举当前质数 p[idx] 可行的指数(+1),再递归下一质数if (n % i == 0) {ret = min(ret, pow(p[idx], i - 1) * dfs(n / i, idx + 1));}}return ret;
}
double solution(long long n){return dfs(n, 0);
}

不出所料啊~ 就是一个数学问题!我肯定上了十好几年假学校,乍就不会这个 “唯一分解定理” 呢。话说小学时好像是有分解质因数的…
题外话:我用暴力硬莽过,50%,优化又优化后搞到90%,就再也没办法了。有谁暴力干翻这题的来说说呗~ 真是挺有难度的一题


这篇关于C++每日一练:贝博士的机械零件(补全题目)奇偶排序(巧妙快排)寻因找祖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/168250

相关文章

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》:本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数:不用传参就可以

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》:本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

C/C++和OpenCV实现调用摄像头

《C/C++和OpenCV实现调用摄像头》本文主要介绍了C/C++和OpenCV实现调用摄像头,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录准备工作1. 打开摄像头2. 读取视频帧3. 显示视频帧4. 释放资源5. 获取和设置摄像头属性

c/c++的opencv图像金字塔缩放实现

《c/c++的opencv图像金字塔缩放实现》本文主要介绍了c/c++的opencv图像金字塔缩放实现,通过对原始图像进行连续的下采样或上采样操作,生成一系列不同分辨率的图像,具有一定的参考价值,感兴... 目录图像金字塔简介图像下采样 (cv::pyrDown)图像上采样 (cv::pyrUp)C++ O

c/c++的opencv实现图片膨胀

《c/c++的opencv实现图片膨胀》图像膨胀是形态学操作,通过结构元素扩张亮区填充孔洞、连接断开部分、加粗物体,OpenCV的cv::dilate函数实现该操作,本文就来介绍一下opencv图片... 目录什么是图像膨胀?结构元素 (KerChina编程nel)OpenCV 中的 cv::dilate() 函

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A

C++ HTTP框架推荐(特点及优势)

《C++HTTP框架推荐(特点及优势)》:本文主要介绍C++HTTP框架推荐的相关资料,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Crow2. Drogon3. Pistache4. cpp-httplib5. Beast (Boos