整数因子分解问题（递归+栈）-程序员宅基地
技术标签： 整数因子分解 c 算法刷题 课程学习 算法分析与设计
整数因子分解问题，对于给定的正整数n，计算n有多少种不同的分解式
上面已经给出了基本的方法，问题分析：这个问题其实很简单，将一个数n从2到它本身依次求余，如果发现n求余后为0，证明这个被求余的数i是这个整数的因子，那么我们对n/i再进行递归，直到n/i变为1停止递归。
扩展问题一：能否输出各种具体的分解表达式？
思路：可以设置一个栈，如果是因子，则将这个因子压入栈中，递归到因子为1时分解完毕，将整个栈中元素输出。一次递归结束后将栈顶的元素弹出。代码如下：
void calculate(int n, Stack *Top){
if( n == 1 ){
count++ ;
Print(Top);
}
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
这里是自定义的栈，栈的实现代码如下：
//栈的结点类型
typedef struct Node
{
int data;
struct Node *next;
}Stack;
//初始化一个栈
Stack *InitStack()
{
Stack *Top;
Top = (Stack *)malloc(sizeof(Stack));
Top->next = NULL;
return Top;
}
//判断栈空
int isEmpty(Stack *Top)
{
if(Top->next==NULL)
return 0;
else
return 1;
}
//入栈
int Push(Stack *Top,int x)
{
Stack *p;
p = (Stack *)malloc(sizeof(Stack));
p->data = x;
p->next = Top->next;
Top->next = p;
return TRUE;
}
//出栈
int Pop(Stack *Top)
{
if(Top->next==NULL){
printf("ERROR\n");
return FLASE;
}
else{
Stack *p;
p = Top->next;
Top->next = p->next;
free(p);
return TRUE;
}
}
//打印栈中元素
void Print(Stack *Top)
{
Stack *p = Top->next;
while (p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n") ;
}
此处没使用STL中的stack，一个主要的原因，就是我想要打印但是不清空栈，这个问题没有解决，STL中无法在不清空栈的情况下直接遍历栈。
扩展问题二：能否输出不重复的分解表达式？
第一种思路：
经过多次试验发现，如果递归结束时，模拟栈中的元素是无序的，则本次分解一定重复。以12为例，有3种情况为：2×2×3、2×3×2、3×2×2，后两种之所以重复，是因为它们都是无序的，因此，在上问题一的基础上，只须在输出之前判断一下模拟栈中的元素是否有序便可，若序时，才进行输出。代码如下:
void calculate(int n, Stack *Top){
if( n == 1 ){
count++ ;
if(isOrder(Top))
{
Print(Top);
}
}
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
其中判断是否有序的函数如下：
bool isOrder(Stack *Top)
{
Stack *p = Top->next;
while(p->next!=NULL)
{
Stack *q = p->next;
if(q->data > p->data)
{
return false;
}
p=p->next;
}
return true;
}
第二种思路：第一种思路的改进
既然为了保持模拟栈中元素的顺序，那每次i入栈之前先同栈顶元素进行比较，如果i大于栈顶元素，则不入栈，这种方法更简洁。代码如下：
void calculate3(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate3( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
进一步进行优化：
其实函数内层循环中i没有必要循环到n，只须要循环到sqrt(n)便可，当然，需要再补上缺失的一种情况，即当i为n乘1的情况，代码如下：
void calculate(int n, Stack *Top){
...
else{
for(int i=2;i<=sqrt(n);i++)
{
...
}
//以下三行代码，处理1乘n的情况
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
基于c解答的完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE 1
#define FLASE 0
int count = 0 ;
//栈的结点类型
typedef struct Node
{
int data;
struct Node *next;
}Stack;
//初始化一个栈
Stack *InitStack()
{
Stack *Top;
Top = (Stack *)malloc(sizeof(Stack));
Top->next = NULL;
return Top;
}
//判断栈空
int isEmpty(Stack *Top)
{
if(Top->next==NULL)
return 0;
else
return 1;
}
//入栈
int Push(Stack *Top,int x)
{
Stack *p;
p = (Stack *)malloc(sizeof(Stack));
p->data = x;
p->next = Top->next;
Top->next = p;
return TRUE;
}
//出栈
int Pop(Stack *Top)
{
if(Top->next==NULL){
printf("ERROR\n");
return FLASE;
}
else{
Stack *p;
p = Top->next;
Top->next = p->next;
free(p);
return TRUE;
}
}
//打印栈中元素
void Print(Stack *Top)
{
Stack *p = Top->next;
while (p!=NULL){
printf("%d ",p->data);
p = p->next;
}
printf("\n") ;
}
bool isOrder(Stack *Top)
{
Stack *p = Top->next;
while(p->next!=NULL)
{
Stack *q = p->next;
if(q->data > p->data)
{
return false;
}
p=p->next;
}
return true;
}
//扩展问题1
void calculate_all(int n, Stack *Top){
if( n == 1 ){
count++ ;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate_all( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2，第一种思路
void calculate(int n, Stack *Top){
if( n == 1 ){
if(isOrder(Top))
{
count++ ;
Print(Top);
}
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2，第一种思路的优化，循环到sqrt(n)
void calculate2(int n, Stack *Top){
if( n == 1 ){
if(isOrder(Top))
{
count++ ;
Print(Top);
}
}
else{
for(int i=2;i<=sqrt(n);i++)
{
if( n%i == 0 ){
Push(Top, i) ;
calculate2( n/i, Top ) ;
Pop(Top) ;
}
}
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
//扩展问题2的第二种思路
void calculate3(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=n;i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate3( n/i, Top ) ;
Pop(Top) ;
}
}
}
}
//扩展问题2的第二种思路的优化，循环到sqrt(n)
void calculate4(int n, Stack *Top){
if( n == 1 ){
count++;
Print(Top);
}
else{
for(int i=2;i<=sqrt(n);i++)
{
if( n%i == 0 ){
if(Top->next!=NULL && i<Top->next->data)
{
continue;
}
Push(Top, i) ;
calculate4( n/i, Top ) ;
Pop(Top) ;
}
}
Push(Top, n);
calculate2(1, Top);
Pop(Top);
}
}
int main()
{
int n ;
Stack *Top = InitStack() ;
printf("请输入一个正整数:") ;
scanf("%d", &n) ;
calculate_all( n, Top) ;
printf("式子个数:%d\n", count) ;
/*
calculate( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate2( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate3( n, Top) ;
printf("式子个数:%d\n", count) ;
calculate4( n, Top) ;
printf("式子个数:%d\n", count) ;
*/
return 0 ;
}
参考链接：
https://blog.csdn.net/qingsong3333/article/details/7348923
https://blog.csdn.net/dms2017/article/details/89192985
智能推荐
没有U盘Win10电脑下如何使用本地硬盘安装Ubuntu20.04（单双硬盘都行）_没有u盘怎么装ubuntu-程序员宅基地
文章浏览阅读3.6k次，点赞2次，收藏2次。DELL7080台式机两块硬盘。_没有u盘怎么装ubuntu
【POJ 3401】Asteroids-程序员宅基地
文章浏览阅读32次。题面Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conv...
工业机器视觉系统的构成与开发过程（理论篇—1）_工业机器视觉系统的构成与开发过程(理论篇—1-程序员宅基地
文章浏览阅读2.6w次，点赞21次，收藏112次。机器视觉则主要是指工业领域视觉的应用研究，例如自主机器人的视觉，用于检测和测量的视觉系统等。它通过在工业领域将图像感知、图像处理、控制理论与软件、硬件紧密结合，并研究解决图像处理和计算机视觉理论在实际应用过程中的问题，以实现高效的运动控制或各种实时操作。_工业机器视觉系统的构成与开发过程(理论篇—1
plt.legend的用法-程序员宅基地
文章浏览阅读5.9w次，点赞32次，收藏58次。legend 传奇、图例。plt.legend()的作用：在plt.plot() 定义后plt.legend() 会显示该 label 的内容，否则会报error: No handles with labels found to put in legend.plt.plot(result_price, color = 'red', label = 'Training Loss') legend作用位置：下图红圈处。..._plt.legend
深入理解 C# .NET Core 中 async await 异步编程思想_netcore async await-程序员宅基地
文章浏览阅读2.2k次，点赞3次，收藏11次。深入理解 C# .NET Core 中 async await 异步编程思想引言一、什么是异步？1.1 简单实例（WatchTV并行CookCoffee）二、深入理解（异步）2.1 当我需要异步返回值时，怎么处理？2.2 充分利用异步并行的高效性async await的秘密引言很久没来CSDN了，快小半年了一直在闲置，也写不出一些带有思想和深度的文章；之前就写过一篇关于async await 的异步理解 ，现在回顾，真的不要太浅和太陋，让人不忍直视！好了，废话不再啰嗦，直入主题：一、什么是异步？_netcore async await
IntelliJ IDEA设置类注释和方法注释带作者和日期_idea作者和日期等注释-程序员宅基地
文章浏览阅读6.5w次，点赞166次，收藏309次。当我看到别人的类上面的多行注释是是这样的：这样的：这样的：好装X啊！我也想要！怎么办呢？往下瞅：跟着我左手右手一个慢动作~~~File--->Settings---->Editor---->File and Code Templates --->Includes--->File Header:之后点applay--..._idea作者和日期等注释
随便推点
发行版Linux和麒麟操作系统下netperf 网络性能测试-程序员宅基地
文章浏览阅读175次。Netperf是一种网络性能的测量工具，主要针对基于TCP或UDP的传输。Netperf根据应用的不同，可以进行不同模式的网络性能测试，即批量数据传输（bulk data transfer）模式和请求/应答（request/reponse）模式。工作原理Netperf工具以client/server方式工作。server端是netserver,用来侦听来自client端的连接,c..._netperf 麒麟
万字长文详解 Go 程序是怎样跑起来的？| CSDN 博文精选-程序员宅基地
文章浏览阅读1.1k次，点赞2次，收藏3次。作者| qcrao责编 | 屠敏出品 | 程序员宅基地刚开始写这篇文章的时候，目标非常大，想要探索 Go 程序的一生：编码、编译、汇编、链接、运行、退出。它的每一步具体如何进行，力图弄清 Go 程序的这一生。在这个过程中，我又复习了一遍《程序员的自我修养》。这是一本讲编译、链接的书，非常详细，值得一看！数年前，我第一次看到这本书的书名，就非常喜欢。因为它模仿了周星驰喜剧..._go run 每次都要编译吗
C++之istringstream、ostringstream、stringstream 类详解_c++ istringstream a >> string-程序员宅基地
文章浏览阅读1.4k次，点赞4次，收藏2次。0、C++的输入输出分为三种：(1)基于控制台的I/O (2)基于文件的I/O (3)基于字符串的I/O 1、头文件[cpp] view plaincopyprint?#include 2、作用istringstream类用于执行C++风格的字符串流的输入操作。 ostringstream类用_c++ istringstream a >> string
MySQL 的 binglog、redolog、undolog-程序员宅基地
文章浏览阅读2k次，点赞3次，收藏14次。我们在每个修改的地方都记录一条对应的 redo 日志显然是不现实的，因此实现方式是用时间换空间，我们在数据库崩了之后用日志还原数据时，在执行这条日志之前，数据库应该是一个一致性状态，我们用对应的参数，执行固定的步骤，修改对应的数据。1，MySQL 就是通过 undolog 回滚日志来保证事务原子性的，在异常发生时，对已经执行的操作进行回滚，回滚日志会先于数据持久化到磁盘上（因为它记录的数据比较少，所以持久化的速度快），当用户再次启动数据库的时候，数据库能够通过查询回滚日志来回滚将之前未完成的事务。_binglog
我的第一个Chrome小插件-基于vue开发的flexbox布局CSS拷贝工具_chrome css布局插件-程序员宅基地
文章浏览阅读3k次。概述之前介绍过 移动Web开发基础-flex弹性布局（兼容写法） 里面有提到过想做一个Chrome插件，来生成flexbox布局的css代码直接拷贝出来用。最近把这个想法实现了，给大家分享下。play-flexbox插件介绍play-flexbox一秒搞定flexbox布局，可直接预览效果，拷贝CSS代码快速用于页面重构。 你也可以通过点击以下链接（codepen示例）查_chrome css布局插件
win10下安装TensorFlow-gpu的流程(包括cuda、cuDnn下载以及安装问题)-程序员宅基地
文章浏览阅读308次。我自己的配置是GeForce GTX 1660 +CUDA10.0+CUDNN7.6.0 + TensorFlow-GPU 1.14.0Win10系统安装tensorflow-gpu（按照步骤一次成功）https://blog.csdn.net/zqxdsy/article/details/103152190环境配置——win10下TensorFlow-GPU安装（GTX1660 SUPER+CUDA10+CUDNN7.4）https://blog.csdn.net/jiDxiaohuo/arti