解题思路:
根据公式f(n) = k * f(n / k)建立递归,采用记忆化递归减少重复计算
注意事项:
理解递归公式,debug了半天才发现问题所在
参考代码:
import java.util.Scanner; /** * @author Alex * @date 2018/2/24 */ public class Basic_16 { public static void main(String[] args) { Scanner input = new Scanner(System.in); int begin, end; begin = input.nextInt(); end = input.nextInt(); items = new String[end + 1]; fun(begin, end); } private static void fun(int begin, int end) { for (int i = begin; i <= end; i++) { System.out.print(i + "="); builder = new StringBuilder(); decomposition(i); System.out.println(builder.toString()); } } //记忆化递归 private static String[] items; private static StringBuilder builder; private static void decomposition(int n) { if (items[n] != null) { builder.append(items[n]); } //找到第一个能够分解的素数就停止循环 for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { builder.append(i + "*"); decomposition(n / i); return ; } } builder.append(n); return ; } }
0.0分
1 人评分