2023年高中信息技术教学课件 分治算法

分治算法 2023年高中信息技术教学课件 主要内容 1.分治思想 2.经典问题 3.基于一维的分治 4.基于二维的分治 5.点分治 分治思想 分治(Divide-And-Conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。 其三个步骤如下： ①划分问题(Divide)：将原问题分成一系列子问题。 ②递归解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。 ③合并问题(Combine)：将子问题的结果合并成原问题的解。 如快速排序、归并排序等都是采用分治思想。 分治算法设计过程图 问题S 问题S 问题S S的解 问题S1 …… 问题S2 问题Si 问题Sn …… S1的解 …… S2的解 Si的解 Sn的解 …… 问题的分解 子集解的合并 递归求解子问题 经典问题1—棋盘覆盖 有一个2k*2k的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。如下图所示为L型牌的4种旋转方式。 经典问题1—棋盘覆盖 题目是要求用L型牌覆盖一个2k*2k的方格棋盘，棋盘有且只有一个黑色方格，且此方格不能被覆盖。 用分治来解决，把原棋盘平均分为4块，通过用1个L型牌覆盖棋盘正中间2*2的区域中的三个格子，把原棋盘分成4块2k-1*2k-1的方格棋盘,且每块中只含有一个黑色方格(不能覆盖的格子)。 此时把原问题分解成4个结构与原问题一样的子问题，棋盘的大小(边长)每次减半，最终会出现边长为1的情况，直接求解即可。 经典问题1—棋盘覆盖 定义cover(x,y,len,x0,y0)表示求解左上角格子在(x,y)边长为len,其中(x0,y0)不能覆盖的棋盘覆盖方案。 根据黑色格子的位置分为以下四种情况： 情况1：黑点位于左上部分 情况2：黑点位于左下部分 递归求解 划分问题 左上:cover(x,y,len/2,x0,y0) 左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1) 右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2) 右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2) 递归求解 划分问题 左上:cover(x,y,len/2,x+len/2-1,y+len/2-1) 左下:cover(x+len/2,y,len/2,x0,y0) 右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2) 右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2) 经典问题1—棋盘覆盖 情况3：黑点位于右上部分 情况4：黑点位于右下部分 每个格子只会被处理一次，时间复杂度为O(n^2)，n为棋盘边长。 递归求解 划分问题 左上:cover(x,y,len/2, x+len/2-1,y+len/2-1) 左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1) 右上:cover(x,y+len/2,len/2,x0,y0) 右下:cover(x+len/2,y+len/2,len/2,x+len/2,y+len/2) 递归求解 划分问题 左上:cover(x,y,len/2,x+len/2-1,y+len/2-1) 左下:cover(x+len/2,y,len/2,x+len/2,y+len/2-1) 右上:cover(x,y+len/2,len/2,x+len/2-1,y+len/2) 右下:cover(x+len/2,y+len/2,len/2,x0,y0) 经典问题1—棋盘覆盖—代码 void cover(int x,int y,int len,int x0,int y0) { int t,len1; if (len==1)return; t=++tot; len1=len/2; if (x0<x+len1&&y0<y+len1)cover(x,y,len1,x0,y0); else{board[x+len1-1][y+len1-1]=t;cover(x,y,len1,x0+len1-1,y0+len1-1);} if (x0>=x+len1&&y0<y+len1)cover(x+len1,y,len1,x0,y0); else{board[x+len1][y+len1-1]=