脚本宝典收集整理的这篇文章主要介绍了2022/2/7(8)递归和分治思想自学,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
听课部分:(0:30-3:30)
一、递归
定义:一个函数在执行时再次调用函数“本身”(逻辑相同,但使用了不同的空间去执行)
例1:NC15173 The Biggest Water PRoblem
1 void mymerge(int l, int mid, int r) 2 { 3 int p = l, q = mid + 1; 4 for (int i = l; i <= r; ++i) 5 { 6 if ((q > r) || (p < mid && arr[p] <= arr[q])) 7 b[i] = arr[p++]; 8 else 9 b[i] = arr[q++]; 10 } 11 for (int i = l; i <= r; ++i) 12 arr[i] = b[i]; 13 } 14 void merge_sort(int l, int r) 15 { 16 if (l == r) 17 return; 18 int mid = (l + r) / 2; 19 merge_sort(l, mid); 20 merge_sort(mid + 1, r); 21 mymerge(l, mid, r); 22 }
给你一个序列,求出这个序列的逆序对个数
逆序对:对于一个包含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 r) 2 { 3 int i = l, j = r; 4 int mid = (l + r) / 2; 5 int x = arr[mid]; 6 while (i <= j) 7 { 8 while (arr[i] < x) 9 ++i; 10 while (arr[j] > x) 11 --j; 12 if (i <= j) 13 { 14 swap(arr[i], arr[j]); 15 ++i; 16 --j; 17 } 18 } 19 if (l < j) 20 quick_sort(l, j); 21 if (i < r) 22 quick_sort(i, r); 23 }
变形2:NC 207028 求一个序列的第k小数
思路:每次分配完成时,都丢掉一半的序列
以上是脚本宝典为你收集整理的2022/2/7(8)递归和分治思想自学全部内容,希望文章能够帮你解决2022/2/7(8)递归和分治思想自学所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。