黑马程序员技术交流社区

标题: 递归思想求解答 [打印本页]

---

作者: 上善若水。V    时间: 2015-4-24 16:50
标题: 递归思想求解答
用递归实现分解质因数：如12=2*2*3？课后作业想了半天，求解答

---

作者: 优质码农    时间: 2015-4-24 16:50
public class Test {
        public static void main(String[] args) {
                List<Long> factors = getFactors(12L, 2);
                System.out.println(factors);
        }

        /**
         * 通过递归实现分解质因数
         * @param n 要分解的数字
         * @param factor 起始因子
         * @return 分解结果
         */
        public static List<Long> getFactors(long n, long factor) {
                // 不断增大 factor 直到能整除 n
                while (n % factor != 0 && factor < n) {
                        // 得到 2,3,5,7,9,11,13,...
                        factor = (factor < 2) ? 2 : ((factor == 2) ? 3 : (factor + 2));
                }
                List<Long> result;
                if (factor >= n) { // 因子已经涨到和 n 一样大，说明 n 本身就是因子。这时递归完成。
                        result = new ArrayList<Long>();
                } else { // 因子能够整除 n，于是继续分解除以因子后的结果
                        result = getFactors(n / factor, factor); // 向下递归
                }
                result.add(factor);
                return result;
用递归实现的，嘻嘻，求奖赏！

---

作者: 43453186@qq.com    时间: 2015-4-26 23:51
if (factor >= n) { // 因子已经涨到和 n 一样大，说明 n 本身就是因子。这时递归完成。
                        result = new ArrayList<Long>();
                }

不太明白，能解释一下么，谢谢

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2