本文主要是介绍算法-17-分治算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

十七、分治算法

1、概念

分治（Divide-and-Conquer），分而治之，将一个复杂的问题，分成两个或多个相同或类似的子问题，再把子问题分成更小的子问题，直到问题简单到可以直接求解，再将所有的子问题的解合并成一个解，即原问题的解。

应用：快速排序、归并排序、二分查找、汉诺塔问题等

2、汉诺塔问题

一共有三根柱子，在其中一根柱子上，从上往下按照从小到大的顺序放着n个圆盘（64个）。现在需要将这些圆盘还按照从小到大的顺序放置到另外的一根柱子上，要求每次只能移动一个圆盘，且小圆盘只能放到大圆盘上。问全部移动过去，需要几步。

  -|-      |    |
 --|--     |    |
---|---    |    |
   左      中   右

1，3，7，15，31，63，127，255，511，1023

f (n) = f (n - 1) * 2 + 1

计算步骤

public long fn(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result = result * 2 + 1;
    }
    return result;
}

public long fn2(int n, long result) {
    if (1 == n) {
        return result;
    }
    return fn2(n - 1, result * 2 + 1);
}


n = 63, result = 9223372036854775807
n = 64, result = -1（超出Long的最大值）

解题示例

class HanoiTower {

    private int step;

    public void hanoi(int count, final String left, final String middle, final String right) {
        if (1 == count) {
            System.out.println("[" + (++step) + "]第1个盘：" + left + "===>" + right);
            return;
        }

        hanoi(count - 1, left, right, middle);
        System.out.println("[" + (++step) + "]第" + count + "个盘：" + left + "===>" + right);
        hanoi(count - 1, middle, left, right);
    }

}


class Test {

    public static void main(String[] args) {
        new HanoiTower().hanoi(3, "左", "中", "右");
    }

}

这篇关于算法-17-分治算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！