一、分治算法概念
“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换) 。
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
二、分治法的设计思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
三、分治策略
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
四、分治法实现步骤
①分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
②解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
③合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
- if |P|≤n0
- then return(ADHOC(P))
- 将P分解为较小的子问题P1,P2,…,Pk
- for i←1 to k
- do yi ← Divide-and-Conquer(Pi) 递归解决Pi
- T ← MERGE(y1,y2,…,yk) 合并子问题
- return(T)
五、可使用分治法求解的一些经典问题
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
六、汉诺塔
6.1 汉诺塔初始状态
[java实现]
public static void main(String[] args) {
solve(3);
}
public static void solve(int n) {
// 已知条件n个圆盘和A、B、C三根石柱
hanoi(n, "A", "B", "C");
}
/**
* 若要让第n个圆盘成功从A移动到C，需要让前n-1个圆盘先从A移动到B，然后让第n个圆盘从A移动到C，
* 最后让第n-1个圆盘从B移动到C，至于如何将前n-1个圆盘从A移动到B或者从A移动到C，仅仅是和父问
* 题相同的子问题，采用父问题的解决方案即可。
*/
private static void hanoi(int n, String a, String b, String c) {
if (n == 1) {
// 只有一个圆盘时直接从A石柱移动到C石柱
move(n, a, c);
} else {
// 将前n-1个圆盘从石柱A移动到石柱B
hanoi(n - 1, a, c, b);
// 将第n号圆盘从石柱A移动到石柱C
move(n, a, c);
// 将前n-1个圆盘从石柱B移动到石柱C
hanoi(n - 1, b, a, c);
}
}
private static void move(int n, String i, String j) {
System.out.println("第" + n + "个圆盘，" + "从" + i + "移动到" + j);
}
运行截图
6.2 运行截图
[JScript实现]
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>hano</title>
<style>
html, body {
margin: 0;
padding: 0;
height: 100%;
}
.header >#number {
display: inline-block;
width: 80%;
height: 28px;
box-sizing: border-box;
position: absolute;
left: 0;
}
.header > #sure {
display: inline-block;
width: 20%;
height: 28px;
box-sizing: border-box;
position: absolute;
right: 0;
}
#contain{
width: 100%;
background: skyblue;
padding: 10px;
text-align: center;
position: absolute;
top: 28px;
user-select: none;
}
.item{
display: inline-block;
box-sizing: border-box;
background: #ffffff;
border: 1px solid #ffffff;
border-radius: 10px;
width: 33%;
}
.item p{
font-size: 20px;
font-weight: bolder;
border-top: 1px solid #ffffff;
border-bottom: 1px solid #ffffff;
}
.item >.area div{
margin: 0 auto;
height: 20px;
}
</style>
</head>
<body>
<div class="header">
<input id="number" type="text" placeholder="please input number...">
<button id="sure">start</button>
</div>
<div id="contain">
<p>there will be showing result for you.</p>
<div>
<div class="item">
<p>A</p>
<div class="area" id="A"></div>
</div>
<div class="item">
<p>B</p>
<div class="area" id="B"></div>
</div>
<div class="item">
<p>C</p>
<div class="area" id="C"></div>
</div>
</div>
</div>
<script>
// 点击开始按钮事件
var sure = document.getElementById('sure');
sure.addEventListener('click', function () {
init();
}
) // 获取输入值
function getNumber() {
return document.getElementById('number').value;
}
// 渲染汉诺塔初始化
function init() {
// 生成三个柱子
var number = getNumber();
var A = document.getElementById('A');
var B = document.getElementById('B');
var C = document.getElementById('C');
// 清空柱子C
C.innerHTML = "";
var htmlA = "";
// 渲染柱子A
for (var i = 0; i < number; i++) {
htmlA += "<div style='width:" + 100 * ((i + 1) / number) + "%;background:" + randomColor() + "'></div>";
}
A.innerHTML = htmlA;
hano(number, A, B, C);
}
// 生成随机颜色
function randomColor() {
var colors = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
var color = '#';
for (var i = 0; i < 6; i++) {
color += colors[Math.floor(Math.random() * 16)] }
return color;
}
// 执行汉诺塔
function hano(n, A, B, C) {
if (n == 1) {
//汉诺塔移动代码
moveHano(A,C);
} else {
hano(n - 1, A, C, B);
hano(1, A, B, C);
hano(n - 1, B, A, C);
}
}
function moveHano(A, C) {
// objA 内部第一个元素 objA.childNodes[0]
debugger;
if(C.childNodes[0]){
C.insertBefore(A.childNodes[0],C.childNodes[0]);
} else{
C.appendChild(A.childNodes[0]);
}
}
</script>
</body>
</html>
http://192.168.45.2:8080/lianxi/js.jsp
运行截图
6.3 js实现
6.4 js实现
6.5 js实现
[python实现]
import turtle
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def drawpole_3():#画出汉诺塔的poles
t = turtle.Turtle()
t.hideturtle()
def drawpole_1(k):
t.up()
t.pensize(10)
t.speed(100)
t.goto(400*(k-1), 100)
t.down()
t.goto(400*(k-1), -100)
t.goto(400*(k-1)-20, -100)
t.goto(400*(k-1)+20, -100)
drawpole_1(0)#画出汉诺塔的poles[0]
drawpole_1(1)#画出汉诺塔的poles[1]
drawpole_1(2)#画出汉诺塔的poles[2]
def creat_plates(n):#制造n个盘子
plates=[turtle.Turtle() for i in range(n)]
for i in range(n):
plates[i].up()
plates[i].hideturtle()
plates[i].shape("square")
plates[i].shapesize(1,8-i)
plates[i].goto(-400,-90+20*i)
plates[i].showturtle()
return plates
def pole_stack():#制造poles的栈
poles=[Stack() for i in range(3)]
return poles
def moveDisk(plates,poles,fp,tp):#把poles[fp]顶端的盘子plates[mov]从poles[fp]移到poles[tp]
mov=poles[fp].peek()
plates[mov].goto((fp-1)*400,150)
plates[mov].goto((tp-1)*400,150)
l=poles[tp].size()#确定移动到底部的高度（恰好放在原来最上面的盘子上面）
plates[mov].goto((tp-1)*400,-90+20*l)
def moveTower(plates,poles,height,fromPole, toPole, withPole):#递归放盘子
if height >= 1:
moveTower(plates,poles,height-1,fromPole,withPole,toPole)
moveDisk(plates,poles,fromPole,toPole)
poles[toPole].push(poles[fromPole].pop())
moveTower(plates,poles,height-1,withPole,toPole,fromPole)
myscreen=turtle.Screen()
drawpole_3()
n=int(input("请输入汉诺塔的层数并回车:\n"))
plates=creat_plates(n)
poles=pole_stack()
for i in range(n):
poles[0].push(i)
moveTower(plates,poles,n,0,2,1)
myscreen.exitonclick()
6.6 python实现
6.7 python实现
网友评论