整数因子分解问题（递归+栈）

r囧r小猫 2022-11-11 14:59 161阅读 0赞

整数因子分解问题，对于给定的正整数n，计算n有多少种不同的分解式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]  
上面已经给出了基本的方法，问题分析：这个问题其实很简单，将一个数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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20221022/d11f771f2ed84562bc3e4b83d94f9660.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: /images/20221022/ebe940001ae042c1b770f8a54f1bcd3b.png