第2章分治策略

第2章分治策略本章主要知识点：2.1分治法的基本思想（DivideandConquer）2.2二分搜索技术2.3大整数的乘法2.4棋盘覆盖2.5归并排序2.6快速排序2.7寻找第k小元素2.8循环赛日程表计划授课时间：4～6课时1第2章分治策略问题：有16枚硬币，其中有一枚是伪造的，并且那枚伪造硬币的重量和真硬币的重量不同(假设比真币轻)。你能不能用最少的比较次数找出这枚伪造的硬币?提供一台可用来比较两组硬币重量的仪器解决问题：1、两两比较2、硬币分成两组，一次比较两组。一次比较后，可以舍弃完全是真币的那一组，只对另一组进行下一步的比较。关键：将大问题分割成若干小问题，小问题与原有问题是完全类似的。分治法（“分而治之”）。分治法在设计查找、排序等算法时很有效，最常用的分治法有二分法、归并法、快速排序等。22.1分治法的基本思想分治法的基本思想大问题分解为子问题，这些子问题互相独立且与原问题相同。分别求解子问题。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。合并解，自底向上逐步求出原来问题的解。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。32.1分治法的基本思想分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质（当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。）利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。42.1分治法的基本思想分治法的基本步骤divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i<=k,i++)

yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。52.1分治法的基本思想分治法的复杂性分析分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有（右上）。通过迭代法求得方程解（右下）。注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。6补充：递归方程求解常用方法：代入法迭代法套用公式法差分方程法母函数法7补充：递归方程求解1、代入法先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。例如：8补充：递归方程求解2、迭代法通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶。另外可画递归树。

9递归树T(n)=T(n/3)+T(2n/3)+n

当我们累计递归树各层的值时，得到每一层的和都等于n，从根到叶的最长路径是先按横向求出每层结点的值之和，并记录在各相应层右端顶格处，然后从根到叶逐层地将顶格处的结果加起来便是我们要求的结果。10补充：递归方程求解3、套用公式法对于形如

T(n)=aT(n/b)+f(n)

的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。11补充：递归方程求解3、套用公式法4、差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程5、母函数法122.2二分搜索技术给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素x。适用分治法求解问题的基本特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。很显然此问题分解出的子问题相互独立，即在a[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。13二分检索原理将二分检索问题问题表示为：I=(n,a1,…,an,x)选取一个下标k，可得到三个子问题：I1=(k-1,a1,…,ak-1,x)I2=(1,ak

,x)I3=(n-k,ak+1,…,an,x)对所求解的问题（或子问题）所选的下标都是中间元素的下标，k=(n+1)/2」2.2二分搜索技术142.2二分搜索技术问题描述已知一个按非降次序排列的元素表a1,a2,…,an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并置于j，否则，置j为0。一般解决方法（从头到尾查找一遍）a1a2a3a4…anx…成功和不成功最坏情况下需要O（n）次比较15二分搜索算法：publicstaticint

binarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;while(left<=right){

intmid=(left+right)/2;//

mid=low+((high-low)/2);

if(x==a[mid])returnmid;if(x>a[mid])left=mid+1;elseright=mid-1;}return-1;//未找到x}思考：二分搜索查找递归算法？2.2二分搜索技术16//初始left=0;right=N-1;publicstaticint

binarySearch(inta[],intx,intleft,intright){//找到x时返回其在数组中的位置，否则返回-1if(left>right)return-1;//未找到xelse{intmid=(left+right)/2;if(x==a[mid])returnmid;if(x>a[mid])returnbinarySearch(a,x,mid+1,right);elsereturnbinarySearch(a,x,left,mid);}}思考：二分搜索查找递归算法2.2二分搜索技术17二分检索实例:设在A(0:8)中顺序放了以下9个元素：检索x=9,9==A[4],一次比较就成功,最好情况-15-6079235482101A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]①②③③④②③④检索x=-15,-15<A[4],-15<A[1],-15==A[0],3次比较,成功检索x=101,101>A[4],101>A[6],101>A[7],101==A[8],4次比较,成功检索x=8,8<A[4],8>A[1],8>A[2],8>A[3],4次比较,不成功检索2.2二分搜索技术18二分检索算法所需的空间和时间所需空间:

用n个位置存放数组A，还有low,high,mid,x,j五个变量需要存储，共需空间n+5所需计算空间:

对于计算时间，需要分别考虑以下几种情况：成功检索的最好情况、平均情况、最坏情况不成功检索的最好情况、平均情况、最坏情况2.2二分搜索技术19二分检索的时间复杂度定理:若n在区域[2k-1,2k)中，则对于一次成功的检索，二分检索算法至多作k次比较。对前面二分检索实例n=9,n∈[23,24),已分析过成功检索和不成功检索的各种情况下的比较次数≤4,易知:Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(logn)Θ(1)不成功的检索成功的检索最坏情况平均情况最好情况计算时间202.3大整数的乘法设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)

效率太低分治法:X=A10n/2+BY=C10n/2+DXY=AC10n+(AD+BC)10n/2+BD复杂度分析

T(n)=O(n2)

没有改进

n/2位n/2位n/2位n/2位X=Y=ABCD21算法改进为了降低时间复杂度，必须减少乘法的次数。为此，我们把XY写成另外的形式：XY=AC10n+((A-C)(B-D)+AC+BD)10n/2+BD或XY=AC10n+((A+C)(B+D)-AC-BD)10n/2+BD复杂性：这两个算式看起来更复杂一些，但它们仅需要3次n/2位乘法[AC、BD和(A±C)(B±D)]，于是

T(n)=O(nlog3)=O(n1.59)

较大的改进

细节问题：两个XY的复杂度都是O(nlog3)，但考虑到A+C

,B+D可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。22算法改进voidmain(){longx,y,a,b,c,d;doublez;

cout<<"Pleaseinputthetwonumberxandy:\n";

cin>>x>>y;a=x/(long)pow(10,num_len(x)/2);b=x%(long)pow(10,num_len(x)/2);c=y/(long)pow(10,num_len(y)/2);d=y%(long)pow(10,num_len(y)/2);//z=(double)(a*c*pow(10,num_len(x))+(a*d+b*c)*pow(10,num_len(x)/2)+b*d);z=(double)(a*c*(long)pow(10,num_len(x))+((a-c)*(b-d)+a*c+b*d)*(long)pow(10,num_len(x)/2)+b*d);

cout<<"theresultis"<<z;}23算法改进（续上页）int

num_len(longz){intt=0;

while(z>0){z=z/10;t++;}returnt;}24更快的方法小学的方法：O(n2)——效率太低分治法:O(n1.59)——较大的改进更快的方法？如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。252.4棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，覆盖任意一个2k×2k的特殊棋盘，用到的骨牌数恰好为(2k×2k

-1)/3。262.4棋盘覆盖分治策略算法描述当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1

子棋盘如图(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。将3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。272.5归并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。Step1：把待排序的n个记录看作长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；Step2

：把得到的n/2个长度为2的有序子序列再归并为长度为2*2的有序序列；Step3

：按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。282.5归并排序算法mergeSort初始序列[49][38][65][97][76][13][27]第一步[3849][6597][1376][27]第二步[38496597][132776]第三步[13273849657697]动画演示：http:///fine/resources/FlashContent.asp?id=93292.5归并排序递归算法描述：voidmerge_sort(intdata[],intleft,intright){if(left<right){intmid=(left+right)/2;

merge_sort(data,left,mid);

merge_sort(data,mid+1,right);

merge(data,left,mid,right);}}初始序列[8][4][5][6][2][1][7][3]

归并到b[48][56][12][37]

复制到a[48][56][12][37]

归并到b[4568][1237]

复制到a[4568][1237]

归并到b[12345678]

复制到a[12345678]

30voidmerge(intarray[],intp,intq,intr){ int

i,k; intbegin1,end1,begin2,end2;

int*temp=newint[r-p+1];

//申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列//设定两个指针，最初位置分别为两个已经排序序列的起止位置begin1=p;end1=q;

begin2=q+1;end2=r;k=0; while((begin1<=end1)&&(begin2<=end2))

{if(array[begin1]<array[begin2]) {temp[k]=array[begin1];begin1++; } else {temp[k]=array[begin2];begin2++; } k++; } 31//接上页//若第一个序列有剩余，拷贝出来粘到合并序列尾while(begin1<=end1)

temp[k++]=array[begin1++];//若第二个序列有剩余，拷贝出来粘到合并序列尾while(begin2<=end2)

temp[k++]=array[begin2++];

for(i=0;i<(r-p+1);i++)//将排序好的序列拷贝回数组中

array[p+i]=temp[i];

delete[](temp);}322.5归并排序复杂度分析T(n)=O(nlogn)

渐进意义下的最优算法332.5归并排序T(n)=2*T(n/2)

+

O(n)

=2*（2*T(n/4)

+

2*O(n/2)

+

O(n)

=4*T(n/4)

+

2*O(n)

=8*T(n/8)

+

3*O(n)

...

=2^k

*

T(n/

2^k)

+

k*O(n)

令

(n=2^k,

k=log(n)

(注：log(n)是以２为底）

则原式T(n)等于

=n*T(1)+log(n)*O(n)

=n*O(1)+O(n*log(n))

=O(n)+

O(n*log(n))

=O(n*log(n))342.6快速排序快速排序是对气泡排序的一种改进方法，它是由C.A.R.Hoare于1962年提出的。基本思想通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。动画演示：http:///fine/resources/FlashContent.asp?id=86352.6快速排序算法过程：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：

1）设置两个变量I、J，排序开始时：I=1，J=N-1；

2）以第一个数组元素作为关键数据，X=A[0]；3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个<=X的值；

4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个>=X的值5）交换A[I],A[J]

6）重复第3-5步，直到I=J；362.6快速排序例如：待排序的数组A的值见表，初始关键数据：X=49

3738392.6快速排序部分排序结果：402.6快速排序算法步骤：（1）分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。（2）递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。（3）合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。412.6快速排序voidquicksort(intnumber[],intleft,intright){inti,j,s;

if(left<right) {s=number[(left+right)/2];i=left-1;j=right+1;while(1) {while(number[++i]<s);//向右找第一个大于轴的数

while(number[--j]>s);//向左找第一个小于轴的数

if(i>=j)break;

SWAP(number[i],number[j]);}

quicksort(number,left,i-1);//对左边进行递归

quicksort(number,j+1,right);//对右边进行递归

}}422.6快速排序对于n个成员，快速排序法的比较次数大约为n*logn

次，交换次数大约为(n*logn)/6次。如果n为100，冒泡法需要进行4950次比较，而快速排序法仅需要200次。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2)，而平均时间复杂度为O(n*logn)

43寻找支点元素sel_有多种实现方法，不同的实现方法会导致快速排序的不同性能。根据分治法平衡子问题的思想，我们希望支点元素可以使a[left..right]尽量平均地分为两部分。几种寻找pivot的方法(见补充快速排序文件)：a[left....right]选择的第一个元素a[left]的值作为p(代码3)；选择最后一个元素a[right]的值作为p(代码1)

；选择中间位置的元素a[mid]的值作为p(代码2)

；选择a[left..right]的某一个随机位置上的值作为p；分解/划分算法描述44（略）2.7寻找第k小元素元素选择问题：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。Randomized_Select算法：模仿快速排序算法，首先对输入数组进行划分，然后对划分出的子数组之一进行递归处理。45（略）2.7寻找第k小元素int

RANDOMIZED_SELECT(int

arr[LEN],int

p,int

r,inti)//找到arr中第i小的数，数组下标从1开始{if(p==r)returnarr[p];

intq=RANDOMIZED_PARTITION(arr,p,r);

intk=q-p+1;

if(i==k)returnarr[q];else

if(i<k)returnRANDOMIZED_SELECT(arr,p,q-1,i);elsereturnRANDOMIZED_SELECT(arr,q+1,r,i-k);}46（略）2.7寻找第k小元素算法复杂性：在最坏情况下，算法randomized_Select需要O(n2)计算时间。可以证明，算法Randomized_Select可以在O(n)平均时间内找出n个输入元素中的第k小元素。472.8循环赛日程表分治法不仅可以用来设计算法，而且再其他方面也有广泛应用：利用分治法设计电路、构造数学证明等。循环赛日程标问题，设有n=2k个选手要进行循环赛，设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1个选手各赛一次；每个选手一天只能赛一次；循环赛一共进行n-1天。按此要求，可以将比赛日程表设计成n行n-1列的表格，i行j列表示第i个选手在第j天所遇到的选手。基本思路：按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。482.8循环赛日程表以k=3(即N=23=8)为例，可以根据问题要求，制定出如下图所示的一种方案：以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。492.8循环赛日程表这样，对8个队的赛事排列就逐步减化为对4个队的排列，然后又进一步减化为对2个队的排列，最后就成为1个队的排列。因此，这一问题可以采用分治法的思想来解决。在设计程序时，采用由小到大的方法进行扩展，而数组下标的处理是解决该问题的关键。思考：若n为奇数，例如5，应该如何排？50补充知识一：堆排序一、堆（heap）的概念特殊的二叉树结构，是一个从上到下有大小关系的二叉树。（如父节点>=子节点或者父节点<=子节点）其中，父节点值大于或等于其孩子节点值的，叫“最大堆（maximumheap)”;父节点值小于或等于孩子节点值的，叫“最小堆（minimumheap)”.在最大堆中，根中的元素值最大；在最小堆中，根中的元素值最小。51补充知识一：堆排序在起始索引为0的“堆”中：

1)堆的根节点将存放在位置0

2)节点i的左子节点在位置2*i+1

3)节点i的右子节点在位置2*i+2

4)节点i的父节点在位置floor((i-1)/2)

:注floor表示“取整”操作在起始索引为1的“堆”中：

1)堆的根节点将存放在位置1

2)节点i的左子节点在位置2*i

3)节点i的右子节点在位置2*i+1

4)节点i的父节点在位置floor(i/2)

:注floor表示“取整”操作52补充知识一：堆排序二、堆的存储按某种次序将一系列数据以完全二叉树形式存放的一种表。它要求堆中的节点的值都大于或等于其孩子节点的值。

length[A]：数组元素个数。heap_size[A]：存放在数组A中的堆的元素个数。例如：{12,39,20,65,47,34,98,81,73,56}为“小顶堆”；{98,81,34,73,56,12,20,39,65,47}为"大顶堆"。parent(i):left（i）：2iright(i):2i+153补充知识一：堆排序三、堆化

数组具有对应的树表示形式。一般情况下，树并不满足堆的条件。通过重新排列元素，可以建立一棵“堆化”的树。

heapify(A,i)//设i下面的元素都已堆化l←left(i)r←right(i)ifl<=heap_size[A]andA[l]>A[i]thenlargest←lelselargest←iifr<=heap_size[A]andA[r]>A[largest]thenlargest←riflargest<>ithenexchange(A[i],A[largest])

heapify(A,largest)54补充知识一：堆排序55补充知识一：堆排序Build-heap(A)//建堆，起始索引1heap-size[A]←length[A]fori←floor(length[A]/2)downto1doheapify(A,i)四、建堆的过程是一个"从下到上"调整堆的过程例如：A(4,1,3,2,16,9,10,14,8,7)，学生演示其建最大堆过程56补充知识一：堆排序堆排序方法基本思想：将原始记录序列建成一个堆，称之为初始堆，并输出堆顶元素；调整剩余的记录序列，使之成为一个新堆，再输出堆顶元素；依此类推，当堆中只有一个元素时，整个序列的排序结束，输出的序列便是

原始序列的排序序列。HeapSort(A，intn){∥对记录序列A[1..n]进行堆排序。

Build-heap(A);

for(i=n;i>1;i--){A[1]←→A[i];∥将堆顶记录和当前未经排序子序列A[1..i]中最后一个记录相互交换heap-size[A]←heap-size[A]-1

heapify(A);}}例如：A={5,13,2,25,7,17,20,8,4}堆排序后,A={2,4,5,7,8,13,17,20,25}57补充知识一：堆排序五、堆的应用-优先级队列（priorityqueue）概念：用来维护由一组元素构成的集合S的数据结构，每一个元素都有一个关键字key。数据项按关键字的值有序，关键字最小的数据项（或者在某些实现中是关键字最大的数据项）总是在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。

讨论基于最大堆的最大优先级队列应用：分时计算机作业调度58补充知识一：堆排序操作：max(S):返回S中具有最大关键字的元素insert(S,x):将x插入Sextract-max(S):去掉最大，从余下的选出最优

HEAP-max(A)1.returnA[1]O(1)59补充知识一：堆排序HEAP-extract-max(A)ifheap-size[A]<1thenerror“heapunderflow”max←A[1]A[1]←A[heap-size[A]]//最后一个元素放在第一heap-size[A]←heap-size[A]-1heapify(A,1);

returnmaxO(1)O(1)O(1)O(1)O(nlog(n-1))O(1)总计O(nlogn)60补充知识一：堆排序HEAP-insert(A,key)//将key插入最大堆A中heap-size[A]←heap-size[A]+1i←heap-size[A]whilei>1andA[parent(i)]<keydoa[i]←A[parent(i)]i←parent(i)A[i]←keyO(1)O(1)O(logn)O(1)*O(logn)O(1)*O(logn)O(1)总计O(logn)61补充知识二：线性时间排序1、计数排序-CountSort集合A有n个元素，每一个元素的值是介于0到k之间的整数。输入：A[1..n]存放排序结果：B[1..n]临时存储：C[0..k]计数排序的基本思想是对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以把x直接放到它在最终输出数组的位置上。例如：若有5个元素小于x，则x就属于第6个输出位置。62补充知识二：线性时间排序1、计数排序-CountSort例如：A={3,6,4,1,3,4,1,4},数值从1-->6C2023011的个数2的个数3的个数4的个数5的个数6的个数整理C2<=12<=24778<=6将A从右往左读，第一个数为4，查C表为7，生成排序后B数组B11334446练习：A={1,3,2,4,7,5,2,1,3,6},求排序后数组B63补充知识二：线性时间排序Count-Sort(A,B,k)//0<=a[i]<=kfori←0tokdoC[i]←0