大佬教程收集整理的这篇文章主要介绍了2022/2/7(8)递归和分治思想自学，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
听课部分：(0:30-3:30)
一、递归
定义：一个函数在执行时再次调用函数“本身”（逻辑相同，但使用了不同的空间去执行）
例1：NC15173 The Biggest Water Problem
1 void mymerge(int l, int mid, int@H_55_197@ r) 2 @H_55_197@{ 3 int p = l, q = mid + 1@H_55_197@; 4 for (int i = l; i <= r; ++@H_55_197@i) 5 @H_55_197@ { 6 if ((q > r) || (p < mid && arr[p] <=@H_55_197@ arr[q])) 7 b[i] = arr[p++@H_55_197@]; 8 else 9 b[i] = arr[q++@H_55_197@]; 10 @H_55_197@ } 11 for (int i = l; i <= r; ++@H_55_197@i) 12 arr[i] =@H_55_197@ b[i]; 13 @H_55_197@} 14 void merge_sort(int l, int@H_55_197@ r) 15 @H_55_197@{ 16 if (l ==@H_55_197@ r) 17 return@H_55_197@; 18 int mid = (l + r) / 2@H_55_197@; 19 @H_55_197@ merge_sort(l, mid); 20 merge_sort(mid + 1@H_55_197@, r); 21 @H_55_197@ mymerge(l, mid, r); 22 }
变形1：求逆序对的个数
给你一个序列，求出这个序列的逆序对个数
逆序对：对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且
A[i] > A[j]，则称(A[i],A[j])为数组A中的一个逆序对
思路1：暴力双循环（n^2）
思路2：记录冒泡排序的交换次数（n^2）
思路3：记录相对顺序调整时，会产生多少逆序对（nlogn）（使用下标进行计算）
将cnt+=min-p+1的计算加入上面代码的else中即可。
本题揭示了要会手写排序而不能只会sort的意义
1 void quick_sort(int l, int@H_55_197@ r) 2 @H_55_197@{ 3 int i = l, j =@H_55_197@ r; 4 int mid = (l + r) / 2@H_55_197@; 5 int x =@H_55_197@ arr[mid]; 6 while (i <=@H_55_197@ j) 7 @H_55_197@ { 8 while (arr[i] <@H_55_197@ X) 9 ++@H_55_197@i; 10 while (arr[j] >@H_55_197@ X) 11 --@H_55_197@j; 12 if (i <=@H_55_197@ j) 13 @H_55_197@ { 14 @H_55_197@ swap(arr[i], arr[j]); 15 ++@H_55_197@i; 16 --@H_55_197@j; 17 @H_55_197@ } 18 @H_55_197@ } 19 if (l <@H_55_197@ j) 20 @H_55_197@ quick_sort(l, j); 21 if (i <@H_55_197@ r) 22 @H_55_197@ quick_sort(i, r); 23 }
变形2：NC 207028 求一个序列的第k小数
思路：每次分配完成时，都丢掉一半的序列
以上是大佬教程为你收集整理的2022/2/7(8)递归和分治思想自学全部内容，希望文章能够帮你解决2022/2/7(8)递归和分治思想自学所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。