数算-经典算法代码

voidqsort(intx,inty)待排序的数据存放在a[1]..a[n]{intintm=a[(x+y)>>1取中间的那个位置的值{while(a[h]<m)h++;//比中间那个位置的值小，循环直到找一个比中间那个值大的whilea[r]>m)r比中间那个位置的值大，循环直到找一个比中间那个值小的{inttemp=a[h];//如果此时h<=ra[h]a[r]h++;r}}if(r>x)qsort(x,r);//注意此处，尾指针跑到前半部分了if(h<y)qsort(h,y);注意此处，头指针跑到后半部分了})//{for(inti=1;i<n;i++)//控制循环（冒泡）的次数，n个数，需要n-1for(intj=1;j<=n-i;jif(a[j]<a[j+1]){int})//{for(inti=1;i<n;i++)//控制循环（冒泡）的次数，n个数，需要n-1for(intj=n-i;j>=1;jif(a[j]<a[j+1]){int}for(inti=1;i<=n;i++)//读入n个数{intatong[a]++;}//1for(inti=1;i<=cmax;i++){if(tong[i]>0)0itong[i]iwhile(tong[i]!=0)cout<<i<<’}}四、合（归）voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]intb[101];//B，使两个有序的子区间合并成一个有序的区间，b数组inth=l;t=m+1;//让h指向第一个区间的第一个元素，twhile((h<=m)&&(t<=r))//在指针h和t没有到区间尾时，把两个区间的元素抄在新数组 if(a[h]<a[t]){b[k]=a[h];h++;} else{b[k]=a[t];t++;}//抄第二个区间元素到新数组}while(h<=m){k++;b[k]=a[h];h++;}//如果第一个区间没有抄结束，把剩下的抄在新数while(t<=r){k++;b[k]=a[t];t++;}//如果第二个区间没有抄结束，把剩下的抄在新数组for(into=1;o<=k;o++)//把新数组中的元素，再抄回原来的区间，这两个连续的区间变a[l+o-}voidmergesort(intx,inty)//对区间[x,y]{intmid;if(x>=y)return;}intfind(intx,inty,intm在[x,y]m{inthead,tail,mid;if(a[mid]==m)returnmid;//如果中间元素值为mif(m>a[mid])//mreturnreturnfind(head,mid-}usingnamespacestd;intmain(){stringinta[250],b[250],len; inti; a[0]=str1.length();//for(i=1;i<=a[0];i++)//a for(i=1;i<=b[0];i++)//把第二个字符串中的每一位转换为整数，存放在数组B for(i=1;i<=len;i++)//做按位加法，同时处理进位{} //下面是去掉最的0，然后输出。while((a[len]==0)&&(len>1))len--;return0;}usingnamespacestd;intcompare(strings1,strings2);intmain(){stringinta[250],b[250],len;inti;if((compare(str1,str2))==0)//{if(a[i]<0){a[i+1]--while((a[a[0]]==0)&&(a[0]>1))a[0]--;}{cout<<'-';//小于就输出负号for(i=1;i<=b[0];i++)//做按位减，大的减小的if(b[i]<0){b[i+1]--while((b[b[0]]==0)&&(b[0]>1))b[0]--;}return}intcompare(strings1,strings2)//比较字符串（两个数）0，1。{if(s1.length()>s2.lengthreturn0;//for(inti=0;i<=s1.length();i++)//{if(s1[i]>s2[i])returnif(s1[i]<s2[i])return}return0;//0}usingnamespacestd;intmain(){stringint inti,j;for(i=1;i<=a[0];i++)//做按位乘法同时处理进位，注意循环内语句的写法。{}len=a[0]+b[0]+1;//去掉最的0，然后输出while((c[len]==0)&&(len>1len--;//len>1??return0;}usingnamespacestd;voidnum1(ints[],stringInt{stringstr1,str2;intlen;num1(a,str1把str14afor(inti=1;i<=a[0];i+作按位乘法并处理进位，此处是万进制进位for(intj=1;j<=b[0];j++){}while((c[len]==0)&&(len>1))len--;//去掉的0，并输出最{if(c[i]<1000)if(c[i]<100)if(c[i]<10)}return0;}中 int--)//{if(count%4==0){s[k]+=(st1[i]-‘0’)*1000;if(i!=0)if(count%4==1)s[k]=(st1[i]-if(count%4==2)s[k]+=(st1[i]-if(count%4==3)s[k]+=(st1[i]-‘0’)*100;}//}九、高精度除法（没讲voidmaketable(intx)//Xprim，prim[i]0i1表示{prim[0]=1;prim[1]=1;prim[2]=0;//X以内的质数表for(inti=2;i<=x;i++)if{intj=2*i;}}voiddfs(intx)\\{cout<<x<<‘‘;\\x顶visited[x]=1;\\作已的标}voidbfs(voidG，n1..n。注：图不一定是连{//使用辅助队列Q和标记数组visitedfor(v=1;v<=n;v++)visited[v]=0；//标记数组初始化for(v=1;v<=n;v++)if(visited[v]==0 inth=1,r=1; //qvisited[v]=1；//顶点v,作标记cout<<v<<‘‘;//顶点vq[r]=v；//v入队列while(h<=r)//当队列非空时循环{inttmp=q[h];//tmpfor(intj=1;j<=n;j++)visited[j]=1;对j作标cout<<j<<‘‘;jrq[r]=jj}//end-}//end-}voidpreorder(intx)//{if(x==0)}voidinorder(intx)//{if(x==0)}voidreorder(intx)//{if(x==0)}十六、voidhaff(void)//构建{for(inti=n+1;i<=2*n-1;i+依次生成n-1{intl=fmin(i-1);la[i].lchild=l;//li的左孩子a[l].father=i;//liintr=fmin(i-1ra[i].rchild=r把li的右孩子a[r].father=i;//把ri//}}intfmin(intk)//1K{intfor(intif((a[mins].da>a[s].da)&&(a[s].father==0))a[s].father=0,说明这个结点还不是 return}voidinorder(intx)//递归生成编{){if(a[a[x].father].lchild==x)if(a[a[x].father].rchild==x)a[x].code=a[a[x].father].code+'1';if(a[x].lchild!=0)inorder(a[x].lchild);//递归生成左子树if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}intgetfather(intx)//Xreturn}intgetfather(intx)//递归求X{if(x==father[x])returnelsereturn}{intwhile(x!=father[x])//从X结点沿Xfather[x]=p;//XP}return}intgetfather(intx)//递归求X{if(x==father[x])returnx;else{inttemp=getfather(father[x]);return}}voidmerge(intx,inty)//合并x,y{intx1=getfather(x);//取得Xif(x1!=x2)father[x1]=x2X，Y两个结})//(}forinti=1;i<=n-1;i++)//n-1{intfor(intj=i+1;j<=n-1;j++)//ii+1至n-1{edge}for(inti=1;i<=n-1;i++)//求最小生成树的值}i+1n-1条边到已经生成的树中最小距离时(上面代码中加粗的部分)elist[j].from=elist[i].to;语句，即在更新权值Primevoiddijkstra(intx)//x{memset(vis,0,sizeof(vis初始化，vis[i]＝0表示源点到结点i//for(inti=1;i<=n;i++) {}for(inti=1;i<=n-1;i++)//对于nxn-1{intm=big;//虚拟一个最大的数big= intk=x;for(intj=1;j<=n;j++)//在未求出的结点中找一个源点到其距离最小的点{}vis[k]=1;//k=Xfor(intj=1;j<=n;j++)//X{dis[j]=dis[k]+g[k][j];//pre[j]=k;//}}}说明：dis[i]xi的最短距离，pre[i]i结点的前趋结点。二十、Kruscal算法voidqsort(intx,inty)//{inth=x,r=y,m=elist[(h+r)>>1].w;{while(elist[h].w<m)h++;while(elist[r].w>m)r--;}if(x<r)if(h<y)}{if(x==father[x])returnx;else{intf=getfather(father[x]);return}}voidmerge(intx,inty)//合并x,y结点，在此题中的x,yvoid{intfor(int{intx1=getfather(elist[i].from);//i条边的起点所在的树的根intx2=getfather(elist[i].to);//i条边的终点所在的树的根{sum++;merge(x1,x2);ans+=elist[i].w;}//不在同一个集合，合并，即第i}cout<<"Impossible"<<endl;t条边中无法确定n-1}Krsl算法。对于岛国问题，我们就要选择此算法，如果用Prm个点的数据，显然在空间上是无法的。voidfloyed(voida[i][j]ij的最短路径长度，初始时值为<I,J>{for(intk=1;k<=n;k+Kf[i][j]最短路径长度，KDPfor(inti=1;i<=n;i+i，jiJDPfor(intif(a[i][j]>a[i][k]+a[k][ja[i][j]=a[i][k]+a[k][j];//这是决策，加和不加中间点，取最}FLOYED算法，可写出iJ是否连通的算法。二十二、01f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]}。f[i][j]i个物品，在背包载jf[n][v]f[0][s]=0,s=0,1,…,v。{}{))}了阶段这一维，同时在枚举状态时，为了保证结果的正确性，枚举的顺序只能是v0，而不能是0到v。大家细想一下为什么？就是保证在求第i阶段j状态时，f[j-w[i]]为第i-1j>=w