题目：
输入一个数字n 如果n为偶数则除以2，若为奇数则加1或者减1，直到n为1，求最少次数 写出一个函数
首先，这道题肯定可以用动态规划来解，
n为整数时，n的解为 n/2 的解加1
n为奇数时，n的解为 (n+1)/2 和 (n-1)/2 的解中较小的解加2
通过这个思路，我们可以自底向上依次计算出n的解，代码如下
public static int getNum(int n) {
if(n<1) {
return 0;
}
int[] res = new int[n+1];
res[0] = 0;
res[1] = 0;
for(int i=2;i<=n;i++) {
if((i&1) == 0) {
res[i] = res[i/2] + 1;
}else {
res[i] = Math.min(res[(i+1)/2], res[(i-1)/2]) + 2;
}
}
return res[n];
}
通过上面的思路可以得到问题的解，但是由于是自底向上依次计算n的解，所以有很多不必要的计算，时间效率和空间效率都不高。
比如，当计算n=100时，如果已经知道n=50的解，那么就可以得出n=100的解，所以n=51到n=99都是没有必要计算的。
如果仍然通过自底向上计算，那么想要忽略51到99这一区间的数字的计算是比较麻烦的，如果是自顶向下计算则容易做到，通过n可以确定只要计算 n/2,(n-1)/2 , (n+1)/2，这三个数就 行，利用递归来做代码如下
public static int getNum2(long n) {
if(n<=1) {
return 0;
}
if((n&1) == 0) {
return getNum2(n/2) + 1;
}else {
long a = (n-1) / 2;
long b = (n+1) / 2;
return Math.min(getNum2(a), getNum2(b)) + 2;
}
}
递归来做这道题简单明了。
递归也有递归的坏处，首先递归最可能问题就是递归深度的问题，很可能造成栈溢出。虽然对这道题来说，几乎不会出现这个问题，但是在用递归做其他问题的时候一定要考虑到这一点。
至于为什么这道题不会造成栈溢出，自己想吧
所有的递归算法都可以转化成非递归算法，这道题也一样，同样的，递归时还有一个小问题，就是它没有复用子问题的解，对于每个子问题，不管之前是否已经计算过解，都要再重新计算一次，转化成非递归算法时可以一并解决这个问题，代码如下
public static int getNum3(long n) {
MyTask task = new MyTask(n);
ForkJoinPool pool = new ForkJoinPool();
int res = pool.invoke(task);
pool.shutdown();
return res;
}
static class MyTask extends RecursiveTask<Integer> {
private long number;
private static final Map<Long,Integer> map = new ConcurrentHashMap<>();
public MyTask(long number) {
super();
this.number = number;
}
private synchronized void put(Long a,Integer b) {
if(map.containsKey(a)) {
System.out.println("had existed!");
}else {
map.put(a, b);
}
}
private Integer get(Long a) {
System.out.println("success");
return map.get(a);
}
@Override
protected Integer compute() {
if(number<=1) {
put(number, 0);
return 0;
}else if(map.containsKey(number)) {
return get(number);
}
int res = 0;
if((number&1) == 0) {
MyTask task = new MyTask(number / 2);
try {
res = task.fork().get() + 1;
put(number, res);
} catch (Exception e) {
e.printStackTrace();
}
return res;
}else {
MyTask task1 = new MyTask((number-1) / 2);
MyTask task2 = new MyTask((number+1) / 2);
try {
int a = task1.fork().get() + 2;
int b = task2.fork().get() + 2;
res = Math.min(a,b);
put(number, res);
} catch (Exception e) {
e.printStackTrace();
}
return res;
}
}
}
这个解法是将第二种解法的递归算法转化成了非递归算法，同时保存了之前已经计算过的子问题的解，并且用到了java中的fork/join框架，至于为什么要用这个框架，原因是，不用它我不知道怎么把这个递归算法转化成非递归算法，望各路大神指点指点
对于这道题来说，第二种方式最快，第三种方式其次，最后是第一种方式，而且第一种方式计算的n的最大值，也远远小于后两种。
好了，就先写到这，人生的第一篇博文就此诞生！庆祝！虽然写的我自己看了都觉得很烂，但是一步一步来嘛