• 【算法设计zxd】第5章分治法

    目录

    分治算法策略的设计模式

    分治思想：

    分治算法求解问题的步骤：

    设计模式

    算法分析

    二分查找算法

    思考题

    计算模型：

    时间复杂度分析：

    代码：

    分治*大数乘法：

    【例5-2】设X, Y是两个n位的十进制数，求X*Y

     问题分析：

    1.1 计算方法：

     2.1 计算方法：

    思考题：

     算法分析：

    代码：

    思考题：二分治法 和 VS算法 矩阵相乘

    算法效率：

    代码：

     棋盘覆盖问题：

    【例5-4】残缺棋盘

    问题分析：s=size/2 分治

    计算模型​

    算法分析

    算法设计与描述：​

    代码： 

     选择性问题：——非等分

    一般性描述：

    问题分析：

    选择性问题：选第k小值

    计算模型

    算法分析

    代码：

    思考题：正元素 负元素排序

    计算模型：

    思考题：用分治法 求 数列的最大子段和

    分治算法策略的设计模式

    分治思想：

    把一个较大的问题分解成几个与原问题相似的 子问题，
    找到求出这几个子问题的解法后，
    再以适当的方法组织，把它们合成求整个问题的解。

    分治算法求解问题的步骤：

    (1) 分解：将要解决的问题划分成若干规模较小的同类问题；
    (2) 求解：当子问题划分得足够小时，用较简单的方法解决；
    (3) 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。

    设计模式

    算法分析

    用DC求解规模为n0 的问题耗费1个单位时间，用Merge合并 k个子问题的所需的时间为f(n)
    ，则分治算法的时间复杂度 为：

     根据主定理有

     

    原问题分为多少个子问题比较合适？每个子问题是否规模要多大？

    【子问题平衡原理】划分规模：等长>不等长规模 

    二分查找算法

    【例5-1】 设有n个元素的集合a[0]~a[n-1]是有序的，设计算
    法从这n个元素中找出值为x的特定元素。
    问题分析
    思想：将n个元素分成个数大致相同的两半，取a[n/2]与x作
    比较。如果x=a[n/2]，则找到x，算法终止。如果x
    在集合的前半部分继续查找，否则在后半部分查找。
    计算模型
    (1)中间下标为mid =(left+right)/2。
    (2)找到待查数据，即有x==a[mid]；
    (3)暂未查到数，若xa[mid]，则
    left=mid+1。
    算法描述
    输入：x和n个元素的数组a[n]
    输出：与x匹配的数组元素下标或未找到（下标为-1）

    思考题

     

    计算模型：

    只剩一个数据时 max=x[low]

    对元素进行分组，中间下标mid=(low+high)/2，递归使用findmax(x,low,mid,tempmax1) ,findmax(x,mid+1,high,tempmax2) 返回两区间最大值tempmax1 和tempmax2

    最大值为tempmax1 和tempmax2 的较大值，

    时间复杂度分析：

    T(n) = 2*T(n/2) + 5; n>1

    T(n)=O(1) ;n=1

    设a=2 b=2 f(n)=5=n^(log_2 2-1)=O(1)   

    根据主定理 T(n)=O(n)

    代码：
     

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. void findmax(int x[],int low,int high,int &max)
    6. {
    7. 	int tempmax1=0,tempmax2=0;
    8. 	if(low==high)
    9. 	{
    10. 		max = x[low] ;
    11. 		return ;
    12. 	}
    13. 	int mid=(low+high)/2;
    14. 	findmax(x,low,mid,tempmax1);
    15. 	findmax(x,mid+1,high,tempmax2);
    16. 	if(tempmax2< tempmax1)max=tempmax1;
    17. 	else max=tempmax2;
    18. }
    19.  
    20. int main()
    21. {
    22. 	int n=10;
    23. 	int x[n];
    24. 	for(int i=0;i
    25. 	{
    26. 		x[i]=30+rand()%10;
    27. 		cout<" ";
    28. 	}
    29. 	int max=0;
    30. 	findmax(x,0,n-1,max);
    31. 	cout<
    32. 	
    33. 	return 0;
    34. }

    分治*大数乘法：

    【例5-2】设X, Y是两个n位的十进制数，求X*Y

     

     问题分析：

    1.1 计算方法：

     1.2 时间复杂度：

     

     2.1 计算方法：

     

     2.2 时间复杂度：

     

     计算模型

    （1） 计算公式

     （2）递归结束条件

    当x=0或y=0时，结果为0。
    当n=1时，返回x*y 。

    思考题：

    算法描述

    输入：两个n位十进制数x,y 

    核心操作：三个乘法

    时间复杂度：T(n)=3*T(n/2)+c*n 

    设a=3,b=2 ,f(n)=cn, n^{log_2 3-log_2 3/2} = n,

    有f(n)=\Theta ( n^{log_2 3-log_2 3/2} )= \Theta (n),取\varepsilon=log_2 3/2 >0 符合主定理（1），因此

     

     算法分析：

    算法设计与描述算法分析
    输入：两个n位十进制数
    输出：乘积
    Karatsuba(x,y)
    {
        if(x==0||y==0)return 0;
        if(n==1)return x*y;
        n<- n/2;
        x1<- x / (int)pow(10,n) ,x0<- x % (int)pow(10,n);
        y1<- y/ (int)pow(10,n),y0<- y % (int)pow(10,n);
        //计算
        xy1<- Karatsuba(x1,y1);
        xy0<- Karatsuba(x0,y0);
        sum<- (x1-x0)*(y0-y1);
        return xy1*pow(10,(2*half) ) + (sum+xy1+xy0)*pow(10,half) +xy0;
    }

    （1）输入两个n位十进制数，

    (2)核心语句：将两数分为前后两部分x1 x0 y1 y0，递归计算

    （3）

     时间复杂度：T(n)=3*T(n/2)+c*n 

    设a=3,b=2 ,f(n)=cn, n^{log_2 3-log_2 3/2} = n,

    有f(n)=\Theta ( n^{log_2 3-log_2 3/2} )= \Theta (n),取\varepsilon=log_2 3/2 >0 符合主定理（1），因此

     

    代码：

    1. #include<bits/stdc++.h>
    2. using namespace std; 
    3. /*
    4. unsigned int 0～4294967295
    5. int -2147483648～2147483647
    6. unsigned long 0～4294967295
    7. long -2147483648～2147483647
    8. long long的最大值：9223372036854775807
    9. long long的最小值：-9223372036854775808
    10. unsigned long long的最大值：18446744073709551615
    11.  
    12. __int64的最大值：9223372036854775807
    13. __int64的最小值：-9223372036854775808
    14. unsigned __int64的最大值：18446744073709551615
    15. */
    16.  
    17.  
    18. //Karatsuba方法 将大数拆分  两数位数相同 
    19. //分治 
    20. long long Karatsuba(long long num1,long long num2)
    21. {
    22. //	cout<<num1<<" "<<num2<<endl;
    23. 	if(num1<10 ||num2<10)return num1*num2;
    24. 	int size1=ceil(log(num1)/log(10));//位数 
    25. 	int size2=ceil(log(num2)/log(10));
    26. 	int half=max(size1,size2)/2;
    27. //	cout<<size1<<" h "<<half<<endl;
    28. 	//拆分为 abcd
    29. 	long long x1=num1 / (int)pow(10,half) ,x0= num1 % (int)pow(10,half);
    30. 	long long y1=num2/ (int)pow(10,half),y0=num2 % (int)pow(10,half);
    31. //	cout<<x1<<"  "<<x0<<endl;
    32. 	//计算
    33. 	long long xy1=Karatsuba(x1,y1);
    34. 	long long xy0=Karatsuba(x0,y0);
    35. 	long long sum= (x1-x0)*(y0-y1);
    36. //	cout<<pow(10,5)<<endl;
    37. 	return xy1*pow(10,(2*half) ) + (sum+xy1+xy0)*pow(10,half) +xy0;
    38. }
    39.  
    40. int main()
    41. {
    42. 	cout<<endl<<"Karatsuba:"<<Karatsuba(155,999);//但是要注意 long long的数字限制 
    43. 	
    44. 	return 0;
    45. }
    46.  
    47.

    思考题：二分治法 和 VS算法 矩阵相乘

    算法效率：

    普通的二分治算法：

    T(n)=O(1) n=2

    T(n)=8*T(n/2)+\Theta(n^2) n>2

    设a=8,b=2,f(n)=\Theta(n^2),n^(log_2 8 -1)=n^2.  

    有f(n)=\Theta(log_2 8 -1)=\Theta(n^2) 取 \varepsilon=1>0 

    根据主定理 T(n)=\Theta(n^3) 

    VS算法：【8次->7次乘法 m不唯一，但也增加了加法运算量】

    T(n)=O(1) n=2

    T(n)=7*T(n/2)+\Theta(n^2) 

    设a=7,b=2,f(n)=\Theta(n^2),n^(log_2 7 -1)=n^2.  

    有f(n)=\Theta(log_2 7 -0.8)=\Theta(n^2) 取\varepsilon =0.8>0  

    根据主定理 T(n)=\Theta(n^2.8)

    7个乘法，18个加法 

    因此VS算法比普通二分治算法效率高

    代码：

    1. #include
    2. using namespace std;
    3.  
    4. class Mat{
    5. 	
    6. public:
    7. 	int **m;
    8. 	int n;
    9. 	
    10. 	Mat(int nn){
    11. //		cout<<"Mat:"<
    12. 		n=nn;
    13. 		m=new int*[n];
    14. 		for(int i=0;i
    15. 		{
    16. 			m[i]=new int[n];
    17. 		}
    18. 		for(int i=0;i
    19. 		{
    20. 			for(int j=0;j
    21. 			{
    22. 				m[i][j]=0;
    23. 			}
    24. 		}
    25. //		cout<<"over"<
    26. 	}
    27. 	void input01(int** x)
    28. 	{
    29. 		int n=this->n;
    30. 		for(int i=0;i
    31. 		{
    32. 			for(int j=0;j
    33. 			{
    34. 				this->m[i][j]=x[i][j];
    35. 			}
    36. 		}
    37. 	}
    38. 	void show()
    39. 	{
    40. 		for(int i=0;i
    41. 		{
    42. 			for(int j=0;j
    43. 			{
    44. 				cout<"\t";
    45. 			}
    46. 			cout<
    47. 		}cout<
    48. 	}
    49. 	Mat operator + (Mat &a)// 定义重载运算符"+"的友元函数
    50. 	{
    51. 		Mat c(a.n);
    52. 		for(int i=0;i
    53. 		{
    54. 			for(int j=0;j
    55. 			{
    56. 				c.m[i][j]=a.m[i][j]+this->m[i][j];
    57. 			}
    58. 		}
    59. 		return c;
    60. 	}
    61. 	Mat operator - (Mat &a)// 定义重载运算符"-"的友元函数
    62. 	{
    63. 		Mat c(a.n);
    64. 		for(int i=0;i
    65. 		{
    66. 			for(int j=0;j
    67. 			{
    68. 				c.m[i][j]=this->m[i][j] -a.m[i][j];
    69. 			}
    70. 		}
    71. 		return c;
    72. 	}
    73. };
    74. int ** change(int x[][4])
    75. {
    76. 	int n=4;
    77. //	int **xx=malloc(4*sizeof(int*));
    78. 	int **xx=new int*[4];
    79. 	for(int i=0;i
    80. 	{
    81. 		xx[i]=new int[4];
    82. 		for(int j=0;j
    83. 		{
    84. 			xx[i][j]=x[i][j];
    85. 			cout<"\t";
    86. 		}
    87. 		cout<
    88. 	}
    89. 		cout<
    90. 	return xx;
    91. }
    92.  
    93. int a[4][4]={
    94. 1,0,2,1,
    95. 4,1,1,0,
    96. 0,1,3,0,
    97. 5,0,2,1
    98. };
    99. int **aa=change(a);
    100.  
    101. int b[4][4]={
    102. 0,1,0,1,
    103. 2,1,0,4,
    104. 2,0,1,1,
    105. 1,3,5,0
    106. };
    107. int **bb=change(b);
    108.  
    109. int n=4;
    110. Mat ma(n),mb(n),mc01(n),mc02(n);
    111.  
    112. //二分治法
    113.  
    114. void bs(int n,Mat a,Mat b,Mat c)
    115. {
    116. //	cout<
    117. 	if(n==1)
    118. 	{
    119. 		c.m[0][0]=ma.m[0][0] * mb.m[0][0];
    120. //		cout<<"n==1"<
    121. 		return ;
    122. 	}
    123. 	else if(n==2)
    124. 	{
    125. //		cout<<"n==2"<
    126. 		c.m[0][0]=a.m[0][0]*b.m[0][0]+a.m[0][1]*b.m[1][0];
    127. 		c.m[0][1]=a.m[0][0]*b.m[0][1]+a.m[0][1]*b.m[1][1];
    128. 		c.m[1][0]=a.m[1][0]*b.m[0][0]+a.m[1][1]*b.m[1][0];
    129. 		c.m[1][1]=a.m[1][0]*b.m[0][1]+a.m[1][1]*b.m[1][1];
    130. 		
    131. //		cout<<"n==2"<
    132. 		return ;
    133. 	}
    134. 	//划分为4个矩阵
    135. 	
    136. 	Mat a00(n/2),a01(n/2),a10(n/2),a11(n/2);
    137. 	Mat b00(n/2),b01(n/2),b10(n/2),b11(n/2);
    138. //	cout<<"划分"<
    139. 	for(int i=0;i2;++i)
    140. 	{
    141. 		for(int j=0;j2;++j)
    142. 		{
    143. 			//左上 
    144. //			cout<<"左上"<
    145. 			a00.m[i][j]=a.m[i][j];
    146. 			b00.m[i][j]=b.m[i][j];
    147. //			cout<<"右上"<
    148. 			//右上 
    149. 			a01.m[i][j]=a.m[i][j+n/2];
    150. 			b01.m[i][j]=b.m[i][j+n/2];
    151. 			//左下 
    152. 			a10.m[i][j]=a.m[i+n/2][j];
    153. 			b10.m[i][j]=b.m[i+n/2][j];
    154. 			//右下 
    155. 			a11.m[i][j]=a.m[i+n/2][j+n/2];
    156. 			b11.m[i][j]=b.m[i+n/2][j+n/2];
    157. 			
    158. 		}
    159. 	}
    160. //	cout<<"递归"<
    161. 	//递归求四个方阵
    162. 	Mat ab0000(n/2);
    163. 	bs(n/2,a00,b00,ab0000);
    164. 	Mat ab0110(n/2);
    165. 	bs(n/2,a01,b10,ab0110);
    166. 	Mat ab0001(n/2);
    167. 	bs(n/2,a00,b01,ab0001); 
    168. 	Mat ab0111(n/2);
    169. 	bs(n/2,a01,b11,ab0111);
    170. 	Mat ab1000(n/2);
    171. 	bs(n/2,a10,b00,ab1000);
    172. 	Mat ab1110(n/2);
    173. 	bs(n/2,a11,b10,ab1110);
    174. 	Mat ab1001(n/2);
    175. 	bs(n/2,a10,b01,ab1001);
    176. 	Mat ab1111(n/2);
    177. 	bs(n/2,a11,b11,ab1111);
    178. 	
    179. 	Mat c00(n/2),c01(n/2),c10(n/2),c11(n/2);
    180. 	c00=ab0000+ab0110;
    181. 	c01=ab0001+ab0111;
    182. 	c10=ab1000+ab1110;
    183. 	c11=ab1001+ab1111;
    184. //	c00 =m1+m4-m5+m7;
    185. //	c01 =m3+m5;
    186. //	c10=m2+m4;
    187. //	c11=m1+m3-m2+m6;
    188.  
    189. 	//合并
    190. 	for(int i=0;i2;++i)
    191. 	{
    192. 		for(int j=0;j2;++j)
    193. 		{
    194. 			c.m[i][j]=c00.m[i][j];
    195. 			c.m[i][j+n/2]=c01.m[i][j];
    196. 			c.m[i+n/2][j]=c10.m[i][j];
    197. 			c.m[i+n/2][j+n/2]=c11.m[i][j];
    198. 		}
    199. 	 } 
    200. }
    201.  
    202. //VS算法
    203.  
    204.  
    205. void vs(int n,Mat a,Mat b,Mat c)
    206. {
    207. //	cout<
    208. 	if(n==1)
    209. 	{
    210. 		c.m[0][0]=ma.m[0][0] * mb.m[0][0];
    211. //		cout<<"n==1"<
    212. 		return ;
    213. 	}
    214. 	else if(n==2)
    215. 	{
    216. //		cout<<"n==2"<
    217. 		c.m[0][0]=a.m[0][0]*b.m[0][0]+a.m[0][1]*b.m[1][0];
    218. 		c.m[0][1]=a.m[0][0]*b.m[0][1]+a.m[0][1]*b.m[1][1];
    219. 		c.m[1][0]=a.m[1][0]*b.m[0][0]+a.m[1][1]*b.m[1][0];
    220. 		c.m[1][1]=a.m[1][0]*b.m[0][1]+a.m[1][1]*b.m[1][1];
    221. 		
    222. //		cout<<"n==2"<
    223. 		return ;
    224. 	}
    225. 	//划分为4个矩阵
    226. 	
    227. 	Mat a00(n/2),a01(n/2),a10(n/2),a11(n/2);
    228. 	Mat b00(n/2),b01(n/2),b10(n/2),b11(n/2);
    229. //	cout<<"划分"<
    230. 	for(int i=0;i2;++i)
    231. 	{
    232. 		for(int j=0;j2;++j)
    233. 		{
    234. 			//左上 
    235. //			cout<<"左上"<
    236. 			a00.m[i][j]=a.m[i][j];
    237. 			b00.m[i][j]=b.m[i][j];
    238. //			cout<<"右上"<
    239. 			//右上 
    240. 			a01.m[i][j]=a.m[i][j+n/2];
    241. 			b01.m[i][j]=b.m[i][j+n/2];
    242. 			//左下 
    243. 			a10.m[i][j]=a.m[i+n/2][j];
    244. 			b10.m[i][j]=b.m[i+n/2][j];
    245. 			//右下 
    246. 			a11.m[i][j]=a.m[i+n/2][j+n/2];
    247. 			b11.m[i][j]=b.m[i+n/2][j+n/2];
    248. 			
    249. 		}
    250. 	}
    251. //	cout<<"递归"<
    252. 	//递归求四个方阵
    253. 	int half=n/2;
    254. 	//m1=(a00+a11)*(b00+b11)
    255. 	Mat m1(n/2);
    256. 	vs(n/2,a00+a11,b00+b11,m1);
    257. //	cout<<"m1"<
    258. 	//m2=(a10+a11)*(b00)
    259. 	Mat m2(n/2);
    260. 	vs(n/2,a10+a11,b00,m2);
    261. 	//m3=(a00)*(b01-b11)
    262. 	Mat m3(n/2);
    263. 	vs(n/2,a00,b01-b11,m3);
    264. 	//m4=(a11)*(b10-b00)
    265. 	Mat m4(n/2);
    266. 	vs(n/2,a11,b10-b00,m4);
    267. 	//m5=(a00+a01)*(b11)
    268. 	Mat m5(n/2);
    269. 	vs(n/2,a00+a01,b11,m5);
    270. 	//m6=(a10-a00)*(b00+b01)
    271. 	Mat m6(n/2);
    272. 	vs(n/2,a10-a00,b00+b01,m6);
    273. 	//m7=(a01-a11)*(b10+b11)
    274. 	Mat m7(n/2);
    275. 	vs(n/2,a01-a11,b10+b11,m7);
    276. //	cout<<"finish m1-7"<
    277. 	Mat c00(n/2),c01(n/2),c10(n/2),c11(n/2);
    278. 	c00 =m1+m4-m5+m7;
    279. 	c01 =m3+m5;
    280. 	c10=m2+m4;
    281. 	c11=m1+m3-m2+m6;
    282. 	//合并
    283. 	for(int i=0;i2;++i)
    284. 	{
    285. 		for(int j=0;j2;++j)
    286. 		{
    287. 			c.m[i][j]=c00.m[i][j];
    288. 			c.m[i][j+n/2]=c01.m[i][j];
    289. 			c.m[i+n/2][j]=c10.m[i][j];
    290. 			c.m[i+n/2][j+n/2]=c11.m[i][j];
    291. 		}
    292. 	 } 
    293. }
    294.  
    295. int main()
    296. {
    297. 	ma.input01(aa);
    298. 	mb.input01(bb);
    299. 	
    300. 	vs(n,ma,mb,mc01);
    301. 	mc01.show();
    302. 	
    303. 	bs(n,ma,mb,mc02);
    304. 	mc02.show();
    305. 	
    306. 	
    307. 	return 0;
    308.  } 
    309.  /*
    310.  
    311.  1       0       2       1
    312. 4       1       1       0
    313. 0       1       3       0
    314. 5       0       2       1
    317. 0       1       0       1
    318. 2       1       0       4
    319. 2       0       1       1
    320. 1       3       5       0
    323. 5       4       7       3
    324. 4       5       1       9
    325. 8       1       3       7
    326. 5       8       7       7
    329. 5       4       7       3
    330. 4       5       1       9
    331. 8       1       3       7
    332. 5       8       7       7
    333.  */

     棋盘覆盖问题：

    【例5-4】残缺棋盘

    残缺棋盘是一个有2^ k ×2^ k （k≥1）个方格的棋盘，其中恰
    有一个方格残缺。如图给出k=1时各种可能的残缺棋盘，其
    中残缺的方格用阴影表示。

    这样的棋盘称作“三格板”，残缺棋盘问题就是要用这四
    种三格板覆盖更大的残缺棋盘。在此覆盖中要求：
    1）两个三格板不能重叠
    2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格
    在这种限制条件下，所需要的三格板总数为(2^ k ×2^ k -1 )/3。【（方格数-1）/3】

    问题分析：s=size/2 分治

    分4种情况：
    1. 若坏格子在左上角，则把图5-2中①号放置在二分后的中间
    位置，如图(2)
    2. 若坏格子在右上角，则把图5-2中②号放置在二分后的中间
    位置，如图(3)
    3. 若坏格子在左下角，则把图5-2中③号放置在二分后的中间
    位置，如图 (4)
    4. 若坏格子在右下角，则把图5-2中④号置在二分后的中间位
    置，如图(5)

    如何确定棋盘，如何区分棋盘？

    ——用棋盘左上角进行定位，用棋盘边长划定范围。

    计算模型

    (1)棋盘：用二维数组CBoard[n][n]存储
    (2)棋盘的识别
    • tr 棋盘中左上角方格所在行。
    • tc 棋盘中左上角方格所在列。
    • dr 残缺方块所在行。
    • dc 残缺方块所在列。
    • size 棋盘的行数或列数。
    覆盖残缺棋盘所需要的三格板数目为：( size^ 2 -1 ) / 3
    将这些三格板编号为1到( size^ 2 -1 ) / 3。则将残缺棋
    盘三格板编号的存储在数组 CBoard[n][n] 的对应位置中

    (3)计算过程
    设s=size/2，当s或size<2时，覆盖结束。
    • 当 行坐标dr时，坏格在左上子棋盘
    中，用①(tr+s-1, tc+s)；(tr+s, tc+s-1) ； (tr+s, tc+s)。//红色部分

    • 当dr

    中，用② (tr+s-1, tc+s-1)； (tr+s, tc+s-1) ； (tr+s, tc+s)。
    • 当dr≥tr+s and dc
    中，用③(tr+s-1, tc+s-1)； (tr+s-1, tc+s) ； (tr+s, tc+s)。

    • 当dr≥tr+s and dc≥tc+s时，坏格在右下子棋盘 中，

    用④ (tr+s-1, tc+s-1)； (tr+s-1, tc+s) ； (tr+s, tc+s-1)。

    算法分析

     

     

    算法设计与描述：

    代码： 

    1. #include
    2. using namespace std;
    3.  
    4. int n=8;//需要是2^x 
    5. int amount=1;
    6. //棋盘
    7. int CBoard[100][100];
    8. //坏格子坐标
    9.  
    10. //覆盖之后棋盘
    11. int chessboard[100][100]; 
    12.  
    13. //左上角方格所在行int tr,左上角 列int tc, (tr.tc)
    14. //残缺 行int dr,残缺 列int dc   (dr,dc )
    15. //棋盘的行数or列数int size)
    16. void CBCover(int CBoard[][100],int tr,int tc,int dr,int dc,int size)
    17. {
    18. 	if(size<2)return;
    19. 	int t=amount;
    20. 	amount++;//所使用的三格板的数目
    21. 	//二分 
    22. 	int s=size/2;//子问题的棋盘
    23. 	//残缺方格位于左上棋盘  1号隔板 
    24. 	if(dr
    25. 	{
    26. 		//递归 
    27. 		CBCover(CBoard,tr,tc,dr,dc,s);
    28. 		//到最接近的 结束 
    29. 		 
    30. 		//覆盖这三块方格 1号隔板 
    31. 		CBoard[tr+s-1][tc+s]=t;//注意是相对于隔板的标记坐标 
    32. 		CBoard[tr+s][tc+s-1]=t;//不是相对于残格的坐标 
    33. 		CBoard[tr+s][tc+s]=t; //
    34. 		
    35. 		//覆盖其余部分
    36. 		//下侧棋盘 覆盖的那块隔板 会在新的棋盘上占用一个方格 也就是一个坏块 
    37. 		CBCover(CBoard,tr,tc+s,tr+s-1,tc+s,s);
    38. 		//右侧 
    39. 		CBCover(CBoard,tr+s,tc,tr+s,tc+s-1,s);
    40. 		//右下侧 
    41. 		CBCover(CBoard,tr+s,tc+s,tr+s,tc+s,s);
    42. 		
    43. 	}
    44. 	//残缺方格位于右上棋盘 2号隔板 
    45. 	else if(dr=tc+s )
    46. 	{
    47. 		//递归 
    48. 		CBCover(CBoard,tr,tc+s,dr,dc,s);
    49. 		
    50. 		CBoard[tr+s-1][tc+s-1]=t;//覆盖2号三格板 
    51. 		CBoard[tr+s][tc+s-1]=t;
    52. 		CBoard[tr+s][tc+s]=t;
    53. 		//覆盖其余部分
    54. 		CBCover(CBoard,tr,tc,tr+s-1,tc+s-1,s);
    55. 		CBCover(CBoard,tr+s,tc,tr+s,tc+s-1,s);
    56. 		CBCover(CBoard,tr+s,tc+s,tr+s,tc+s,s);
    57. 		
    58. 	}
    59. 	//残缺方格位于左下棋盘 3号隔板 
    60. 	else if(dr>= tr+s && dc < tc+s )
    61. 	{
    62. 		//递归 
    63. 		CBCover(CBoard,tr+s,tc,dr,dc,s);
    64. 		CBoard[tr+s-1][tc+s-1]=t;//上
    65. 		CBoard[tr+s-1][tc+s]=t;//右上
    66. 		CBoard[tr+s][tc+s]=t;//右 
    67. 		//覆盖其余部分
    68. 		CBCover(CBoard,tr,tc,tr+s-1,tc+s-1,s);
    69. 		CBCover(CBoard,tr,tc+s,tr+s-1,tc+s,s);
    70. 		CBCover(CBoard,tr+s,tc+s,tr+s,tc+s,s);
    71. 		
    72. 	}
    73. 	//残缺方格位于右下棋盘 4号隔板 
    74. 	else if(dr>=tr+s && dc>=tc+s )
    75. 	{
    76. 		//递归 
    77. 		CBCover(CBoard,tr+s,tc+s,dr,dc,s);
    78. 		
    79. 		CBoard[tr+s-1][tc+s-1]=t;//覆盖2号三格板 
    80. 		CBoard[tr+s-1][tc+s]=t;
    81. 		CBoard[tr+s][tc+s-1]=t;
    82. 		//覆盖其余部分
    83. 		CBCover(CBoard,tr,tc,tr+s-1,tc+s-1,s);
    84. 		CBCover(CBoard,tr,tc+s,tr+s-1,tc+s,s);
    85. 		CBCover(CBoard,tr+s,tc,tr+s,tc+s-1,s);
    86. 		
    87. 	}
    88. 	 
    89. }
    90. void output(int a[][100])
    91. {
    92. 	cout<<"a:"<
    93. 	for(int i=0;i
    94. 	{
    95. 		for(int j=0;j
    96. 		{
    97. 			cout<"\t";
    98. 		}
    99. 		cout<
    100. 	}
    101. 	
    102. }
    103. int main()
    104. {
    105. 	output(CBoard);
    106. 	CBCover(CBoard,0,0,0,0,n);
    107. 	output(CBoard);
    108. 	return 0;
    109. }

     选择性问题：——非等分

    选最大值、最小值、选中位数、选第二大值

    一般性描述：

    设A是含有n个元素的集合，从A中选出第k小的元素，其中
    1≤k≤n。这里的第k小是指当A中元素从小到大排序之后，
    第k个位置的元素，当k=1时，选出的是A中的最小值，当
    k=n时，选出的就是最大值。

    问题分析：

    (1)排序--找第k小的元素，时间渐近复杂度为O(nlogn)——高级排序算法 极限
    (2)蛮力算法--当k=1或k=n时【最大或最小】，一趟即可找到解，时间渐近复杂度只有O(n)。
    (3)二分治策略--当k=2时，将原数列分为两个子集，每个子 集各选出一个最小值和第二小值，从这个4个数字里可找到当前的最小值

    选择性问题：选第k小值

    计算模型

    选择pivot=a[left]值，j=right对集合进行二分
    (1) j-left=k-1，则分界数据就是选择问题的答案
    (2) j-left>k-1，则选择问题的答案继续在左子集中找，问题规模变小了。
    (3) j-left

    算法分析

    (1)最坏情况下的复杂性是O(n 2 )，left 总是为空，第k个元素总是位于 right
    子集中。
    (2)设n=2 k ，算法的平均复杂性是O (n+logn)。若仔细地选择分界元素，则
    最坏情况下的时间开销也可以变成O(n)。
    (3)它与本章第一个例子非常相似，只对一半子集进行搜索，所不同的时，
    由于pivot点选择的不同，多数情况下它是非等分的。
    算法设计与分析
    输入
    输出

    int select(int a[],int left,int right,int k)
    {
        int i,j,pivot,t;
        if(left>=right)return a[left];
        i=left;
        j=right+1;
        pivot=a[left];
        while(true)
        {
            do{
                i++;
            }
            while(a[i]         if(i>=j)break;
            t=a[i];
            a[i]=a[j];
            a[j]=t;
            
        }
        if(j-left+1==k) return pivot;
        a[left]=a[j];
        a[j]=pivot;
        if(k<(j-left+1))select(a,left,j-1,k);
        else select(a,j+1,right,k-j-j+left);
    } 

    代码：

    1. #include
    2. using namespace std;
    3.  
    4. void show(int a[])
    5. {
    6. 	cout<<"a[]:";
    7. 	for(int i=0;i<8;i++)
    8. 		cout<"\t";
    9. 	cout<
    10. }
    11.  
    12. int select(int a[],int left,int right,int k)
    13. {
    14. 	cout<"select:left:"<" right:"<" k: "<
    15. 	cout<<"left不变 right不变"<
    16. 	show(a);
    17. 	
    18. 	int i,j,pivot,t;
    19. 	if(left>=right) {
    20. 		cout<<"left>=right a[left]"<
    21. 		return a[left];
    22. 	}
    23. 	i=left;
    24. 	j=right+1;
    25. 	pivot=a[left];
    26. 	cout<<"left:"<" a[left] = pivot: "<
    27. 	while(true)
    28. 	{
    29. 		cout<"in while:"<
    30. 		do{
    31. 			i++;
    32. 		}
    33. 		while(a[i]
    34. 		
    35. 		do{
    36. 			j--;
    37. 		}while(a[j]>pivot);
    38. 		cout<<"now pivot is "<" 从left到i都小于pivot "<":"<" 从j到right都大于pivot "<":"<
    39. 		if(i>=j){
    40. 			cout<<"i>=j break;"<
    41. 			break;
    42. 		}
    43. 		
    44. 		t=a[i];
    45. 		a[i]=a[j];
    46. 		a[j]=t;
    47. 		cout<<"swap "<" "<
    48. 		show(a);
    49. 	}
    50. 	cout<"while结束 此时 j left k 是"<" "<" "<
    51. 	
    52. 	
    53. 	cout<"最开始right-left+1等于总的元素个数,现在j往前移动 也就是比pivot大的数有（right-j）个"<
    54. 	<<"选第k小的元素 应该是有sum1=k-1个数比x小，有sum2=right-left+1-k个数比x大"<
    55. 	<<"此时 sum2=(right-j) 那么k=right-left+1-(right-j) =j-left+1 也就是此时是第(j-left+1)小 "<
    56. 	<<"需要让此时的 (j-left+1)==k 就求出了答案 "<
    57. 	
    58. 	if(j-left+1==k) return pivot;
    59. 	cout<<"然而 (j-left+1)!=k 需要继续寻找 "<
    60. 	cout<<"a[left]是基准元素,j小于等于基准，因此交换 "<
    61. 	cout<<"交换 left j 的元素"<
    62. 	a[left]=a[j];
    63. 	a[j]=pivot;
    64. 	show(a);
    65. 	
    66. 	if(k<(j-left+1))
    67. 	{
    68. 		cout<"左侧";
    69. 		select(a,left,j-1,k);	
    70. 	} 
    71. 	else 
    72. 	{
    73. 		cout<"右侧";
    74. 		select(a,j+1,right,k-j-1+left);
    75. 	}
    76. } 
    77.  
    78. int a[]={1,4,5,3,2,6,8,7};
    79. int k=2;
    80. int main()
    81. {
    82. 	
    83. 	int left=0;
    84. 	int right=7;
    85. 	int res= select(a,left,right,k);
    86. 	cout<
    87. 	return 0;
    88. }

    思考题：正元素 负元素排序

    问题分析：
    使数组中所有负数位于正数之前，空间效率：原数组的空间不可改变，临时变量尽可能少，在原数组上改变 不增加结果数组。时间效率：运算次数尽可能少。

    一定会遍历一遍数组，且每个元素与0进行比较，因此从两侧开始，若左侧小于0 不变，大于0需要后移，右侧大于0不变，小于0需要后移。因此找到两位置left right ，进行交换。再以此为范围进行下一轮递归，直到left>=right 结束递归。

    计算模型：

    从[left,right]范围内进行二分。

    （1）left>=right 结束循环

    （2）从left开始找到第一个大于0的元素下标，更新left

    （3）从right开始找到第一个小于0的元素下标，更新right

    （4）若left>=right 结束循环

    （5）否则从新的【left，right】范围进行递归排序

    算法设计与分析

    算法设计与描述

    		算法分析
    输入：数组a[]
    输出：排序后数组

    void fun(int a[],int left,int right)
    {
        if(left>=right) {
            return ;
        }
        while(a[left]<0) ++left;
        
        while(a[right]>0) --right;

        if(left     {
            t=a[left];
            a[left]=a[right];
            a[right]=t;
            fun(a,left,right);
        }
        else return ;
    }

    （1）输入规模n
    （2）核心语句：比较和交换语句

    （3）

    时间复杂度 按最坏情况 每交换一次 都只能纠正2个元素的位置，则需要递归n/2次 ：

    T(n)= T(n-2) + c

    =T(n-4) + 2*c

    =T(n-6)+3*c

    共n/2次 T(n)=O(n)

    空间复杂度：则S(n)= n/2 +2;

     

    思考题：用分治法 求 数列的最大子段和

  • 相关阅读:
    什么是war包？war包该怎么运行？
    嵌入式学习笔记（16）反汇编工具objdump
    Linux系统管理
    Pandas 2.1中的新改进和新功能
    Bash变量--位置参数变量
    深圳市第十二届职工技术创新运动会暨2022年深圳技能大赛—集成电路应用开发职业技能竞赛
    电阻值的优先值
    java设计模式之命令设计模式的前世今生
    【Pytest实战】Pytest+Allure+Jenkins自动化测试框架搭建
    Linux内核设计与实现 第九章 内核同步与介绍
  • 原文地址：https://blog.csdn.net/iivan_cpp/article/details/123517470