数据结构 基本算法

《数据结构 基本算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基本算法c语言版一、数论算法1、求两个数的最大公约数原理：欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：定理：gcd(a,b)=gcd(b,amodb)证明：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有d

2、a,d

3、b，而r=a-kb，因此d

4、r因此d是(b,amodb)的公约数假设d是(b,amodb)的公约数，则d

5、b,d

6、r，但是a=kb+r因此d也是(a,b)的公约数因此(a,b)和(b,amodb)的公约数是一样的，其最大公约数也必然相等，

7、得证参考代码：intgcb(inta,intb){if(b==0)returna;else{returngcb(b,a%b);}2、求最小公倍数intlcm(inta,intb){intt,p;if(b>a){t=a;a=b;b=t;}p=a;while((p%b)!=0)p=p+a;returnp;}3、求素数1）小范围内判断一个数是否为质数intprimc(inta){inti,p;p=sqrt(a);for(i=2;i<=p;i++)if(a%i==0)break;if(i<=p)return0;elsereturn

8、1;}2）判断longint范围内的数是否为素数（包含求50000以内的素数表）intprc[50000],prim[50000];voidgetprimc(){longinti,j;for(i=2;i<50000;i++)prc[i]=1;prc[1]=0;i=2;while(i<50000){if(prc[i]){j=i*2;while(j<50000){prc[j]=0;j=j+i;}}i++;}j=0;for(i=2;i<50000;i++){if(prc[i]){j++;prim[j]=i;}}prim[0]=j

9、;/*for(i=1;i<=j;i++){printf("%ld",prim[i]);if(i%1000==0){printf("");getch();}}//77591519334603*/}intprimc2(longinta){longinti,p;getprimc();p=prim[0];printf("pnum=%ld",p);for(i=1;i

10、

11、(a

12、、高精度加法与乘法#include#includecharstr1[30],str2[30];inta[50],b[50],c[100],len1,len2,len;//高精度加法intgjdplus(){inti,k,len;len1=strlen(str1);len2=strlen(str2);k=0;for(i=len1;i>=0;i--){a[k]=str1[i-1]-48;k=k+1;}k=0;for(i=len2;i>=0;i--){b[k]=str2[i-1]-48;k=

13、k+1;}if(len1len2)k=len1;elsek=len2;intf=0;for(i=0;i=10)f=a[i]/10;elsef=0;a[i]=a[i]%10;}len=k-1;if(f!=0){a[k]=f;len=k;printf("%d",a[k]);}returnlen;}//高精度

14、乘法intmultiply(){inti,j,k;len1=strlen(str1);len2=strlen(str2);k=0;for(i=len1-1;i>=0;i--){a[k]=str1[i]-'0';k=k+1;}for(i=0;i=0;i--){b[k]=str2[i]-'0';k=k+1;}for(i=0;i

15、;for(i=0;i