C++实现短除法

什么是短除法

短除法就是将多个数不断整除一个质数

这是一个简单的示意图

短除单独一个数，要把这个数除到1，用来分解质因数。这个数的质因数就是短除结果的左边和下边

短除两个数，可以找到这两个数的最大公因数和最小公倍数。这两个数的最大公因数是左边的积，最小公倍数是左边和下边的积

短除大于2个数，可以找到这些数的最大公因数，但不能直接找到最小公倍数。这些数的最大公因数是左边的积

怎么实现

我们发现，每个短除法的结果都由左边和下边组成。所以我们可以定义结果的结构体如下

typedef struct {std::list left;     // 左边的数据std::list bottom;   // 下边的数据 
}short_t;

这里面的list是C++给我们封装好的链表类型，是关于泛型的，表示链表的每个元素是int类型的。泛型实际上是类型的占位符，毕竟在机器码里没有类型的说法了。

那么std::是什么意思呢？是使用std命名空间的list类型的意思

很多人在写程序的时候，都会写，

using namespace std;

但不知道这是干嘛的。实际上，这句话声明了接下来使用std命名空间的东西。

在C语言中，printf(3)可以直接使用。因为C语言里函数是全局的（除非用static），而且不包含头文件都不会报错（非常不推荐这么写）；而C++的cin和cout都在std命名空间里，只有使用这个空间的时候才能调用。当然，C++还得给C语言一点面子，所以C语言的把函数写在全局的操作C++也是支持的。

扯远了。我们既然用到了list类型，就要导入相应的头文件

#include 

铺垫到这里，是时候上代码了：

short.h

#ifndef _SHORT_H_
#define _SHORT_H_// 导入C++的链表 
#include // 数组最大值和最小值 
#include // 判断两数大小
#define MAX(A, B) (((A)>(B))?(A):(B)) 
#define MIN(A, B) (((A)<(B))?(A):(B)) typedef struct {std::list left;     // 左边的数据std::list bottom;   // 下边的数据 
}short_t;// 判断一个数是否是质数
bool is_number_prime(unsigned int number); // 对两个数进行短除 
short_t two_number_short(int first, int second);// 对一个数进行短除
short_t one_number_short(int number); // 对一个数组里的所有数进行统一短除
// 注意：数组元素的值将变换 
short_t x_number_short(int arr[], int len); #endif

 short.cpp

#include "short.h"bool is_number_prime(unsigned int number){// 如果是0或1（小于等于1），返回假if(number <= 1)return false; // 从2开始直到number-1，如果有因数则不是质数for(int i = 2; i <= number-1; i++){// 如果没有余数（即i是number的因数） if(number % i == 0)return false; // 返回假 } return true;
}// 短除的核心代码 
// arr：要短除的数的地址数组
// len：arr的长度
// i：除的数
// result：结果结构体的引用 
static void __short(int *arr[], int len, int i, short_t &result){// 如果i是质数，则短除if(is_number_prime(i)){// 一直短除这个数直到除不了 while(1){// 只要有数除不了就退出for(int k = 0; k < len; k++)if(*(arr[k]) % i != 0)return;for(int k = 0; k < len; k++)*(arr[k]) = *(arr[k]) / i;// 放在结果里result.left.push_back(i); }}
}short_t two_number_short(int first, int second){int min = MIN(first, second);short_t result;int *tmp[2] = {&first, &second};// 从小到大找质数短除for(int i = 2; i <= min; i++)__short(tmp, 2, i, result);// 将两个数存在结果里 result.bottom.push_back(first);result.bottom.push_back(second);// 返回结果return result; 
}short_t one_number_short(int number){short_t result;int *tmp[2] = {&number};for(int i = 2; i <= number; i++)__short(tmp, 1, i, result);result.bottom.push_back(number);return result;
}short_t x_number_short(int arr[], int len){short_t result;// 获取arr里的最小值 int min = *std::min_element(arr, arr + len);int *tmp[len];for(int i = 0; i < len; i++)tmp[i] = &arr[i];for(int i = 2; i <= min; i++)__short(tmp, len, i, result);for(int i = 0; i < len; i++)result.bottom.push_back(*(tmp[i]));return result;
}

main.cpp

#include "short.h"
#include int main(void){int tmp[4] = {58, 28, 46, 18};short_t s = x_number_short(tmp, 4);printf("left:");std::list::iterator it = s.left.begin();for(;it != s.left.end(); it++)printf("%d\t", *it);printf("\n");printf("bottom:");it = s.bottom.begin();for(;it != s.bottom.end(); it++)printf("%d\t", *it);printf("\n");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！