精华内容
下载资源
问答
  • 整数因子分解问题

    2021-03-21 15:20:50
    整数因子分解问题及其扩展问题的解答

    整数因子分解问题,对于给定的正整数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

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 483
精华内容 193
关键字:

整数因子分解问题