分析QQ图片20200924085145.jpg

  • 类似于整数划分问题 , 因子分解也可以递归求解
  • 通过划分解树 , 可以观察到以下规律
    • 一个数的所有因子中有如下规律
      • 该数的因子的因子, 一定是该数的因子
      • 但是该数的因子A , 不一定是该数因子B 的因子

    设q(n,m) n的所有因子分解中 , 一定包含m因子的 , 分解个数 q(n,m) = q(n,n) n<m

    1.        = q(n,m/[小于m的n的因子]) + q(n/m,n/m)                    n>m
    2.        = q(n,[小于n的n的因子]) + 1                                          n=m
    3.        = 0                                                                                 m =1
    4.        = 1                                                                                 n为质数<br />

解的输出

  • 输出位置 : 在 n = m , 和 n 为质数的两个位置输出
  • 解的存储 , 用stack sta 存储
  • 解的输出 , 用tsta 辅助sta输出
  • 因子的入栈, 出栈时机
    1. n == m
      • 此时一定存在一个解 , 然后将n入栈之后输出栈里面的所有因子 , 然后再将n退栈
    2. n 为质数
      • 同上
    3. n > m ,且m为n的因子时候
      • 此时 q(n,m) 分解为 q(n,m/[小于m的n的因子]) + q(n/m,n/m) , 即一定包含m的解 ,和 不一定包含m的解
        • 对于n/m,n/m , 一定包含m , 所以将m 入栈 , 然后再递归查找n/m的分解 , 递归回到原处后m退栈
        • 接下来是 n,m/[小于m的n的因子] , 不一定包含m , 递归查找对于小于m的因子分解即可

          注意

  1. 首先求出n的所有因子
    1. [小于m的n的因子] , 注意次小于m的n的因子,不一定是m的因子 , 此处需要判断
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<stack>
using namespace std;
int divisors[100];
int divisorsNum;
stack<int> sta;
stack<int> tsta;
int firstM = 0; 
//输出一次结果
void printOneResault() {
    int flag = 0;
    while (!sta.empty()) {
        tsta.push(sta.top());
        sta.pop();
    }
    //格式化输出 
    if( firstM != tsta.top()){
        firstM = tsta.top();
        flag = 1;
    }
    if(flag){
        printf("\n");
    } else{
        printf("\t|");
    }
    while (!tsta.empty()) {
        int n = tsta.top();
        tsta.pop();
        sta.push(n);
        printf("%d ", n);
    }


}

//获得下一个较小的因子 
int getNextSmall(int n) {
    if (n == 1) {
        return 1;
    }
    else {
        for (int i = 0; i < divisorsNum; i++) {
            if (divisors[i] == n) {
                return divisors[i - 1];
            }
        }
    }
    return -1;
}

//如果是1 或者 质数 则只有一个分解方式 
int isPrime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

//核心方法 
int function(int n, int m) {
    int resNum1 = 0;
    int resNum2 = 0;
    //如果待分解数n是1或者是质数   直接输出
    if (isPrime(n)) {
        //输出一次结果 
        sta.push(n);
        printOneResault();
        sta.pop();
        return 1;
    }
    //如果m不是n的因子 则继续寻找下一个因子
    else if (n % m != 0) {
        //!!!!!!!! 注意: 一个数的所有因子中 , 某因子 ,不一定是其他因子的因子 例如 [40] {1,2,4,5,8,10.20.40} 其中5不是8的因子 
        //由于 在一次求解过程中,公用最大n的因子 , 所以需要过滤掉 类似于function(8,5) 这样的参数
        //在n的所有因子中 , 小因子A 的所有因子也一定包含在 , n的不大于A的因子中 , 但不全都是A的因子  
        return function(n, getNextSmall(m));
    }
    //如果因子为一 则不输出, 因为和 p(n,n) 中的 +1 重复
    else if (m == 1) {
        return 0;
    }
    else if (n == m) {
        //输出return 1 的组合 
        sta.push(n);
        printOneResault();
        sta.pop();

        return function(n, getNextSmall(n)) + 1;
    }
    //n>m 则结果分解为有一定包含m因子  和 不一定包含m因子的  两群结果
    else if (n > m && m != 1) {
        //一定包括m 
        sta.push(m);
        resNum2 = function(n / m, n / m);
        sta.pop();

        //不一定包括 m 
        int smallM = getNextSmall(m);
        resNum1 = function(n, smallM);

        return resNum1 + resNum2;
    }
    //m>n 的情况
    else {
        return function(n, n);
    }
}

int main()
{
    int n;
    while (1) {
        printf("请输入一个数 : ");
        scanf("%d", &n);
        divisorsNum = 0;
        //获得所有因子 
        for (int i = 1; i <= n; i++) {
            if (n == (n / i) * i) {
                divisors[divisorsNum] = i;
                divisorsNum++;
            }
        }
        //获得所有组成
        printf("\n---> %d 的因式分解个数: %d\n", n, function(n, n));
    }
    return 0;
}