递推实现递推思想

 	/*递推实现递推思想*/public static Integer getSum1(Integer n) {if (n <= 0) return 0;//越界代偿Integer sum = 0;while (true) {if (n == 1) break;if (n % 2 == 0) n = n / 2;else n = n * 3 + 1;sum++;}return sum;}

递归实现递归思想

 	 /*递归实现递归思想*/public static Integer getSum2(Integer n) {if (n <= 0) return 0;//越界代偿if (n == 1) return 0;if (n % 2 == 0) return getSum2(n / 2) + 1;else return getSum2(n * 3 + 1) + 1;}

递归实现递推思想

 	 /*递归实现递推思想*/public static void getSum3(Integer n, int sum) {if (n <= 0) return;//越界代偿if (n == 1) {System.out.println(sum);return;}if (n % 2 == 0) getSum3(n / 2, ++sum);else getSum3(n * 3 + 1, ++sum);}

递推实现递归思想

 	/*借助栈数据结构递推实现递归思想*/public static Integer getSum4(Integer n) {if (n <= 0) return 0;//越界代偿var stack = new Stack<Integer>();stack.push(n);var sum = 0;while (true) {var top = stack.peek();if (top == 1) {var size = stack.size();for (int i = 0 ;i<size-1;i++){stack.pop();sum++;}break;}else if (top % 2 == 0) stack.push(top / 2);else stack.push(top * 3 + 1);}return sum;}
}

四种方法的特点

以下总结出自刘铁猛老师的《算法之禅》

方案	特点
递推实现递推思想	中规中矩，使用循环语句，有时候会有队列参与
递归实现递推思想	自顶向下式的递归代码，可使代码得到简化
递归实现递归思想	顺利成章，方法调用自己，自底向上，结果对其
递推实现递归思想	使用循环语句加栈数据结构，避免了调用栈的溢出

思维拓展

通过一个while从1到n去执行getSum1获得运算次数
并在运算过程中将其每次运算的结构放入一个队列（Queue）中
并将最终运算为1的结果次数，以及该数的数值存入hashmap中（key为数值，value为次数）
同时进行查重，如果有重复或者大于n的数直接Continue跳过

  	/*运算过程中将其每次运算的结构放入一个队列（Queue）中*/public static Integer getSum1(Integer n, LinkedList<Integer> numQ) {if (n <= 0) return 0;//越界代偿Integer sum = 0;while (true) {if (n == 1) break;if (n % 2 == 0) {n = n / 2;numQ.offer(n);} else {n = n * 3 + 1;numQ.offer(n);}sum++;}return sum;}

  	/*通过一个while从1到n去执行getSum1获得运算次数并在运算过程中将其每次运算的结构放入一个队列（Queue）中并将最终运算为1的结果次数，以及该数的数值存入hashmap中（key为数值，value为次数）同时进行查重，如果有重复或者大于n的数直接Continue跳过*/public static Map<Integer, Integer> getMaxSum(int n) {var sums = new HashMap<Integer, Integer>();var numQ = new LinkedList<Integer>();int i = 1;while (true) {if (i > n) break;if (numQ.contains(i)) {i++;continue;}var sum = getSum1(i, numQ);sums.put(i, sum);i++;}for (var num : numQ) {if (sums.containsKey(num) || num > n) continue;sums.put(num, getSum1(num));}return sums;}

此时可以通过loadMap()来查看刚创建的hashmap

    /*打印输出hashmap*/public static void loadMap(Map<Integer, Integer> map) {Iterator iter = map.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry = (Map.Entry) iter.next();Object key = entry.getKey();Object val = entry.getValue();System.out.printf("key=%d,val=%d\n", key, val);}}

public class Main {public static void main(String[] args) {long a= System.currentTimeMillis();//获取当前系统时间(毫秒)var sums= Homework.getMaxSum(10000);Homework.loadMap(sums);System.out.print("程序执行时间为：");System.out.println(System.currentTimeMillis()-a+"毫秒");}}

输出结果如下所示：
在这里插入图片描述
此时可以通过hashmap的键值对来查询1-10000的计算所需要的次数
再通过Map.Entry的排序，即可获取最大运算次数的数字

 	/*将hashmap中的value进行排序并打印输出*/public static void mapSort(Map<Integer, Integer> sums) {List<Map.Entry<Integer, Integer>> sumList = new ArrayList<>();for (var entry : sums.entrySet())sumList.add(entry);sumList.sort(new Comparator<Map.Entry<Integer, Integer>>() {@Overridepublic int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {return o2.getValue() - o1.getValue();}});for(Map.Entry<Integer, Integer> entry: sumList){System.out.printf("key=%d,val=%d\n", entry.getKey(), entry.getValue());}}

public class Main {public static void main(String[] args) {long a= System.currentTimeMillis();//获取当前系统时间(毫秒)var sums= Homework.getMaxSum(10000);Homework.mapSort(sums);System.out.print("程序执行时间为：");System.out.println(System.currentTimeMillis()-a+"毫秒");}}