ACM程序設(shè)計大賽常用算法模板

ACM算法模板總結(jié)班級:計算機091學(xué)號:10921018姓名:鮑杭文件狀態(tài)：[√]草稿[]正式發(fā)布[]正在修改文件標(biāo)識：ACM算法模板總結(jié)當(dāng)前版本：1.0作者：鮑杭編完成日期：2023-4-3目錄數(shù)論 1高精度算法[1] 1高精度加法 2高精度減法 2高精度乘法 4整型常量階乘 6整型常量階乘和 6高精度的乘方 7高精度除法 7帶符號的數(shù)據(jù)運算 9廣度優(yōu)先搜索大數(shù)應(yīng)用 11基于比擬的排序算法 12插入排序 12選擇排序 13冒泡排序 13堆排序 13歸并排序 14快速排序 15希爾排序 16同余運算 16模線性方程問題 16計算a^nmodk 19階乘最后非0位 20素數(shù)篇 20線性篩法 21費馬小定理 22MR素性測試 22歐拉函數(shù)問題 22巴赫猜測 23最大公約數(shù) 24最小公倍數(shù) 25不定方程求解 25概率因子分解Pollard算法 25數(shù)值計算[2] 26定積分計算(Romberg) 26多項式求根(牛頓法) 27周期性方程(追趕法) 29組合論[3] 30組合公式 30全組合排列 30非重復(fù)組合排列 32類循環(huán)組合排列 34普通選擇性組合排列 35生成全子集組合排列 36非重復(fù)生成全子集組合排列 37一般組合 39排列組合生成 39生成gray碼 41置換(polya) 42字典序全排列 42字典序組合 43計算幾何 43對于任意多邊形求面積 43判斷兩線是否相交 44二分查找模板 44二分圖匹配模板 45動態(tài)規(guī)劃 46求局部最大和模板 46字符串 46字符計數(shù)應(yīng)用 46最大子序列算法 47求最長公供子串〔DP算法〕 48數(shù)據(jù)結(jié)構(gòu) 49圖論 49入度和出度表的轉(zhuǎn)化 49生成樹 52最小生成樹 56關(guān)鍵路徑 59迷宮算法的隊列實現(xiàn) 64最短路徑 67棧的相關(guān)操作 75一元多項式計算 78單鏈表的簡單操作 84快速排序 89哈夫曼編碼 90隊列的簡單操作 94KMP模式匹配算法 98常用的數(shù)學(xué)公式[4] 100中國剩余定理 100根本幾何公式 100歐拉公式 101劃分問題： 102Stirling公式 102皮克定理 103卡特蘭數(shù) 103原理: 103錯排公式 103等比數(shù)列 104等差數(shù)列 104二次函數(shù) 104二次方程 105約瑟夫環(huán) 105多邊形面積 105均值不等式的簡介 105均值不等式的變形 106Lucas定理 107斐波那契數(shù)列 107歐拉函數(shù) 108螞蟻爬繩 109(a/b)%m 109泰勒公式 109乘法與因式分解公式 109三角不等式 110某些數(shù)列的前n項和 110二項式展開公式 110三角函數(shù)公式 110常用系統(tǒng)函數(shù) 112將字符串轉(zhuǎn)化為數(shù)字 112系統(tǒng)函數(shù)排序 112數(shù)論高精度算法[1]#include<stdio.h>#include<string.h>charc[2000];//全局變量，存儲大數(shù)運算的結(jié)果chararr[1000];//高精度除以高精度的余數(shù)longz=0;//高精度除以低精度的余數(shù)intJudge(charch[]){//判斷字符串ch是否全為0，假設(shè)全為0，返回0，否那么返回1inti,k; k=strlen(ch); for(i=0;i<k;i++) if(ch[i]!='0') return0; return1;}intCompare(chara[],charb[]){//比擬字符串的大小，方法不同于strcmp函數(shù)，類似于整型常量的比擬 intlena,lenb,i; lena=strlen(a); lenb=strlen(b); if(lena<lenb) return-1; elseif(lena>lenb) return1; else { if(strcmp(a,b)==0) return0; else { for(i=0;i<lena;i++) { if(a[i]>b[i]) return1; if(a[i]<b[i]) return-1; } return0; } }}高精度加法/*算法：先確定a和b中的最大位數(shù)k，然后依照由低至高位的順序進行加法運算。注意進位，假設(shè)高位有進位，那么c的長度為k+1。*/voidBigNumberAdd(chara1[],charb1[]){ inti,j,k,lena,lenb; inta[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); //將加數(shù)與被加數(shù)化為整型數(shù)組，并且該數(shù)組的其他位為 for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; //當(dāng)數(shù)組除了加數(shù)和被加數(shù)以外的整型數(shù)組元素均為0時，無需考慮lena和lenb的大小 k=lena>lenb?lena:lenb; for(i=0;i<k;i++) { d[i]=a[i]+b[i]+d[i]; d[i+1]=d[i+1]+d[i]/10; d[i]=d[i]%10; } //假設(shè)高位進 while(d[k]) k++; while(!d[k-1]) k--;//001+0003=4 //將整型數(shù)組逆著轉(zhuǎn)變并賦值給c字符型數(shù)組 for(j=0;j<k;j++) c[j]=d[k-j-1]+'0'; if(Judge(c))//假設(shè)全為0，那么只輸出一個 strcpy(c,"0");}高精度減法/*算法：依照由低位至高位的順序進行減法運算。在每次位運算中，假設(shè)出現(xiàn)不夠減的情況，那么向高位借位。在進行了la的減法后，假設(shè)最高位為0，那么a的長度減。假設(shè)A、B大小未知，那么需先判斷大小。*/voidBigNumberSub(chara1[],charb1[]){//a1為被減數(shù)，b1為減數(shù) intlena,lenb,i,j,k,flag; inta[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); if(Compare(a1,b1)>=0) {//假設(shè)被減數(shù)大于等于減數(shù) for(i=0;i<lena;i++) a[i]=a1[lena-1-i]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; flag=0;//結(jié)果正的標(biāo)志 } else {//假設(shè)被減數(shù)小于減數(shù) for(i=0;i<lenb;i++) a[i]=b1[lenb-1-i]-'0'; for(i=0;i<lena;i++) b[i]=a1[lena-1-i]-'0'; flag=1;//結(jié)果負(fù)的標(biāo)志 } k=lena>lenb?lena:lenb; for(i=0;i<k;i++) {//大數(shù)減小數(shù) if(a[i]<b[i]) {//假設(shè)被減數(shù)不夠減，向高位借一位 a[i+1]--; d[i]=a[i]-b[i]+10; } else d[i]=a[i]-b[i]; } //假設(shè)較高位已為0，并且不止1位時 while(!d[i-1]) { k--; i--; } //根據(jù)flag，輸出有無"-" if(!flag) { for(i=0;i<k;i++) {//將結(jié)果轉(zhuǎn)化為字符逆著賦給數(shù)組c if(!i&&!d[k-i-1])//假設(shè)差的第一個字母為0，那么馬上跳過 continue; c[i]=d[k-i-1]+'0'; } } else { c[0]='-'; for(i=1;i<=k;i++) {//將結(jié)果轉(zhuǎn)化為字符逆著賦給數(shù)組c if(i==1&&!d[k-i])//假設(shè)差的第一個字母為0，那么馬上跳過 continue; c[i]=d[k-i]+'0';//注意d的下標(biāo)，不是k-i-1 } } if(Judge(c))//假設(shè)差全為0，那么只輸出一個 strcpy(c,"0");}高精度乘法高精度乘以低精度/*算法：將多位數(shù)存入數(shù)組，低位在前、高位在后，然后用一位數(shù)去乘數(shù)組的各位，考慮進位，最后按正常順序輸出*/voidBigNumMultiSmall(chara1[],intb1){ inti,j,t; inta[2000]={0}; //將字符串轉(zhuǎn)化為整型數(shù)組，并逆置 t=strlen(a1); for(i=0;i<t;i++) a[i]=a1[t-1-i]-'0'; //整型數(shù)組的每個元素乘以b1，然后對其進行求余，整除，使其只有一位數(shù) a[0]=a[0]*b1; for(i=1;i<t;i++) { a[i]*=b1; a[i]+=a[i-1]/10; a[i-1]=a[i-1]%10; } while(a[i-1]>9) {//假設(shè)最后一個元素大于9 a[i]=a[i-1]/10; a[i-1]=a[i-1]%10; i++; } //將得到的整型數(shù)組逆置賦給字符串 for(j=0;j<i;j++) c[j]=a[i-j-1]+'0'; if(Judge(c))//假設(shè)積全為0，那么只輸出一個0 strcpy(c,"0");}高精度乘以高精度voidBigNumMultiBig(chara1[],charb1[]){ inti,j,k,lena,lenb; inta[1000]={0},b[1000]={0},d[2000]={0}; //將字符串轉(zhuǎn)化為整型數(shù)組，并逆置 lena=strlen(a1); lenb=strlen(b1); for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-i-1]-'0'; //計算乘數(shù)從低位到高位以此乘以被乘數(shù)的低位到高位 for(i=0;i<lena;i++) for(j=0;j<lenb;j++) { d[i+j]=d[i+j]+a[i]*b[j]; d[i+j+1]+=d[i+j]/10; d[i+j]=d[i+j]%10; } //根據(jù)高位是否為判斷整型數(shù)組的位數(shù) k=lena+lenb; while(!d[k-1]) k--; //積轉(zhuǎn)化為字符型 for(i=0;i<k;i++) c[i]=d[k-1-i]+'0'; if(Judge(c))//假設(shè)積全為0，那么只輸出一個1 strcpy(c,"0");}整型常量階乘voidBigNumFact(intx){ inti,k,m=0,a[1000]={0}; a[0]=1; for(;x;x--) {//m為在求階乘過程中a的元素個數(shù) for(k=i=0;i<=m;i++) { k=k+a[i]*x;//數(shù)組各個元素均乘以x(x遞減)，以完成階乘的運算 a[i]=k%10; k/=10; } while(k) { a[++m]=k%10; k/=10; } } //階乘的結(jié)果轉(zhuǎn)化為字符型 for(i=0;i<=m;i++) c[i]=a[m-i]+'0'; if(Judge(c))//假設(shè)結(jié)果全為，那么只輸出一個 strcpy(c,"0");}整型常量階乘和voidBigNumFactAdd(intt)//可以改良，減少算法時間復(fù)雜度{ inti; charsum[2000],d[2000]; //對字符串進行初始化 memset(d,0,sizeof(d)); memset(sum,0,sizeof(sum)); //分別求出相應(yīng)i的階乘然后相加 for(i=t;i>0;i--) { BigNumFact(i);//調(diào)用大數(shù)乘法。可以減少時間復(fù)雜度 strcpy(d,c); memset(c,0,sizeof(c)); BigNumberAdd(d,sum); strcpy(sum,c); memset(c,0,sizeof(c)); } strcpy(c,sum);//將結(jié)果賦值給全局變量，進行輸出}高精度的乘方voidBigNumInvol(chara1[],intb1)//冪為整型常量{ inti; chartemp[1000]; strcpy(temp,a1);//注意乘方是自己乘自己，而不是結(jié)果乘結(jié)果 for(i=2;i<b1;i++) { BigNumMultiBig(a1,temp); strcpy(temp,c); memset(c,0,sizeof(c));//將c清空，防止出現(xiàn)錯誤 } //進行最后一次乘法 BigNumMultiBig(a1,temp); if(Judge(c))//假設(shè)結(jié)果全為0，那么只輸出一個0 strcpy(c,"0");}高精度除法高精度除以低精度，只產(chǎn)生余數(shù)intBigNumDividSmall(chara1[],intb1){ if(!b1) return0; inti,j,k,flag=0,a[1000]={0}; charb[2000]; memset(b,0,sizeof(b)); k=strlen(a1); for(i=0;i<k;i++) a[i]=a1[i]-'0'; z=0; for(i=0;i<k;i++) { z=a[i]+z*10; b[i]=z/b1+'0'; z=z%b1; } i=j=0; while(b[i++]=='0'); for(i=i-1;i<k;i++) c[j++]=b[i]; return1;}高精度除以高精度，只產(chǎn)生余數(shù)voidBigNumDividBig(chara1[],charb1[]){ chara[1000],b[1000],time[1000]; intlena1,lentime,i,j,k,flag=0; memset(arr,0,sizeof(arr)); //假設(shè)被除數(shù)小于除數(shù)，那么商為，余數(shù)為被除數(shù) if(Compare(a1,b1)<0) strcpy(arr,a1); //假設(shè)兩數(shù)相等，那么商為，余數(shù)為 elseif(!Compare(a1,b1)) c[0]='1'; //假設(shè)被除數(shù)大于除數(shù) else { j=lentime=0; lena1=strlen(a1); memset(b,0,sizeof(b)); memset(time,0,sizeof(time)); for(i=0;i<lena1;i++) {//計算得到被除數(shù)的前幾位,得到整型數(shù)組形式的商 //time的一個元素表示一次相除的商 b[j++]=a1[i]; flag=0; while(Compare(b,b1)>=0) { BigNumberSub(b,b1); strcpy(b,c); memset(c,0,sizeof(c)); time[lentime]++; flag=1;//控制time的元素的位置 } if(flag)//將商轉(zhuǎn)換為字符 time[lentime]+='0'; else//當(dāng)被除數(shù)前幾位小于除數(shù)，商補 time[lentime]='0'; if(!strcmp(b,"0"))//假設(shè)b為‘’ j=0; else//繼續(xù)在b的后面加值 j=strlen(b); lentime++; } k=0; for(i=0;i<lentime;i++) if(time[i]!='0') break;//找到time數(shù)組中第一個不為的位置 for(j=i;j<lentime;j++) c[k++]=time[j]; strcpy(arr,b); } if(Judge(c)) strcpy(c,"0"); if(Judge(arr)) strcpy(arr,"0");}帶符號的數(shù)據(jù)運算2

$1,234,567.89

$9,876,543.21#include<string.h>#include<stdio.h>intmain(){ chars[10001][30],t[30]; longa,sum; inti,j,k,m,n; while(scanf("%d",&n)&&n) { sum=0; getchar(); for(i=0;i<n;i++) { gets(s[i]); m=strlen(s[i]); a=0; for(j=1;j<m;j++) { if(s[i][j]!=','&&s[i][j]!='.') a=a*10+(s[i][j]-'0'); } sum+=a; } if(sum<100) { t[0]=(sum%10-0)+'0'; t[1]=((sum%100-sum%10)/10+'0'); t[2]='.'; t[3]='0'; j=4; } else { t[0]=(sum%10-0)+'0'; t[1]=((sum%100-sum%10)/10+'0'); sum/=100; t[2]='.'; k=0; j=3; while(sum) { if(k!=3) { t[j]=sum%10+'0'; sum/=10; j++; k++; } else { t[j]=','; k=0; j++; } } } printf("$"); for(i=j-1;i>=0;i--) printf("%c",t[i]); printf("\n"); }}廣度優(yōu)先搜索大數(shù)應(yīng)用/*****求一個數(shù)m它的各個數(shù)位只由0或1構(gòu)成，并且能被輸入的整數(shù)m整除*******/#include<stdio.h>structnode{ inta,b;///a存0、1,b存余數(shù) intpre;//前一點}queue[200];voidoutput(intk){ if(queue[k].pre>=0) { output(queue[k].pre); } printf("%d",queue[k].a);}intmain(){ intn,r,i,j,L; queue[0].a=1; queue[0].b=1; queue[0].pre=-1; while(scanf("%d",&n)!=EOF)//除數(shù) { if(n==0) return0; charused[200]={0}; used[1]=1; L=1;//r if(n>1) { for(i=0;i<L;i++) { for(j=0;j<2;j++)//確定只有0或1,廣度優(yōu)先搜索思維 { r=(queue[i].b*10+j)%n; if(!used[r]) { queue[L].a=j; queue[L].b=r;//用余數(shù)繼續(xù)乘10+0或+1循環(huán)乘、取余直到整除 queue[L].pre=i; used[r]=1; L++;//用來控制輸出01序列的,構(gòu)造是從右往左,輸出時從左往右(L-1開始) } if(r==0) break; } if(r==0) break; } } output(L-1); printf("\n"); } return0;}基于比擬的排序算法#include<iostream>usingnamespacestd;#defineSWAP(i,j){intt=(i);(i)=(j);(j)=t;}插入排序voidInsertSort(int*a,intlen)//算法主體函數(shù){ for(inti=1;i<len;i++) { intj=i,x=a[i]; while(j&&a[j-1]>x) a[j]=a[j-1],j--; a[j]=x; }}/********************************/選擇排序voidSelectSort(int*a,intlen)//算法主體函數(shù){ for(inti=1,j,k;i<len;i++) { for(j=i,k=i-1;j<len;j++) if(a[j]<a[k]) k=j; if(k>=i) SWAP(a[i-1],a[k]); }}/********************************/冒泡排序voidBubbletSort(int*a,intlen)//算法主體函數(shù){ for(boolbSwap=true;bSwap;len--) { bSwap=false; for(intj=1;j<len;j++) if(a[j-1]>a[j]) { SWAP(a[j-1],a[j]); bSwap=true; } }}/********************************/堆排序//堆調(diào)整voidHeapAdjust(int*a,introot,intlen){ intchild,x=a[root]; while(child=root<<1|1,child<len) { if(child<len-1&&a[child]<a[child+1]) child++; if(x<a[child]) { a[root]=a[child]; root=child; } else break; } a[root]=x;}//堆排序voidHeapSort(int*a,intlen)//算法主體函數(shù){ for(inti=len/2-1;i>=0;i--) HeapAdjust(a,i,len); while(--len) { SWAP(a[0],a[len]); HeapAdjust(a,0,len); }}/********************************/歸并排序//歸并voidMerge(int*a,intlen1,intlen2){ int*a1=newint[len1+1],*a2=newint[len2+1],len=len1+len2; for(inti=0;i<len1;i++) a1[i]=a[i]; for(inti=0;i<len2;i++) a2[i]=a[len1+i]; a1[len1]=a2[len2]=INT_MAX; for(inti=0,j=0,k=0;k<len;k++) if(a1[i]<a2[j]) a[k]=a1[i++]; else a[k]=a2[j++]; delete[]a1;delete[]a2;}//歸并排序voidMergeSort(int*a,intlen)//算法主體函數(shù){ if(len>1) { intc=len/2; MergeSort(a,c); MergeSort(a+c,len-c); Merge(a,c,len-c); }}/********************************/快速排序//劃分intPartition(int*a,intlen){ intx=a[--len],i=-1; for(intj=0;j<len;j++) if(a[j]<x) { i++; SWAP(a[i],a[j]); } SWAP(a[i+1],a[len]); returni+1;}//快速排序voidQuickSort(int*a,intlen)//算法主體函數(shù){ if(len>0) { intq=Partition(a,len); if(q<len-q) { QuickSort(a,q-1); QuickSort(a+q+1,len-q-1); } else { QuickSort(a+q+1,len-q-1); QuickSort(a,q-1); } }}/***********插入式希爾排序****************/希爾排序//希爾插入voidShellInsert(int*a,intinc,intlen){ for(inti=inc;i<len;i+=inc) { intj=i,x=a[i]; while(j>0&&a[j-inc]>x) a[j]=a[j-inc],j-=inc; a[j]=x; }}//插入式希爾排序voidShellSort(int*a,intlen)//算法主體函數(shù){ intinc=len; do { inc=inc/3+1; for(ints=0;s<inc;s++) ShellInsert(a-s,inc,len+s); } while(inc>1);}/********************************/同余運算(1〕ifa≡b(Modm)andc≡d(Modm),thena+c≡b+d(Modm)(2〕ifa≡b(Modm)andc≡d(Modm),thenac≡bd(Modm)(3〕ifa≡b(Modm)k>0,thenak≡bk(Modmk)(4〕ifa≡b(Modm)andd|a,d|b,d|m,thena/d≡b/d(Modm/d)(5〕ifa≡b(Modm)andd|m,thena≡b(Modd)(6〕ifca≡cb(Modm)andd=gcd(c,m),thena≡b(Modm/d)假設(shè)a≡0(Modm)，稱a被m整除模線性方程問題/*求最小的N，使得A+C*N==B(mod2^k)。也就是求模線性方程C*N==B-A(mod2^k)的最小解,N<4^k推論1：方程ax=b(modn)對于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n)|b。推論2：方程ax=b(modn)或者對模n有d個不同的解，其中d=gcd(a,n)，或者無解。定理1：設(shè)d=gcd(a,n)，假定對整數(shù)x和y滿足d=ax+by(比方用擴展Euclid算法求出的一組解)。如果d|b，那么方程ax=b(modn)有一個解x0滿足x0=x*(b/d)modn。特別的設(shè)e=x0+n，方程ax=b(modn)的最小整數(shù)解x1=emod(n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。定理2：假設(shè)方程ax=b(modn)有解，且x0是方程的任意一個解，那么該方程對模n恰有d個不同的解(d=gcd(a,n))，分別為：xi=x0+i*(n/d)modn。以上定理的具體證明見《算法導(dǎo)論》*/#include<iostream>#include<cmath>usingnamespacestd;#definemod(a,b)((a)%(b)+(b))%(b)//把負(fù)數(shù)轉(zhuǎn)化成為正數(shù)typedeflonglongint64;int64ext_euclid(int64a,int64b,int64&x,int64&y){ int64t,d; if(b==0) { x=1; y=0; returna; } d=ext_euclid(b,mod(a,b),x,y); t=x; x=y; y=t-a/b*y; returnd;}voidmodular_linear_equation_solver(int64a,int64b,int64n){ int64d; int64x,y; d=ext_euclid(a,n,x,y); if(mod(b,d)>0) cout<<"FOREVER"<<endl; elsecout<<mod((x*(b/d)),n/d)<<endl;}intmain(){ int64a,b,c,n; intk; while(cin>>a>>b>>c>>k) { if(!a&&!b&&!c&&!k) break; n=pow(2.0,k); modular_linear_equation_solver(c,b-a,n); } return0;}方法二：#ifdefWIN32typedef__int64i64;#elsetypedeflonglongi64;#endif//擴展Euclid求解gcd(a,b)=ax+byintext_gcd(inta,intb,int&x,int&y){ intt,ret; if(!b){ x=1,y=0; returna; } ret=ext_gcd(b,a%b,x,y); t=x,x=y,y=t-a/b*y; returnret;}//計算m^a,O(loga),本身沒什么用,注意這個按位處理的方法:-Pintexponent(intm,inta){ intret=1; for(;a;a>>=1,m*=m) if(a&1) ret*=m; returnret;}//計算冪取模a^bmodn,O(logb)intmodular_exponent(inta,intb,intn){//a^bmodn intret=1; for(;b;b>>=1,a=(int)((i64)a)*a%n) if(b&1) ret=(int)((i64)ret)*a%n; returnret;}//求解模線性方程ax=b(modn)//返回解的個數(shù),解保存在sol[]中//要求n>0,解的范圍0..n-1intmodular_linear(inta,intb,intn,int*sol){ intd,e,x,y,i; d=ext_gcd(a,n,x,y); if(b%d) return0; e=(x*(b/d)%n+n)%n; for(i=0;i<d;i++) sol[i]=(e+i*(n/d))%n; returnd;}//求解模線性方程組(中國余數(shù)定理)//x=b[0](modw[0])//x=b[1](modw[1])//...//x=b[k-1](modw[k-1])//要求w[i]>0,w[i]與w[j]互質(zhì),解的范圍1..n,n=w[0]*w[1]*...*w[k-1]intmodular_linear_system(intb[],intw[],intk){ intd,x,y,a=0,m,n=1,i; for(i=0;i<k;i++) n*=w[i]; for(i=0;i<k;i++){ m=n/w[i]; d=ext_gcd(w[i],m,x,y); a=(a+y*m*b[i])%n; } return(a+n)%n;}計算a^nmodk//k<40000intpowmod(inta,intn,intk){intd=1;for(a%=k;n>0;n>>=1){if(n&1)d=(d*a)%k;a=(a*a)%k;}returnd;}階乘最后非0位//求階乘最后非零位,復(fù)雜度O(nlogn)//返回該位,n以字符串方式傳入#include<string.h>#defineMAXN10000intlastdigit(char*buf){ constintmod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; intlen=strlen(buf),a[MAXN],i,c,ret=1; if(len==1) returnmod[buf[0]-'0']; for(i=0;i<len;i++) a[i]=buf[len-1-i]-'0'; for(;len;len-=!a[len-1]){ ret=ret*mod[a[1]%2*10+a[0]]%5; for(c=0,i=len-1;i>=0;i--) c=c*10+a[i],a[i]=c/5,c%=5; } returnret+ret%2*5;}素數(shù)篇除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)，又稱質(zhì)數(shù)。方法一：voidprim(){ longi,j,k; prime[0]=2; prime[1]=3; jue[2]=true; jue[3]=true; jue[5]=true; for(i=5,k=2;i<999983;i+=2) { for(j=0;prime[j]*prime[j]<=i&&i%prime[j];) { j++; if(prime[j]*prime[j]>i) { prime[k++]=i; jue[i]=true; } } }}方法二：#include<string.h>boolused[21000];voidgetprimes(){ memset(used,true,sizeof(used)); used[0]=false; used[1]=false; for(inti=2;i<=21000;i++) { if(used[i]) for(intj=2*i;j<=21000;j+=i) used[j]=false; }}線性篩法constintUPBOUND=100000;inta[UPBOUND];intp[UPBOUND],pn;//號稱線性的篩素數(shù)算法，實際性能確實不錯//p[]={2,3,5,7,...},pn為小于UPBOUND的素數(shù)個數(shù)//假設(shè)i是合數(shù)a[i]為i的最小因子，假設(shè)i是素數(shù)a[i]=0voidprimefilter(){inti,j;for(i=2;i<UPBOUND;++i) { if(!(a[i]))p[pn++]=i; for(j=0;(j<pn&&i*p[j]<UPBOUND&&(p[j]<=a[i]||a[i]==0));++j) a[i*p[j]]=p[j]; }}voidprim()//建立素數(shù)表{ longlongi,j,k; prime[0]=2; prime[1]=3; for(i=5,k=2;i<47000;i+=2) { for(j=1;prime[j]*prime[j]<=i&&i%prime[j];j++); if(prime[j]*prime[j]>i) prime[k++]=i; }}voidgetprimes()//構(gòu)建素數(shù)表{ inti; primes[1]=1;for(i=2;i<=32;i++) { if(!primes[i]) for(intj=2*i;j<=32;j+=i) primes[j]=1; }}費馬小定理假設(shè)p為素數(shù)，a為正整數(shù)，那么一定有a^p≡a(Modp)MR素性測試給定整數(shù)a，假設(shè)滿足a^p≡a(Modp)，p為一個素數(shù)，那么a很可能也是素數(shù)歐拉函數(shù)問題#include<stdio.h>intmain(){longn,i,k;doubler;while(scanf("%ld",&n)&&n) { r=n; i=2;while(n>1) { k=0;while(n%i==0) {n/=i; k=1; }if(k) r*=1.0-1.0/i;if(i==2)i++;else i=i+2; }printf("%.0lf\n",r); }return0;}巴赫猜測/*哥德巴赫猜測:每一個數(shù)最多可由3個素數(shù)相加表示，任意一個大于4的偶數(shù)必定可以表示為兩奇素數(shù)之和*/#include<stdio.h>intcnt,n,tmp;intff[10001],f[10001],b[10001],primes[3000];voidprime(){inti,j,t;for(i=0;i<10001;i++)ff[i]=0;for(i=2;i<=100;i++) {if(ff[i])continue; j=i*i;while(j<=10000){ff[j]=1; j+=i; } }cnt=0;for(i=2;i<=10000;i++)if(ff[i]==0)primes[cnt++]=i;for(i=0;i<10001;i++)f[i]=-1;f[0]=0;for(i=0;i<cnt;i++) { t=primes[i];for(j=t;j<=3*t;j++) { /////***************和包含t的數(shù)中，最小為t，最大為t+t+tif(j>10000)break;if(f[j-t]!=-1&&(f[j]==-1||f[j]>f[j-t]+1)) {f[j]=f[j-t]+1;b[j]=t; } } }}intmain(){prime();while(scanf("%d",&n)!=EOF) {if(n<=1)printf("0\n");else {if(ff[n]==0) {printf("1\n");printf("%d\n",n);continue; }else {printf("%d\n",f[n]);while(n>0) {printf("%d",b[n]);n-=b[n];if(n==0)printf("\n");elseprintf(""); } } } }return0;}最大公約數(shù)intgcd(inta,intb)//遞歸實現(xiàn){return(b?gcd(b,a%b):a);}intgcd(inta,intb)//非遞歸實現(xiàn){while(b){intt=a%b;a=b;b=t;}returna;}最小公倍數(shù)lcm(a,b)=a/gcd(a,b)*b不定方程求解二元線性不定方程：形如ax+by=c不定方程求解程序：對于方程ax+by=gcd(a,b)voideuclid_gcd(inta,intb,int&d,int&x,int&y){if(!b){d=a;x=1;y=0;}else{ euclid_gcd(b,a%b,d,y,x); y-=x*(a/b); }}概率因子分解Pollard算法typedef__int64Long;//或自定義大整數(shù)類〔必須重載運算符〕LongPollard(Longn){ Longi=1,x=rand()%n,y=x,k=2;while(1) { ++i; x=(x*x-1)%n; Longd=gcd(y-x,n);if(d>1&&d<n)returnd;if(i==k) { y=x;k*=2; } }return-1;}數(shù)值計算[2]定積分計算(Romberg)/*Romberg求定積分輸入：積分區(qū)間[a,b]，被積函數(shù)f(x,y,z)輸出：積分結(jié)果f(x,y,z)例如：doublef0(doublex,doublel,doublet){returnsqrt(1.0+l*l*t*t*cos(t*x)*cos(t*x));}*/doubleIntegral(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet)doubleRomberg(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet){#defineMAX_N1000inti,j,temp2,min;doubleh,R[2][MAX_N],temp4;for(i=0;i<MAX_N;i++){R[0][i]=0.0;R[1][i]=0.0; } h=b-a;min=(int)(log(h*10.0)/log(2.0));//hshouldbeatmost0.1R[0][0]=((*f)(a,l,t)+(*f)(b,l,t))*h*0.50; i=1; temp2=1;while(i<MAX_N){i++;R[1][0]=0.0;for(j=1;j<=temp2;j++)R[1][0]+=(*f)(a+h*((double)j-0.50),l,t);R[1][0]=(R[0][0]+h*R[1][0])*0.50; temp4=4.0;for(j=1;j<i;j++){R[1][j]=R[1][j-1]+(R[1][j-1]-R[0][j-1])/(temp4-1.0); temp4*=4.0; }if((fabs(R[1][i-1]-R[0][i-2])<eps)&&(i>min))returnR[1][i-1];h*=0.50; temp2*=2;for(j=0;j<i;j++)R[0][j]=R[1][j]; }returnR[1][MAX_N-1];}doubleIntegral(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet){intn;doubleR,p,res; n=(int)(floor)(b*t*0.50/pi); p=2.0*pi/t;res=b-(double)n*p;if(n) R=Romberg(a,p,f0,eps/(double)n,l,t); R=R*(double)n+Romberg(0.0,res,f0,eps,l,t);returnR/100.0;}多項式求根(牛頓法)/*牛頓法解多項式的根輸入：多項式系數(shù)c[]，多項式度數(shù)n，求在[a,b]間的根輸出：根要求保證[a,b]間有根*/doublefabs(doublex){return(x<0)?-x:x;}doublef(intm,doublec[],doublex){inti;doublep=c[m];for(i=m;i>0;i--) p=p*x+c[i-1];returnp;}intnewton(doublex0,double*r,doublec[],doublecp[],intn,doublea,doubleb,doubleeps){intMAX_ITERATION=1000;inti=1;doublex1,x2,fp,eps2=eps/10.0;x1=x0;while(i<MAX_ITERATION){x2=f(n,c,x1);fp=f(n-1,cp,x1);if((fabs(fp)<0.000000001)&&(fabs(x2)>1.0))return0;x2=x1-x2/fp;if(fabs(x1-x2)<eps2){if(x2<a||x2>b)return0; *r=x2;return1; }x1=x2;i++; }return0;}doublePolynomial_Root(doublec[],intn,doublea,doubleb,doubleeps){double*cp;inti;doubleroot;cp=(double*)calloc(n,sizeof(double));for(i=n-1;i>=0;i--){cp[i]=(i+1)*c[i+1]; }if(a>b){root=a;a=b;b=root; }if((!newton(a,&root,c,cp,n,a,b,eps))&&(!newton(b,&root,c,cp,n,a,b,eps)))newton((a+b)*0.5,&root,c,cp,n,a,b,eps);free(cp);if(fabs(root)<eps)returnfabs(root);elsereturnroot;}周期性方程(追趕法)/*追趕法解周期性方程周期性方程定義：|a1b1c1...|=x1|a2b2c2...|=x2|...|*X=...|cn-1...an-1bn-1|=xn-1|bncnan|=xn輸入：a[],b[],c[],x[]輸出：求解結(jié)果X在x[]中*/voidrun(){ c[0]/=b[0];a[0]/=b[0];x[0]/=b[0]; for(inti=1;i<N-1;i++){ doubletemp=b[i]-a[i]*c[i-1]; c[i]/=temp; x[i]=(x[i]-a[i]*x[i-1])/temp; a[i]=-a[i]*a[i-1]/temp; } a[N-2]=-a[N-2]-c[N-2]; for(inti=N-3;i>=0;i--){ a[i]=-a[i]-c[i]*a[i+1]; x[i]-=c[i]*x[i+1]; } x[N-1]-=(c[N-1]*x[0]+a[N-1]*x[N-2]); x[N-1]/=(c[N-1]*a[0]+a[N-1]*a[N-2]+b[N-1]); for(inti=N-2;i>=0;i--) x[i]+=a[i]*x[N-1];}組合論[3]組合公式1.C(m,n)=C(m,m-n)2.C(m,n)=C(m-1,n)+C(m-1,n-1)derangementD(n)=n!(1-1/1!+1/2!-1/3!+...+(-1)^n/n!)=(n-1)(D(n-2)-D(n-1))Q(n)=D(n)+D(n-1)求和公式,k=1..n1.sum(k)=n(n+1)/22.sum(2k-1)=n^23.sum(k^2)=n(n+1)(2n+1)/64.sum((2k-1)^2)=n(4n^2-1)/35.sum(k^3)=(n(n+1)/2)^26.sum((2k-1)^3)=n^2(2n^2-1)7.sum(k^4)=n(n+1)(2n+1)(3n^2+3n-1)/308.sum(k^5)=n^2(n+1)^2(2n^2+2n-1)/129.sum(k(k+1))=n(n+1)(n+2)/310.sum(k(k+1)(k+2))=n(n+1)(n+2)(n+3)/412.sum(k(k+1)(k+2)(k+3))=n(n+1)(n+2)(n+3)(n+4)/5全組合排列方法一：#defineMAX_N10intn;//共n個數(shù)intrcd[MAX_N];//記錄每個位置填的數(shù)intused[MAX_N];//標(biāo)記數(shù)是否用過intnum[MAX_N];//存放輸入的n個數(shù)voidfull_permutation(intL){ inti; if(L==n+1) { //輸出 return; } for(i=1;i<=n;i++)//枚舉所有的數(shù)，循環(huán)從0開始 if(!used[i]){//num[i]沒有使用過 used[i]=1;//標(biāo)記為已使用 rcd[L]=i;//在l位置放上該數(shù) full_permutation(L+1);//填下一個位置 used[i]=0;//清標(biāo)記 }}方法二：#include<iostream>usingnamespacestd;intx[11]={0,1,2,3,4,5,6,7,8,9,10};voidpermute(intt)//全排列{ if(t>n) output(); else { for(inti=t;i<=n;i++) { swap(x[t],x[i]); permute(t+1); swap(x[t],x[i]); } }}測試函數(shù)SampleInput3123SampleOutput123132213231312321//Program#include<stdio.h>#include<string.h>constintmaxn=11;intn;intused[maxn];//標(biāo)記數(shù)組intmat[maxn];//存儲數(shù)組intnum[maxn];//輸出數(shù)組voidsolve(intl){ if(l>=n) { for(inti=0;i<n;++i)printf("%d",num[i]); puts(""); return; } for(inti=0;i<n;++i) { if(!used[i]) { used[i]=1; num[l]=mat[i]; solve(l+1); used[i]=0; } }}intmain(){ while(scanf("%d",&n)!=EOF) { for(inti=0;i<n;++i)scanf("%d",mat+i); memset(used,0,sizeof(used)); solve(0); } return0;}非重復(fù)組合排列含重復(fù)數(shù)字時，生成不重復(fù)組合排列SampleInput41223SampleOutput122312321322212321322213223123122321312232123221//Program#include<stdio.h>constintmaxn=10;intn,var;intIndex;intused[maxn],mat[maxn],num[maxn];voidpush(intvarNum){ //壓棧for(inti=0;i<Index;++i){if(mat[i]==varNum){++used[i];return;}}mat[Index]=varNum;++used[Index++];}voidsolve(intl){ //求解if(l>=n){for(inti=0;i<n;++i)printf("%d",num[i]);puts("");return;}for(inti=0;i<Index;++i){if(used[i]){used[i]--;num[l]=mat[i];solve(l+1);used[i]++;}}}intmain(){while(scanf("%d",&n)!=EOF){Index=0;for(inti=0;i<n;++i){scanf("%d",&var);push(var);}solve(0);}return0;}類循環(huán)組合排列SampleInput：42SampleOutput0000000100100011010001010110011110001001101010111100110111101111//Program#include<stdio.h>intn,m;intmat[10];voidsolve(intl){ if(l>=n) { for(inti=0;i<n;++i) printf("%d",mat[i]); puts(""); return; } for(inti=0;i<m;++i) { mat[l]=i; solve(l+1); }}intmain(){ while(scanf("%d%d",&n,&m)!=EOF) { solve(0); } return0;}普通選擇性組合排列SampleInput5312345SampleOutput123124125134135145234235245345//Program#include<stdio.h>constintmaxn=10;inttotalN,selectM;intmat[maxn];//存儲數(shù)組intnum[maxn];//輸出數(shù)組voidsolve(intstartVar,intselectVar){if(selectVar>=selectM){for(inti=0;i<selectM;++i)printf("%d",num[i]);puts("");return;}for(inti=startVar;i<totalN;++i){num[selectVar]=mat[i];solve(i+1,selectVar+1);}}intmain(){while(scanf("%d%d",&totalN,&selectM)!=EOF){for(inti=0;i<totalN;++i)scanf("%d",mat+i);solve(0,0);}return0;}生成全子集組合排列SampleInput41234SampleOutput11212312341241313414223234243344//Program#include<stdio.h>constintmaxn=10;intn;intmat[maxn];intnum[maxn];voidsolve(intcur_totalVar,intnextVar){for(inti=0;i<cur_totalVar;++i)printf("%d",num[i]);if(cur_totalVar)puts("");for(inti=nextVar;i<n;++i){num[cur_totalVar]=mat[i];solve(cur_totalVar+1,i+1);}}intmain(){while(scanf("%d",&n)!=EOF){for(inti=0;i<n;++i)scanf("%d",mat+i);solve(0,0);}return0;}//注意：倘假設(shè)需要輸出空集〔也即輸出一個換行〕，可做如下修改//在函數(shù)solve()中，將if(cur_totalVar)puts("");改為puts("");非重復(fù)生成全子集組合排列含重復(fù)數(shù)字時，生成不重復(fù)全子集組合排列SampleInput41223SampleOutput112122122312313222223233//Program#include<stdio.h>constintmaxn=10;intn,var;intIndex;intused[maxn],mat[maxn],num[maxn];voidpush(intvarNum){ //壓棧for(inti=0;i<Index;++i){if(mat[i]==varNum){++used[i];return;}}mat[Index]=varNum;++used[Index++];}voidsolve(intl,intp){ //求解for(inti=0;i<l;++i)printf("%d",num[i]);if(l)puts("");for(inti=p;i<Index;++i){if(used[i]){used[i]--;num[l]=mat[i];solve(l+1,i);used[i]++;}}}intmain(){while(scanf("%d",&n)!=EOF){Index=0;for(inti=0;i<n;++i){scanf("%d",&var);push(var);}solve(0,0);}return0;}//注意：倘假設(shè)需要輸出空集〔也即輸出一個換行〕，可做如下修改//在函數(shù)solve()中，將if(l)puts("");改為puts("");一般組合select_combination(intStep,intPos){ //已經(jīng)確定Step-1個數(shù)字,第Step步的數(shù)為X[Pos,…,n]的任一個 if(Step==m+1) {//已確定數(shù)字?jǐn)?shù)目為m時， Output(); //輸出一種組合 return; }for(i=Pos;i<=n;i++) { A[Step]=X[i]; select_combination(Step+1,Pos+1); }}一般組合的優(yōu)化select_combination(intStep,intPos){ //已經(jīng)確定Step-1個數(shù)字,第Step步的數(shù)為X[Pos,…,n]的任一個 if(Step==m+1) {//已確定數(shù)字?jǐn)?shù)目為m時， Output(); //輸出一種組合 return; }for(i=Pos;i<=n-m+Step;i++) { A[Step]=X[i]; select_combination(Step+1,Pos+1); }}總結(jié)：遞歸思想在搜索技術(shù)中有著廣泛的應(yīng)用，應(yīng)當(dāng)熟練掌握和學(xué)習(xí)這種思想，對求解這一類搜索題目大有裨益。排列組合生成//gen_perm產(chǎn)生字典序排列P(n,m)//gen_comb產(chǎn)生字典序組合C(n,m)//gen_perm_swap產(chǎn)生相鄰位對換全排列P(n,n)//產(chǎn)生元素用1..n表示//dummy為產(chǎn)生后調(diào)用的函數(shù),傳入a[]和n,a[0]..a[n-1]為一次產(chǎn)生的結(jié)果#defineMAXN100intcount;#include<iostream.h>voiddummy(int*a,intn){ inti; cout<<count++<<":"; for(i=0;i<n-1;i++) cout<<a[i]<<''; cout<<a[n-1]<<endl;}void_gen_perm(int*a,intn,intm,intl,int*temp,int*tag){ inti; if(l==m) dummy(temp,m); else for(i=0;i<n;i++) if(!tag[i]){ temp[l]=a[i],tag[i]=1; _gen_perm(a,n,m,l+1,temp,tag); tag[i]=0; }}voidgen_perm(intn,intm){ inta[MAXN],temp[MAXN],tag[MAXN]={0},i; for(i=0;i<n;i++) a[i]=i+1; _gen_perm(a,n,m,0,temp,tag);}void_gen_comb(int*a,ints,inte,intm,int&count,int*temp){ inti; if(!m) dummy(temp,count); else for(i=s;i<=e-m+1;i++){ temp[count++]=a[i]; _gen_comb(a,i+1,e,m-1,count,temp); count--; }}voidgen_comb(intn,intm){ inta[MAXN],temp[MAXN],count=0,i; for(i=0;i<n;i++) a[i]=i+1; _gen_comb(a,0,n-1,m,count,temp);}void_gen_perm_swap(int*a,intn,intl,int*pos,int*dir){ inti,p1,p2,t; if(l==n) dummy(a,n); else{ _gen_perm_swap(a,n,l+1,pos,dir); for(i=0;i<l;i++){ p2=(p1=pos[l])+dir[l]; t=a[p1],a[p1]=a[p2],a[p2]=t; pos[a[p1]-1]=p1,pos[a[p2]-1]=p2; _gen_perm_swap(a,n,l+1,pos,dir); } dir[l]=-dir[l]; }}voidgen_perm_swap(intn){ inta[MAXN],pos[MAXN],dir[MAXN],i; for(i=0;i<n;i++) a[i]=i+1,pos[i]=i,dir[i]=-1; _gen_perm_swap(a,n,0,pos,dir);}生成gray碼//生成reflectedgraycode//每次調(diào)用gray取得下一個碼//000...000是第一個碼,100...000是最后一個碼voidgray(intn,int*code){ intt=0,i; for(i=0;i<n;t+=code[i++]); if(t&1) for(n--;!code[n];n--); code[n-1]=1-code[n-1];}置換(polya)//求置換的循環(huán)節(jié),polya原理//perm[0..n-1]為0..n-1的一個置換(排列)//返回置換最小周期,num返回循環(huán)節(jié)個數(shù)#defineMAXN1000intgcd(inta,intb){ returnb?gcd(b,a%b):a;}intpolya(int*perm,intn,int&num){ inti,j,p,v[MAXN]={0},ret=1; for(num=i=0;