算法笔记 07_整数因子分解问题


★问题描述:

// 大于 1 的正整数 n 可以分解为:n = x1 * x2 * … * xm 
// 例如:当 n = 12 时,共有 8 种不同的分解式: 
// 12 = 12; 12 = 6 * 2; 12 = 4 * 3; 12 = 3 * 4; 12 = 3 * 2 * 2; 
// 12 = 2 * 6; 12 = 2 * 3 * 2; 12 = 2 * 2 * 3。 
// 对于给定的正整数 n,计算 n 共有多少种不同的分解式。

** 
**

★算法思想

//读到一个数 n,让其除以自己减 1 的数(n/n, n/(n-1), n/(n-2)…),当可以整除某个数 a 时,说明这种情况可以; 
//然而还要再进行深一层判断,首先判断这个除数 a 是否等于自身 n ,是的话计数器 count 直接加一,不是的话,判断除数 a 是否还可以再进行因子分解。 
**

★ C++ 代码(Visual Studio 2017):

#include"stdafx.h"
#include<iostream>
using namespace std;

int ZSFJ(int n) { 
    int count = 0;       //记录结果总数变量

    for(int i = n; i > 1; i --)
    {          
        if(n % i == 0)      //当 n 能整除 i 
        {           
            if (n != i)    //当 n 能整出 i 并且当 n 不等于 i,说明此时遍历到了 n 的某个因子,而这个因子也可以继续进行因子分解,那我们也将其进行递归运算 
                count += ZSFJ(n / i);       
            else
                count ++;   //说明 n 等于了 i, count + 1
        }    
    }         
    return count; 
} 

void main() 
{ 
    int n;      
    while (!0) 
    { 
        cout << "Please input the integer you like: " << endl;        
        cin >> n;        
        cout << "Result: " << ZSFJ(n) << endl; 
        cout << "____________________________________________________" << endl;
    }  
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论