整式因子分解问题

1. 问题描述

  一个大于1的正整数可以分解为。例如，当时，共有8种不同的分解式：

•  算法设计：对于给定的正整数n，算出共有多少种不同的分解式。
•  数据输入：由文件input.txt给出输入数据。第一行有个正整数)。
•   结果输入：将计算的不同的分解式的数目输出到文件output.txt中。

1.1. 问题分析

  上面描述的分解式不考虑乘法的交换律，所以可以把第一个分解因子看作一个可以被12整除数字的遍历，剩下的因子就是一个递归问题，求解剩下因子的分解式即可，然后把每种因子的分解结果数相加，递归的返回条件是，因子等于1。

int solveInterger(int input){
    if(input <= 0){
        std::cout<<"input is illegal"<<std::endl;
        return -1;
    }
    int result = 0;
    if(input == 1)
        return 1;
    else
        for(int i = input; i > 1 && input % i == 0 ; i--){
                result = result + solveInterger(input/i);  //每种可整除因子递归结果求和
        }
    return result;
}

1.2. 算法分析

  算法中的循环边界是，其中是输入的数字，但是能够进入到循环中的次数肯定小于。进入循环之后通过递归调用一个更少规模的子问题，输入变成了。但是这其中必然存在重复多算的过程，即递归的是不独立的子问题，如下面的情形取：

两种情形的子问题都是求解6的整式分解问题，但是会出现多次求解的冗余过程，当数字n比较小的时候出现的这种情形的可能会比较低，但是当n很大时，会造成很坏的情况。

1.3. 实验验证

result.png