当前课程知识点:计算思维导论 > 第七章 问题求解 > 7.12 算法策略之分治法 > 图文教学

分治法,分割问题、各个击破。将一个大问题,分割成许多小问题。如果小问题还是很难,就继续分割成更小的问题,直到问题变得容易解决。分割出来的小问题,称作「子问题」。解决一个问题,等价于解决所有子问题。用树形图表达原问题与子问题的关系,最好不过!

分治法着重分割问题的方式 ── 要怎么分割问题,使得子问题简单又好算?
示例:分解动作
想要学习「从中场带球上篮」,我们可以将此动作分割为「跑步运球」、「跑步收球」、「单手将球放入篮框」等动作,分别学习。每一项动作都熟练之后,组合起来便是带球上篮了。如果觉得「跑步运球」还是太难,可以更细分成「原地运球」、「走动运球」、「运球时护球」等动作,克服了之后便能够顺利解决「跑步运球」的问题了。

示例:方格求面积
左边为原问题,右边放大并细分的图是其中一个子问题。


示例1:二分求幂
计算机模拟手工计算 2^159 = ?
解析:
手工计算2^159,怎么计算?自然是判断指数,如果指数为奇数,则,2^奇数幂 = 2* 2^奇数幂-1,如:2^159 = 2 * 2^158,否则,指数为偶数幂,2^偶数幂 = 4^偶数幂的一半。如:2^158 =(2^2)^79 = 4^79。
求解过程,
2^159 =?
=2*2^158
=2*4^79
=2*4*4^78
=2*(4*16^39)
=……
=2*(4*(16*256*(256^2)* (256^2^2^2)^2))
伪代码如下:
被调函数
function f(x,n) // 求 x^n
if n=1 then
return x
endif
if n mod 2=1 then
return x*f(x, n-1)
else
return f(x^2, n/2)
endif
endfunction
流程图如下:

示例2:找假币
16个硬币中,混进了1枚假币。现在知道假币的重量比真币的质量要轻。给你一个天平,请用最快的时间把那个可恶的假币找出来。
解析:
当硬币总数为一,那么该币就是假币。当硬币总数为二,则两枚硬币分别放在天平两端秤重,较轻的一端就是假币。当硬币总数为三以上,一定有办法找出假币,以下介绍两种策略。采用递增法。每次取两枚硬币,放在天平两端秤重。当天平平衡,表示这两枚硬币都是真币,接着继续处理剩余硬币。当天平倾斜,比较轻的硬币就是假币。

采用分治法。两枚硬币放在天平两端秤重,当天平平衡,表示这两枚硬币都是真币。接着只剩下 N-2 枚硬币要寻找假币 ── 问题递归缩小了!剩下 N-2 枚,太多了一点。一次取多一点硬币,同时放在天平两端秤,问题就能缩小更多了!把所有硬币平均分成三份,取两份放在天平两端秤重。当天平平衡,表示剩下的一份含有假币,问题一次便缩小为 1/3 。当天平倾斜,表示比较轻的一份含有假币,问题一次便缩小为 1/3 。

伪代码如下:
input n=16, t=0
while n>1 do
t=t+1
n=n/3
endwhile
output t
流程图如下:

-1.1 计算与计算思维1
--计算与计算思维1
--图文教学
--1-1 巩固练习--作业
-1.2 计算与计算思维2
--计算与计算思维2
--图文教学
--1-2 巩固练习--作业
-1.3 计算工具与计算机
--计算工具与计算机
--图文教学
--什么是摩尔定律?
--1-3 巩固练习--作业
-实验1-1 初识计算思维
--计算机发展简史
--这才是大学
--实验1-1 初识计算思维
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-2.1 初识二进制
--初识二进制
--图文教学
--2-1 巩固练习--作业
-2.2 二进制的运算
--二进制的运算
--图文教学
--2-2 巩固练习--作业
-2.3 数制转换
--数制转换
--常见进制
--图文教学
--数制转换口诀
--2-3 巩固练习--作业
-2.4 数的表示
--数的表示
--图文教学
--负数补码问题
--2-4 巩固练习--作业
-2.5 字符编码
--字符编码
--图文教学
--汉字编码问题
--2-5 巩固练习--作业
-2.6 声音图像编码
--声音图像编码
--延伸学习:小趣闻
--图文教学
--2-6 巩固练习--作业
-本章小结
--知识点回顾
--习题与解析
--本章测验--作业
-3.1 计算机系统构成
--计算机系统构成
--图文教学
--3-1 巩固练习--作业
-3.2 主板
--主板
--图文教学
--主板的作用
--3-2 巩固练习--作业
-3.3 接口与总线
--接口与总线
--图文教学
--总线和接口的区别
--3-3 巩固练习--作业
-3.4 CPU
--CPU
--延伸学习:从沙子到CPU的制造过程告诉你造芯片到底有多难
--图文教学
--什么是主频?
--3-4 巩固练习--作业
-3.5 内存
--内存
--图文教学
--主流内存类型
--3-5 巩固练习--作业
-3.6 外存
--外存
--图文教学
--硬盘类型
--3-6 巩固练习--作业
-3.7 输入输出设备
--输入输出设备
--图文教学
--微机故障检测
--I/O设备
--3-7 巩固练习--作业
-3.8 计算机工作原理
--计算机工作原理
--图文教学
--人类与计算机
--3-8 巩固练习--作业
-3.9 操作系统1
--图文教学
--虚拟内存?
--3-9 巩固练习--作业
-3.10 操作系统2
--图文教学
--操作系统
--3-10 巩固练习--作业
-实验3-1 计算机原理与硬件组装
--上机实验3-1:计算机工作原理与硬件组装
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-4.1 初识网络
--初识网络
--图文教学
--4.1 巩固练习--作业
-4.2 网络分类
--网络分类
--图文教学
--校园网
--4.2 巩固练习--作业
-4.3 网络体系结构
--网络体系结构
--图文教学
--4.3 巩固练习--作业
-实验4-1:简单网络布线
-4.4 网络设备
--网络设备
--图文教学
--4.4 巩固练习--作业
-实验4-2:将计算机添加到现有网络中
-4.5 局域网搭建
--局域网搭建
--图文教学
--4.5 巩固练习--作业
-实验4-3 无线路由器连接与设置
-4.6 IP与域名系统
--IP与域名系统
--图文教学
--4.6 巩固练习--作业
-实验4-4:测试无线连接
-4.7 划分子网
--划分子网
--图文教学
--子网掩码
--4.7 巩固练习--作业
-4.8 Internet 服务
--工信部部长谈5G
--图文教学
--4.8 巩固练习--作业
-4.9 数字公民与网络安全
--图文教学
--数字签名
--4.9 巩固练习--作业
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-5.1 数据库基本概念
--数据库基本概念
--图文教学
--5.1 巩固练习--作业
-5.2 数据库的设计方法
--图文教学
--数据库的设计步骤
--5.2 巩固练习--作业
-5.3 数据库的规范化设计1
--图文教学
--为什么要规范化数据库设计?如果不规范化设计会有什么问题?
--5.3 巩固练习--作业
-5.4 数据库的规范化设计2
--图文教学
--规范化设计数据库
--5.4 巩固练习--作业
-5.5 ACCESS数据库的创建与查询
--图文教学
--主键与外键
--5.5 巩固练习--作业
-5.6 关系代数理论
--关系代数理论
--图文教学
--5.6 巩固练习--作业
-5.7 SQL语句查询
--SQL语句查询
--图文教学
--5.7 巩固练习--作业
-实验5-1:数据库设计与实现(PBL直播课)
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-6.1 逻辑思维及其训练方法
--图文教学
--白马非马论
--6-1 巩固练习--作业
-6.2 命题及命题判断
--命题及命题判断
--图文教学
--命题判断条件
--6.2 巩固练习--作业
-6.3 命题符号化
--命题符号化
--图文教学
--蕴含运算符
--6-3 巩固练习--作业
-6.4 布尔代数与真值表
--布尔代数与真值表
--图文教学
--构造真值表
--6-4 巩固练习--作业
-6.5 命题演算和逻辑推理
--图文教学
--永真式和永假式
--6-5 巩固练习--作业
-实验6-1:用真值表进行逻辑推理(PBL录屏课)
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-7.1 什么是问题求解
--什么是问题求解
--图文教学
--7-1 巩固练习--作业
-7.2 算法与算法描述
--算法与算法描述
--图文教学
--算法描述方法
--7-2 巩固练习--作业
-7.3 顺序结构设计
--顺序结构设计
--图文教学
--温度转换问题
--7-3 巩固练习--作业
-7.4 选择结构设计
--选择结构设计
--图文教学
--7-4 巩固练习--作业
-7.5 循环结构设计
--循环结构设计
--图文教学
--7-5 巩固练习--作业
-7.6 算法策略基础之数组
--图文教学
--7.6 巩固练习--作业
-7.7 算法策略基础之函数
--图文教学
--用户自定义函数
--7.7 巩固练习--作业
-实验7-1:Raptor的基本操作(PBL录屏课)
-7.8 算法策略之枚举法
--算法策略之枚举法
--图文教学
--7-8 巩固练习--作业
-7.9 算法策略之递归法
--算法策略之递归法
--图文教学
--德罗斯特效应
--7.9 巩固练习--作业
-7.10 算法策略之递推法
--算法策略之递推法
--图文教学
--7-10 巩固练习--作业
-7.11 算法策略之迭代法
--算法策略之迭代法
--图文教学
--7-11 巩固练习--作业
-实验7-2:算法设计与分析(PBL直播课)
-7.12 算法策略之分治法
--算法策略之分治法
--图文教学
--分治法思想
--7-12 巩固练习--作业
-7.13 算法策略之动态规划
--图文教学
--什么是动态规划?
--7-13 巩固练习--作业
-7.14 算法策略之贪心算法
--图文教学
--贪心策略
--7.14 巩固练习--作业
-7.15 算法策略之回溯法
--算法策略之回溯法
--图文教学
--回溯现象
--7-15 巩固练习--作业
-7.16 算法策略之查找算法
--图文教学
--7-16 巩固练习--作业
-7.17 算法策略之排序算法
--图文教学
--冒泡排序
--7-17 巩固练习--作业
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-8.1 数据挖掘概述
--数据挖掘概述
--图文教学
--数据挖掘案例
--8-1 巩固练习--作业
-8.2 数据采集
--数据采集
--图文教学
--数据采集
--8-2 巩固练习--作业
-8.3 数据探索之数据质量分析
--图文教学
--异常值处理
--8-3 巩固练习--作业
-8.4 数据探索之数据特征分析
--图文教学
--帕累托法则
--8-4 巩固练习--作业
-8.5 数据特征分析之分布分析
--图文教学
--分组方法
--8-5 巩固练习--作业
-8.6 数据特征分析之统计分析
--图文教程
--加权平均数
--8-6 巩固练习--作业
-8.7 数据特征分析之统计分析(续)
--图文教学
--无量纲数
--8-7 巩固练习--作业
-8.8 数据预处理
--数据预处理
--图文教学
--数据预处理
--8-8 巩固练习--作业
-8.9 数据挖掘之分类
--数据挖掘之分类
--图文教学
--8-9 巩固练习--作业
-8.10 数据挖掘之预测
--数据挖掘之预测
--图文教学
--分类与预测
--8-10 巩固练习--作业
-8.11 数据挖掘之聚类分析
--图文教学
--聚类和分类
--8-11 巩固练习--作业
-8.12 数据挖掘之关联规则
--图文教学
--智能推荐系统
--8-12 巩固练习--作业
-本章小结
--知识点回顾
--习题与解析
--章节自测--作业
-期中考试(1-4章)
-期末考试(5-8章)





