第一篇：RSA加密解密算法C语言代码
#include
#include
#include
void sub(int a[MAX],int b[MAX] ,int c[MAX]);
struct slink {
int bignum[MAX];/*bignum[98]用来标记正负号，1正，0负bignum[99]来标记实际长度*/
struct slink *next;};
/*/-------自己建立的大数运算库------*/
void print(int a[MAX])
{
int i;
for(i=0;i printf(“%d”,a[a[99]-i-1]); printf(“nn”); return; } int cmp(int a1[MAX],int a2[MAX]){ int l1, l2;int i;l1=a1[99];l2=a2[99];if(l1>l2) return 1; if(l1 return-1; for(i=(l1-1);i>=0;i--) { if(a1[i]>a2[i]) return 1; if(a1[i] return-1; } return 0;} void mov(int a[MAX],int *b){ int j; for(j=0;j b[j]=a[j]; return;} void mul(int a1[MAX],int a2[MAX],int *c){ int i,j;int y;int x;int z;int w;int l1, l2;l1=a1[MAX-1];l2=a2[MAX-1];if(a1[MAX-2]=='-'&& a2[MAX-2]=='-') c[MAX-2]=0;else if(a1[MAX-2]=='-') c[MAX-2]='-';else if(a2[MAX-2]=='-') c[MAX-2]='-';for(i=0;i for(j=0;j { x=a1[i]*a2[j]; y=x/10; z=x%10; w=i+j; c[w]=c[w]+z; c[w+1]=c[w+1]+y+c[w]/10; c[w]=c[w]%10; } } w=l1+l2;if(c[w-1]==0)w=w-1;c[MAX-1]=w;return;} void add(int a1[MAX],int a2[MAX],int *c){ int i,l1,l2;int len,temp[MAX];int k=0;l1=a1[MAX-1];l2=a2[MAX-1];if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-')){ c[MAX-2]='-';} else if(a1[MAX-2]=='-'){ mov(a1,temp);temp[MAX-2]=0;sub(a2,temp,c);return;} else if(a2[MAX-2]=='-'){ mov(a2,temp);temp[98]=0;sub(a1,temp,c);return;} if(l1 c[i]=(a1[i]+a2[i]+k)%10; k=(a1[i]+a2[i]+k)/10;} if(l1>len){ for(i=len;i { c[i]=(a1[i]+k)%10; k=(a1[i]+k)/10; } if(k!=0) { c[l1]=k; len=l1+1; } else len=l1;} else { for(i=len;i { c[i]=(a2[i]+k)%10; k=(a2[i]+k)/10; } if(k!=0) { c[l2]=k; len=l2+1; } else len=l2;} c[99]=len; return;} void sub(int a1[MAX],int a2[MAX],int *c){ int i,l1,l2;int len,t1[MAX],t2[MAX];int k=0;l1=a1[MAX-1];l2=a2[MAX-1];if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-')){ mov(a1,t1); mov(a2,t2);t1[MAX-2]=0; t2[MAX-2]=0;sub(t2,t1,c);return;} else if(a2[MAX-2]=='-'){ mov(a2,t2);t2[MAX-2]=0;add(a1,t2,c);return;} else if(a1[MAX-2]=='-'){ mov(a2,t2);t2[MAX-2]='-';add(a1,t2,c);return;} if(cmp(a1,a2)==1){ len=l2;for(i=0;i if((a1[i]-k-a2[i])<0){ c[i]=(a1[i]-a2[i]-k+10)%10; k=1;} else { c[i]=(a1[i]-a2[i]-k)%10; k=0; } } for(i=len;i { if((a1[i]-k)<0){ c[i]=(a1[i]-k+10)%10; k=1;} else { c[i]=(a1[i]-k)%10; k=0; } } if(c[l1-1]==0)/*使得数组C中的前面所以0字符不显示了，如1000-20=0980--->显示为980了*/ { len=l1-1; i=2; while(c[l1-i]==0)/*111456-111450=00006，消除0后变成了6；*/ { len=l1-i; i++; } } else { len=l1; } } else if(cmp(a1,a2)==(-1)){ c[MAX-2]='-'; len=l1; for(i=0;i if((a2[i]-k-a1[i])<0){ c[i]=(a2[i]-a1[i]-k+10)%10; k=1;} else { c[i]=(a2[i]-a1[i]-k)%10; k=0; } } for(i=len;i { if((a2[i]-k)<0){ c[i]=(a2[i]-k+10)%10; k=1;} else { c[i]=(a2[i]-k)%10; k=0; } } if(c[l2-1]==0) { len=l2-1; i=2; while(c[l1-i]==0) { len=l1-i; i++; } } else len=l2; } else if(cmp(a1,a2)==0) { len=1; c[len-1]=0; } c[MAX-1]=len;return;} void mod(int a[MAX],int b[MAX],int *c)/*/c=a mod b//注意：经检验知道此处A和C的数组都改变了。*/ { int d[MAX];mov(a,d);while(cmp(d,b)!=(-1))/*/c=a-b-b-b-b-b.......until(c sub(d,b,c); mov(c,d);/*/c复制给a*/ } return;} void divt(int t[MAX],int b[MAX],int *c ,int *w)/*//试商法//调用以后w为a mod b, C为a div b;*/ { int a1,b1,i,j,m;/*w用于暂时保存数据*/ int d[MAX],e[MAX],f[MAX],g[MAX],a[MAX]; mov(t,a); for(i=0;i e[i]=0;for(i=0;i d[i]=0;for(i=0;i b1=b[MAX-1];if(cmp(a,b)==(-1)){ c[0]=0; c[MAX-1]=1; mov(t,w); return;} else if(cmp(a,b)==0){ c[0]=1; c[MAX-1]=1; w[0]=0; w[MAX-1]=1; return;} m=(a1-b1); for(i=m;i>=0;i--)/*341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1*/ { for(j=0;j d[j]=0; d[i]=1; d[MAX-1]=i+1; mov(b,g); mul(g,d,e); while(cmp(a,e)!=(-1)) { c[i]++; sub(a,e,f); mov(f,a);/*f复制给g*/ } for(j=i;j e[j]=0; } mov(a,w);if(c[m]==0)c[MAX-1]=m;else c[MAX-1]=m+1; return;} void mulmod(int a[MAX] ,int b[MAX] ,int n[MAX],int *m)/*解决 了 m=a*b mod n;*/ { int c[MAX],d[MAX];int i;for(i=0;i d[i]=c[i]=0;mul(a,b,c); divt(c,n, d,m); for(i=0;i printf(“%d”,m[m[MAX-1]-i-1]); printf(“nm length is : %d n”,m[MAX-1]);} /*接下来的重点任务是要着手解决 m=a^p mod n的函数问题。*/ void expmod(int a[MAX] ,int p[MAX] ,int n[MAX],int *m){ int t[MAX],l[MAX],temp[MAX];/*/t放入2，l放入1；*/ int w[MAX],s[MAX],c[MAX],b[MAX],i;for(i=0;i b[i]=l[i]=t[i]=w[i]=0;t[0]=2;t[MAX-1]=1;l[0]=1;l[MAX-1]=1; mov(l,temp);mov(a,m); mov(p,b); while(cmp(b,l)!=0){ for(i=0;i divt(b,t,w,c);/*// c=p mod 2 w= p /2*/ mov(w,b);/*//p=p/2*/ if(cmp(c,l)==0)/*/余数c==1*/ { for(i=0;i mul(temp,m,w); mov(w,temp); for(i=0;i divt(temp,n,w,c);/* /c为余c=temp % n，w为商w=temp/n */ mov(c,temp);} for(i=0;i mul(m,m,s);//s=a*a for(i=0;i divt(s,n,w,c);/*/w=s/n;c=s mod n*/ mov(c,m);} for(i=0;i mul(m,temp,s); for(i=0;i divt(s,n,w,c); mov(c,m);/*余数s给m*/ m[MAX-2]=a[MAX-2];/*为后面的汉字显示需要，用第99位做为标记*/ return;/*/k=temp*k%n;*/ } int is_prime_san(int p[MAX]){ int i,a[MAX],t[MAX],s[MAX],o[MAX]; for(i=0;i s[i]=o[i]=a[i]=t[i]=0; t[0]=1; t[MAX-1]=1; a[0]=2;// { 2,3,5,7 } a[MAX-1]=1; sub(p,t,s); expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } a[0]=3; for(i=0;i expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } a[0]=5; for(i=0;i expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } a[0]=7; for(i=0;i expmod(a, s, p ,o); if(cmp(o,t)!= 0) { return 0; } return 1;} int coprime(int e[MAX],int s[MAX])/*//// 求两个大数之间是否互质////*/ { int a[MAX],b[MAX],c[MAX],d[MAX],o[MAX],l[MAX]; int i;for(i=0;i l[i]=o[i]=c[i]=d[i]=0;o[0]=0;o[MAX-1]=1;l[0]=1;l[MAX-1]=1;mov(e,b);mov(s,a);do { if(cmp(b,l)==0){ return 1;} for(i=0;i }while(cmp(c,o)!=0);/* printf(“Ihey are not coprime!n”);*/ return 0;} void prime_random(int *p,int *q){ int i,k;time_t t; p[0]=1; q[0]=3; // p[19]=1;// q[18]=2; p[MAX-1]=10; q[MAX-1]=11; do { t=time(NULL); srand((unsigned long)t);for(i=1;i k=rand()%10;} p[p[MAX-1]-1]=k; }while((is_prime_san(p))!=1); printf(“素数 p 为 : ”); for(i=0;i printf(“nn”); do { t=time(NULL); srand((unsigned long)t);for(i=1;i }while((is_prime_san(q))!=1); printf(“素数 q 为 : ”); for(i=0;i printf(“nn”);return;} void erand(int e[MAX],int m[MAX]){ int i,k;time_t t;e[MAX-1]=5;printf(“随机产生一个与(p-1)*(q-1)互素的 e :”); do { t=time(NULL); srand((unsigned long)t);for(i=0;i k=rand()%10;e[e[MAX-1]-1]=k;}while(coprime(e, m)!=1); for(i=0;i printf(“nn”);return;} void rsad(int e[MAX],int g[MAX],int *d){ int r[MAX],n1[MAX],n2[MAX],k[MAX],w[MAX];int i,t[MAX],b1[MAX],b2[MAX],temp[MAX];mov(g,n1);mov(e,n2);for(i=0;i k[i]=w[i]=r[i]=temp[i]=b1[i]=b2[i]=t[i]=0;b1[MAX-1]=0;b1[0]=0;/*/b1=0;*/ b2[MAX-1]=1;b2[0]=1;/*/b2=1;*/ while(1){ for(i=0;i k[i]=w[i]=0; divt(n1,n2,k,w);/*/k=n1/n2;*/ for(i=0;i temp[i]=0; mul(k,n2,temp);/*/temp=k*n2;*/ for(i=0;i r[i]=0; sub(n1,temp,r); if((r[MAX-1]==1)&&(r[0]==0))/*/r=0*/ { break; } else { mov(n2,n1);/*/n1=n2;*/ mov(r,n2);/*/n2=r;*/ mov(b2, t);/*/t=b2;*/ for(i=0;i temp[i]=0; mul(k,b2,temp);/*/b2=b1-k*b2;*/ for(i=0;i b2[i]=0; sub(b1,temp,b2); mov(t,b1); } } for(i=0;i t[i]=0; add(b2,g,t); for(i=0;i temp[i]=d[i]=0; divt(t,g,temp,d); printf(“由以上的(p-1)*(q-1)和 e 计算得出的 d : ”); for(i=0;i printf(“nn”);} /*/求解密密钥d的函数(根据Euclid算法)***68000*/ unsigned long rsa(unsigned long p,unsigned long q,unsigned long e)/*/求解密密钥d的函数(根据Euclid算法)*/ { unsigned long g,k,r,n1,n2,t;unsigned long b1=0,b2=1; g=(p-1)*(q-1);n1=g;n2=e; while(1){ k=n1/n2; r=n1-k*n2; if(r!=0) { n1=n2; n2=r; t=b2; b2=b1-k*b2; b1=t; } else { break; } } return(g+b2)%g;} /*/-----------导入导出公钥和私钥-----/*/ void loadpkey(int e[MAX],int n[MAX])//导入公钥 { FILE *fp;char filename[25],str[MAX],ch;int i,k;for(i=0;i e[i]=n[i]=0;while(1){ printf(“n”);printf(“为导入(e,n)，请输入加密密钥对文件路径: n”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) printf(“输入的文件不存在，请重新输入!n”); else break;} k=0; while((ch=fgetc(fp))!=EOF) { if(ch!=' ') { str[k]=ch; k++; } else { for(i=0;i { e[i]=str[k-i-1]-48; } e[MAX-1]=k; k=0; } } for(i=0;i n[i]=str[k-i-1]-48; n[MAX-1]=k; printf(“n加密密钥 e : ”); for(i=0;i printf(“%d”,e[e[MAX-1]-i-1]); printf(“n”); printf(“n 公钥 n : ”); for(i=0;i printf(“%d”,n[n[MAX-1]-i-1]); printf(“n”); fclose(fp); printf(“n导入(e,n)成功!n”); getchar();} void loadskey(int d[MAX],int n[MAX])//导入私钥 { { FILE *fp;char filename[25],str[MAX],ch;int i,k;for(i=0;i d[i]=n[i]=0;while(1){ printf(“为导入(d,n)，请输入解密密钥对文件的路径: n”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) { printf(“输入的文件不存在，请重新输入!n”); } else break;} k=0; while((ch=fgetc(fp))!=EOF) { if(ch!=' ') { str[k]=ch; k++; } else { for(i=0;i { d[i]=str[k-i-1]-48; } d[MAX-1]=k; k=0; } } for(i=0;i n[i]=str[k-i-1]-48; n[MAX-1]=k; printf(“n解密密钥 d : ”); for(i=0;i printf(“%d”,d[d[MAX-1]-i-1]); printf(“n”); printf(“n 公钥 n : ”); for(i=0;i printf(“%d”,n[n[MAX-1]-i-1]); printf(“n”); fclose(fp); printf(“n导入(d,n)成功!n”); getchar();} } void savepkey(int e[MAX],int n[MAX])//导出公钥 { FILE *fp; int i; char savefile[25],ch;printf(“导出加密密钥(e,n)，存放的文件路径为: ”); scanf(“%s”,savefile);printf(“n”); fp=fopen(savefile,“w”);for(i=0;i ch=e[e[MAX-1]-i-1]+48; fputc(ch,fp);} ch=' ';fputc(ch,fp);for(i=0;i ch=n[n[MAX-1]-i-1]+48; fputc(ch,fp);} fclose(fp);printf(“n保存(e,n)操作完成!n”);} void saveskey(int d[MAX],int n[MAX])//导出私钥 { FILE *fp; int i; char savefile[25],ch;printf(“导出解密密钥(d,n)，存放的文件路径为: ”); scanf(“%s”,savefile);printf(“n”); fp=fopen(savefile,“w”);for(i=0;i ch=d[d[MAX-1]-i-1]+48; fputc(ch,fp);} ch=' ';fputc(ch,fp);for(i=0;i ch=n[n[MAX-1]-i-1]+48; fputc(ch,fp);} fclose(fp);printf(“n保存(d,n)操作完成!n”); } /*/-----------加密和解密的块-----/*/ void printbig(struct slink *h){ struct slink *p; int i; p=(struct slink *)malloc(LEN); p=h; if(h!=NULL)do { for(i=0;i bignum[MAX-1];i++) printf(“%d”,p->bignum[p->bignum[MAX-1]-i-1]); p=p->next;} while(p!=NULL); printf(“nn”); } void tencrypto(int e[MAX], int n[MAX])/*//对有需要的文件进行加密*/ { FILE *fp; int i,k,count,temp,c; char filename[25],ch,encryfile[25]; struct slink *p,*p1,*p2; struct slink *h; h=p=p1=p2=(struct slink *)malloc(LEN); h=NULL; printf(“n输入需要加密的文件路径 : ”); scanf(“%s”,filename); if((fp=fopen(filename,“r”))==NULL) { printf(“Cannot open file!n”); exit(0); } printf(“n文件的原文内容：nn”); count=0; while((ch=fgetc(fp))!=EOF) { putchar(ch); c=ch; k=0;if(c<0){ c=abs(c);/*/把负数取正并且做一个标记*/ p1->bignum[MAX-2]='0';} else { p1->bignum[MAX-2]='1';} while(c/10!=0){ temp=c%10; c=c/10; p1->bignum[k]=temp; k++;} p1->bignum[k]=c; p1->bignum[MAX-1]=k+1;count=count+1;if(count==1) h=p1;else p2->next=p1;p2=p1; p1=(struct slink *)malloc(LEN);} p2->next=NULL; printf(“n”); fclose(fp); // printf(“加密后文件的保存路径 : n”);// scanf(“%s”,encryfile);// fp=fopen(encryfile,“w”); fp=fopen(filename,“w”); p=p1=(struct slink *)malloc(LEN); p=h; printf(“n加密后文件中所形成密文：nn”); if(h!=NULL)do { expmod(p->bignum , e ,n ,p1->bignum); ch=p1->bignum[MAX-2]; printf(“%c”,ch); fputc(ch,fp); if((p1->bignum[MAX-1]/10)==0)/*/判断p1->bignum[99]的是否大于十；*/ { ch=0+48; printf(“%c”,ch); fputc(ch,fp); ch=p1->bignum[MAX-1]+48; printf(“%c”,ch); fputc(ch,fp); } else { ch=p1->bignum[MAX-1]/10+48; printf(“%c”,ch); fputc(ch,fp); ch=p1->bignum[MAX-1]%10+48; printf(“%c”,ch); fputc(ch,fp); } for(i=0;i bignum[MAX-1];i++) { printf(“%d”,p1->bignum[i]); ch=p1->bignum[i]+48; fputc(ch,fp); } p=p->next; p1=(struct slink *)malloc(LEN);}while(p!=NULL);printf(“nn”); fclose(fp);return;} void tdecrypto(int d[MAX], int n[MAX]){ FILE *fp; struct slink *h,*p1,*p2; char ch,encryfile[25],decryfile[25]; int i,j,k,c,count,temp; printf(“n输入加密过的文件路径 : ”); scanf(“%s”,encryfile); if((fp=fopen(encryfile,“r”))==NULL) { printf(“此文件不存在!n”); exit(0); } printf(“n文件中密文内容：nn”); i=0; j=3; count=0; h=p1=p2=(struct slink *)malloc(LEN); while((ch=fgetc(fp))!=EOF) { putchar(ch); c=ch; if(j==3) { p1->bignum[MAX-2]=c; j--; } else if(j==2) { temp=c-48; j--; } else if(j==1) { p1->bignum[MAX-1]=temp*10+c-48; j--; } else if(j==0) { p1->bignum[i]=c-48; i++; if(i==p1->bignum[MAX-1]) { i=0; j=3; count++; if(count==1) h=p1; else p2->next=p1; p2=p1; p1=(struct slink *)malloc(LEN); } } } p2->next=NULL; printf(“n”); fclose(fp); // printf(“解密后的明文文件保存路径 : n”);// scanf(“%s”,decryfile);// fp=fopen(decryfile,“w”); fp=fopen(encryfile,“w”);printf(“n解密密文后文件中的明文:nn”);p2=(struct slink *)malloc(LEN); p1=h;k=0;if(h!=NULL)/*/temp为暂存ASIIC码的int值*/ do { for(i=0;i p2->bignum[i]=0; expmod(p1->bignum , d ,n ,p2->bignum); temp=p2->bignum[0]+p2->bignum[1]*10+p2->bignum[2]*100; if((p2->bignum[MAX-2])=='0') { temp=0-temp; }/*/转化为正确的ASIIC码，如-78-96形成汉字 */ ch=temp;/* str[k]--->ch */ printf(“%c”,ch);/* str[k]--->ch */ fputc(ch,fp);/*/写入文件str[k]--->ch*/ k++; p1=p1->next; p2=(struct slink *)malloc(LEN); }while(p1!=NULL); printf(“nn”); fclose(fp);return;} struct slink *input(void)/*/输入明文并且返回头指针，没有加密时候转化的数字*/ { struct slink *head; struct slink *p1,*p2; int i,n,c,temp; char ch; n=0;p1=p2=(struct slink *)malloc(LEN);head=NULL;printf(“n请输入你所要加密的内容 : n”);while((ch=getchar())!='n') { i=0;c=ch;if(c<0){ c=abs(c);/*/把负数取正并且做一个标记*/ p1->bignum[MAX-2]='0';} else { p1->bignum[MAX-2]='1';} while(c/10!=0){ temp=c%10; c=c/10; p1->bignum[i]=temp; i++;} p1->bignum[i]=c; p1->bignum[MAX-1]=i+1;n=n+1;if(n==1) head=p1;else p2->next=p1;p2=p1; p1=(struct slink *)malloc(LEN);} p2->next=NULL; return(head);} struct slink *jiami(int e[MAX],int n[MAX],struct { struct slink *p; struct slink *h; struct slink *p1,*p2; int m=0,i;printf(“n”); printf(“加密后形成的密文内容：n”);p1=p2=(struct slink*)malloc(LEN);h=NULL; p=head; if(head!=NULL)do slink *head){ expmod(p->bignum , e ,n ,p1->bignum); for(i=0;i bignum[MAX-1];i++){ printf(“%d”,p1->bignum[p1->bignum[MAX-1]-1-i]);} m=m+1;if(m==1) h=p1;else p2->next=p1;p2=p1; p1=(struct slink *)malloc(LEN); p=p->next;} while(p!=NULL);p2->next=NULL; p=h; printf(“n”); return(h); } void jiemi(int d[MAX],int n[MAX],struct slink *h){ int i,j,temp; struct slink *p,*p1; char ch[65535]; p1=(struct slink*)malloc(LEN); p=h; j=0; if(h!=NULL) do { for(i=0;i p1->bignum[i]=0; expmod(p->bignum , d ,n ,p1->bignum); temp=p1->bignum[0]+p1->bignum[1]*10+p1->bignum[2]*100; if((p1->bignum[MAX-2])=='0') { temp=0-temp; } ch[j]=temp; j++; p=p->next;}while(p!=NULL);printf(“n”);printf(“解密密文后所生成的明文:n”);for(i=0;i printf(“%c”,ch[i]);printf(“n”);return; } void menu(){ printf(“nnn”);printf(“nnn”);printf(“ R--------产生密钥对 nnn”); printf(“ S--------保存密钥对 nnn”);printf(“ L--------载入密钥对 nnn”);printf(“ E--------对文件加密 nnn”);printf(“ D--------对文件解密 nnn”);printf(“ T--------简单测试 nnn”);printf(“ Q--------退出 nnn”);printf(“请选择一种操作：”);} /*/------------------主MAIN函数----/*/ void main(){ int i; char c; int p[MAX],q[MAX],n[MAX],d[MAX],e[MAX],m[MAX],p1[MAX],q1[MAX];struct slink *head,*h1,*h2; for(i=0;i m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0;/*/简单初始化一下*/ while(1) { menu(); c=getchar(); getchar();//接受回车符 if((c=='r')||(c=='R'))//操作r产生密钥对 { for(i=0;i m[i]=p[i]=q[i]=n[i]=d[i]=e[i]=0; printf(“nnnnnnnnn”); printf(“nn随机密钥对产生如下：nn”); prime_random(p,q);/*/随机产生两个大素数*/ mul(p,q,n); printf(“由 p、q 得出 n :”); print(n); mov(p,p1); p1[0]--; mov(q,q1); q1[0]--; /*/q-1;*/ mul(p1,q1,m);//m=(p-1)*(q-1) erand(e,m); rsad(e,m,d); printf(“密钥对产生完成，现在可以直接进行加解密文件!n”); printf(“n按任意键回主菜单…………”); getchar();} else if((c=='l')||(c=='L')) { printf(“nn选择导入密钥类型：加密密钥(P)还是解密密钥(S)?”); c=getchar(); getchar(); if((c=='p')||(c=='P')) loadpkey(e,n); else if((c=='s')||(c=='S')) loadskey(d,n); printf(“n按任意键回主菜单…………”); getchar(); } else if((c=='e')||(c=='E')) { tencrypto(e, n); printf(“n加密文件操作完成!n”); printf(“n按任意键回主菜单…………”); getchar(); getchar(); } else if((c=='d')||(c=='D')) { tdecrypto(d, n); printf(“n解密文件操作完成!n”); printf(“n按任意键回主菜单…………”); getchar(); getchar(); } else if((c=='s')||(c=='S')) { savepkey(e,n); printf(“n”); saveskey(d,n); printf(“n按任意键回主菜单…………”); getchar(); getchar(); } else if((c=='T')||(c=='t')) { head=input(); h1=jiami(e, n, head); jiemi(d, n, h1); printf(“nRSA测试工作完成!n”); printf(“n按任意键回主菜单…………”); getchar(); } else if((c=='Q')||(c=='q')) break; } } #include #include #include //将十进制数转换成二进制，用于检验大素数p和q int zhuan_huan(int b,int a[],int k) { int t,temp=-1; while(b>0){ t=b%2; temp++; a[temp]=t; b=b/2; } return temp; } //欧几里得算法，用于判断加密指数e是否符合要求 int gcd(int n,int b) { int r1=n,r2=b,r; while(r2>0){ r=r1%r2; r1=r2; r2=r; } return r1; } //扩展欧几里得算法求乘法逆元，即求解密指数d int extend(int n,int b) { int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1; while(r2>0) { q=r1/r2; r=r1%r2; r1=r2;r2=r; t=t1-q*t2; t1=t2; t2=t; } if(t1>=0)return t1%n; else{ while((t1+i*n)<0) i++; return t1+i*n; } } //检验大素数，符合要求返回1，否则返回0 int Witness(int a,int n) { int d=1,k,r=n-1,i,x,b[1000]; k=zhuan_huan(r,b,1000); for(i=k;i>=0;i--){ x=d; d=(d*d)%n; if((d==1)&&(x!=1)&&(x!=n-1))return 0; if(b[i]==1)d=(d*a)%n; } if(d!=1)return 0; else return 1; } //快速计算模指数 int js_mod(int a,int b,int n) { int x=0,y=1,k,i,s[1000]; k=zhuan_huan(b,s,1000); for(i=k;i>=0;i--){ x=2*x; y=(y*y)%n; if(s[i]==1){ x++; y=(y*a)%n; } } return y; } //主函数。。。。。。。。。。。。。。。。。。。。。。 void main() { int p,q,e,d,n,yn,m[1000],c[10000];//c[10000]存放加密后的数字密文，m[1000]存放解密后的数字明文，即英文明文在zimu_biao[69]中的下标。 int i,j;//i,j用于循环遍历数组 int mi_yue;//用户输入的密钥 int count=1;//统计输入密钥的次数，count>3时将不允许用户再输入。 char min_wen[1000],re_min_wen[1000];//分别为用户输入的明文、密文，解密后的明文。//密钥生成char zimu_biao[69]=“abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789'.?!”; printf(“请输入您要发送的明文文件（小写英文表示）:n”); printf(“******************************************************n”); gets(min_wen); printf(“******************************************************n”); printf(“n加密开始，请按要求操作。。nn”); printf(“请输入第一个大素数p：n”); while(1){ scanf(“%d”,&p); if(Witness(2,p)==1){ printf(“您输入的第一个大素数 %d 符合要求n”,p); break; } else printf(“您输入的 %d 不是素数,请重新输入：n”,p); } printf(“请输入第二个大素数q：n”); while(1){ scanf(“%d”,&q); if(Witness(2,q)){ printf(“您输入的第二个大素数 %d 符合要求n”,q); break; } else printf(“您输入的 %d 不是素数,请重新输入：n”,q); } n=p*q;yn=(p-1)*(q-1); printf(“请输入加密指数（整数）e,且0 scanf(“%d”,&e); if(gcd(yn,e)==1){ printf(“您输入加密指数 %d 与 %d 互素,符合要求n”,e,yn); break; } else printf(“您输入加密指数 %d 与 %d 不互素,请重新输入。。n”,e,yn); } d=extend(yn,e);//求解密指数d printf(“nn请记住您的两个大素数分别为p=%d(保密),q=%d(保密),模数n=%d(公开),欧拉函数yn=%d(保密),加密指数e=%d(公钥,公开),。。解密指数 d=%d(私钥,保密)nn”,p,q,n,yn,e,d); //明文转换过程 /* scanf(“%s”,min_wen); printf(“%s”,min_wen);*/ for(i=0;i for(j=0;j<68;j++)//for(j=0;j<26;j++) if(min_wen[i]==zimu_biao[j]) m[i]=j;//将字符串明文换成数字，并存到整型数组m里面，即明文的另一种表示方法 //加密过程 for(i=0;i c[i]=js_mod(m[i],e,n); printf(“输出密文：n”); printf(“******************************************************n”); for(i=0;i printf(“%d”,c[i]); printf(“n******************************************************n”); //解密过程 for(i=0;i m[i]=js_mod(c[i],d,n); for(i=0;i re_min_wen[i]=zimu_biao[m[i]]; //提示用户解密 printf(“nn您有3次输入密钥的机会，密钥正确后将进行解密显示明文，3次输入错误解密将终止，请注意。。nn”); while(1){ scanf(“%d”,&mi_yue); if(mi_yue==d){ printf(“密钥输入正确，您得到的明文为：nn”); for(i=0;i printf(“%c”,re_min_wen[i]); printf(“nn”); break; } else{ }} }}printf(“您第%d次输入的密钥错误，请重新输入。。n”,count);count++;if(count>3){printf(“n您已%d次输入的密钥错误，将不允许继续输入n”,count-1);break; C 语 言 课 程 设 计 实 验 报 告 实验名称：文件加密解密 院系：软件学院 学号： 年9月3日—9月17日 日期：2012 一：设计题目 1：设计图形用户界面。 2：对文件进行加密并对加密文件进行保存。3：对加密了的文件进行解密。 二：设计过程 设计过程中遇到的困难和解决方法： 1：不能很好地理解题意（通过老师的讲解）。 2：不知道如何设计加密解密程序（通过翻阅书籍和上网查找资料）过程： 首先通过学习老师提供的资料了解大致的设计过程并懂得运用一些以前没有学习过的c语言。先利用文本文件设计出加密解密的主要过程并能运行。知道如何运用fopen将原文件打开并用fread将原文件内容读出来，然后进行加密设计并将加密的数据用fwrite写进指定的文件中并保存。然后读出加密的文件并解密并保存。最后在写出的程序中加入图形用户界面，运用window，box，gotoxy等进行设计。 三：源代码 #include ///////////////////////////////////////////////////////////////加密解密 */ void fun(char *list,char *sd)/*加密过程*/ { FILE *fp1,*fp2;char buf[1000];/*文件临时存放处*/ register int ch;fp1=fopen(“e:list.txt”,“r”);/*用可读方式打开文件*/ fp2=fopen(“e:sd.txt”,“w”);/*用可写方式创建一个文件*/ if(fp1==NULL){ printf(“cannot open filen”);exit(1);} if(fp2==NULL){ printf(“cannot build filen”);exit(1);} ch=fgetc(fp1);/*读出打开文件的光标处的一个字符*/ while(!feof(fp1))/*读出的字符不是最后的字符*/ { ch=ch<<1;/*加密方法*/ fputc(ch,fp2);/*加密的字符存放在指定的地方*/ ch=fgetc(fp1); } rewind(fp2);/*将光标移动到第一个字符前面*/ fread(buf,sizeof(buf),1,fp2);/*从文件的当前位置开始中读取buf中存放的数据*/ printf(“%s”,buf);/*fclose(fp1);fclose(fp2);*/ } void man(char *sd,char *ds)/*解密过程*/ { /*int n=0;*/ FILE *fp2,*fp3;register int fh;char buf1[1000]; fp2=fopen(“e:sd.txt”,“rb”);/*用可读方式打开文件*/ fp3=fopen(“e:ds.txt”,“wb”);/*用可写方式创建一文件*/ if(fp2==NULL){ printf(“cannot open filen”);exit(1);} if(fp3==NULL){ printf(“cannot build filen”);exit(1);} fh=fgetc(fp2);/*从光标处读出一个字符*/ while(!feof(fp2))/*当读出的字符到达最后一个则停止*/ { fh=fh>>1;/*解密方式*/ fputc(fh,fp3);/*解密的字符存放在指定的地方*/ fh=fgetc(fp2);} fread(buf1,sizeof(buf1),1,fp3);/*读出buf1中所存放的数据*/ printf(“%s”,buf1);} void main(){ int k;char *f[]={“jiami”,“jiemi”};/**界面的形式/ int key,y;int j,q;char list[300];char sd[300];char ds[300];char ch,fh;char buf[1000];char buf1[1000];FILE *fp1;FILE *fp2;int l1,l2;window(1,1,80,25);/*left,top,right,bottom,相对于屏幕的字符坐标，屏幕原点在左上角*/ gettext(20,10,40,14,buf);/*保存矩形屏幕上的字符*/ textbackground(7);/*背景颜色*/ textcolor(0);/*字体颜色*/ clrscr();/*清除矩形屏幕上的所有字符*/ gotoxy(24,10);/*将当前字符屏幕的光标位置移动到x,y的坐标位子*/ printf(“%s”,f[0]);gotoxy(24,14);printf(“%s”,f[1]);gettext(10,8,60,16,buf);box(22,9,3,30);/*建立一个小窗口*/ key=0;while(1){ while(bioskey(1)==0);/*读取键盘值查询键盘是否按下*/ key=get_key();/*按下了什么键盘*/ if(key==key_up||key==key_down){ y=wherey();/*得到字符模式下窗口光标的x坐标数值*/ if(key==key_up)y=y==10? y+4:10;/*当y=10光标向下移动四个位置否则将光标移动到y=10处*/ if(key==key_down)y=y==14? y-4:14;/*当y=14光标向下移动四个位置否则将光标移动到y=14处*/ puttext(10,8,60,16,buf);/*将gettext函数保存的字符恢复到屏幕上 */ gotoxy(24,y); if(y==10){ textbackground(7);textcolor(0);box(22,9,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[0]);} else { textbackground(7);textcolor(0);box(22,13,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[1]);} } if(key==key_enter&&y==10)且光标在y=10处 /*当按下enter键且光标在y=10处进行下步*/ { clrscr();textbackground(3);textcolor(15);/*clrscr();*/ gotoxy(24,5);printf(“input the file name for jiamin”);/*用户给需要加密的文件加密 */ l1=strlen(“input the file name for jiami:”);/*待求长度的字符串指针*/ gotoxy(24+l1,5);scanf(“%s”,list);gotoxy(24,10);printf(“input file name for saven”);/*给加密后的文件命名，并保存*/ l2=strlen(“input file name for save:”);gotoxy(24+l2,10);scanf(“%s”,sd);fun(list,sd);fp1=fopen(“e:sd.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp1);gotoxy(10,15);printf(“%sn”,buf1);getch();printf(“file haven jiami ,save now”);getche();break;} if(key==key_enter&&y==14){ clrscr();textbackground(3);textcolor(15);gotoxy(24,5); printf(“input the file name for jiemi n”);/*用户给需要解密的文件解密 */ l1=strlen(“input the file name for jiemi: ”);gotoxy(24+l1,5);scanf(“%s”,sd);gotoxy(24,10);printf(“input file name for save：n”);/*对解密的文件系统又可以提供保存路径 */ l2=strlen(“input file name for save: ”);gotoxy(24+l2,10);scanf(“%s”,ds);man(sd,ds);fp2=fopen(“e:ds.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp2);gotoxy(10,15);printf(“%sn”,buf1);getch(); printf(“file haven jiemi,save now”);getche();break;} } window(1,1,80,25);gettext(20,10,40,14,buf); textbackground(7);textcolor(0);clrscr();gotoxy(24,10);printf(“%s”,f[0]);gotoxy(24,14);printf(“%s”,f[1]);gettext(10,8,60,16,buf);box(22,9,3,30);key=0;while(1){ while(bioskey(1)==0);key=get_key(); if(key==key_up||key==key_down){ y=wherey();if(key==key_up)y=y==10? y+4:10;if(key==key_down)y=y==14? y-4:14;puttext(10,8,60,16,buf); gotoxy(24,y); if(y==10)/*光标在10处的窗口*/ { textbackground(7);textcolor(0);box(22,9,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[0]);} else { textbackground(7);textcolor(0);box(22,13,3,30);textbackground(3);textcolor(15);gotoxy(24,y);cprintf(“%s”,f[1]);} } if(key==key_enter&&y==10){ clrscr();textbackground(3);textcolor(15);/*clrscr();*/ gotoxy(24,5);printf(“input the file name for jiamin”);/*用户给需要加密的文件加密 */ l1=strlen(“input the file name for jiami:”);gotoxy(24+l1,5);scanf(“%s”,list);gotoxy(24,10);printf(“input file name for saven”);/*给加密后的文件命名，并保存*/ l2=strlen(“input file name for save:”);gotoxy(24+l2,10);scanf(“%s”,sd);fun(list,sd);fp1=fopen(“e:sd.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp1);gotoxy(10,15);printf(“%sn”,buf1);getch();printf(“file haven jiami ,save now”);getche();} if(key==key_enter&&y==14){ clrscr();textbackground(3);textcolor(15);gotoxy(24,5); printf(“input the file name for jiemi n”);/*用户给需要解密的文件解密 */ l1=strlen(“input the file name for jiemi: ”);gotoxy(24+l1,5);scanf(“%s”,sd);gotoxy(24,10);printf(“input file name for save：n”);/*对解密的文件系统又可以提供保存路径 */ l2=strlen(“input file name for save: ”);gotoxy(24+l2,10);scanf(“%s”,ds);man(sd,ds);fp2=fopen(“e:ds.txt”,“rb”);fread(buf1,sizeof(buf1),1,fp2);gotoxy(10,15);printf(“%sn”,buf1);getch(); printf(“file haven jiemi,save now”);getche();break;} } } int get_key(){ union REGS rg;rg.h.ah=0;int86(0x16,&rg,&rg);return rg.h.ah;getchar();} void box(int startx,int starty,int high,int width)/*的建立*/ { int i;gotoxy(startx,starty);putch(0xda);for(i=startx+1;i for(i=starty+1;i 屏幕 } gotoxy(startx,starty+high-1);putch(0xc0);gotoxy(startx+1,starty+high-1);for(i=startx+1;i 通过这次的作业我觉得最大的收获是不仅把平时学习到的知识理解的更加透彻，而且使知识更加系统化，同时还把有些平时不太注意的小问题发现了出来，这不但有利于我学习C语言，而且对于我学习任何一门课程都是很有益处的。总之，做这份作业对于我们学习C语言有很大的帮助。 在做课程设计时，由于运用了很多新知识，新的方法，还有题目更加复杂，应用性更强，在编写过程中遇到了很多困难，从而使自己能够学习到更多以前不懂，难懂的东西。 信息安全实验报告 题 目 RSA算法 姓 名 学 号 专业年级 计算机科学与技术2014级（1）班 指导教师 2016年 12 月 10日 一、实验目的 了解非对称加密机制 理解RSA算法的加解密原理 熟悉Java的学习以及运用Java实现RSA算法的加解密过程 二、实验背景 钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的这么多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。 三、实验原理 1.非对称密钥加解密概述 使用对称密钥加密体制进行保密通信时，任意不同的两个用户之间都应该使用互不相同的密钥。这样，如果一个网络中有n个用户，他们之间彼此都可能进行秘密通信，这时网络中将需要n(n-1)/2个密钥(其中，每个用户都需要保存n-1个密钥)，这样巨大的密钥量给密钥分配和管理带来了极大的困难。另外，随着计算机网络，特别是因特网的发展，网络上互不相识的用户可能需要进行保密的会话(例如，如果用户在进行电子商务活动时，需要保密的连接，这时的客户对象可能根本不是固定的对象)。最后，对称密钥加密机制难以解决签名验证问题。 非对称密钥加密也称为公开密钥加密，或者叫做公钥加密算法。使用公开密钥密码的每一个用户都分别拥有两个密钥：加密密钥和解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算机上是不可行的。每一个用户的加密密钥都是公开的。因此，加密密钥也称为公开密钥。所有用户的公开密钥都将记录在作用类似于电话号码薄的密钥本上，而它可以被所有用户访问，这样每一个用户都可以得到其他所有用户的公开密钥。同时，每一个用户的解密密钥将由用户保存并严格保密。因此，解密密钥也称为私有密钥。 非对称密码算法解决了对称密码体制中密钥管理的难题，并提供了对信息发送人的身份进行验证的手段，是现代密码学最重要的发明。公钥加密算法一般是将对密钥的求解转化为对数学上的困难问题的求解，例如RSA算法的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，已知两个大素数a和b，求出a*b是容易计算的，而已知a*b，想知道其是哪两个大素数的乘积目前还没有好的计算方法，另外也有一些非对称加密算法(如ELGamal算法)的安全性是基于求“离散对数”这个数学难题上的。 在公钥密码系统中每个实体都有自己的公钥和相应的私钥。公钥密码系统的加密变换和解密变换分别用E和D表示。任何实体B要向实体A发送信息m的步骤如下：实体B首先获得实体A的真实公钥的拷贝(eA)，实体B使用eA计算密文c=E(m)并发送给实体A，实体A使用自己的私钥dA，计算m=D(c)解密密文，恢复出明文m。这里公钥不需要保密，但要保证它的真实性，即eA确实是实体A掌握的私钥dA所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这也是公钥密码系统的主要优点之一。 公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(data origin authentication)和数据完整性(data integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输后存储没有发生改变。数据源认证和数据完整性要由其他技术来提供(如消息认证码技术、数字签名技术等)。 从本质上来看，公钥密码比对称密钥密码加密的速度要慢，粗略的说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。 公钥解密也可以提供认证保证(如：在实体认证协议、带认证的密钥建立协议等)。公钥加密中必须有颁发让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。 2.公钥加解密的优缺点： 1)大型网络中的每个用户需要的密钥数量少。 2)对管理公钥的可信第三方的信任程度要求不高而且是离线的。3)只有私钥是保密的，而公钥只要保证它的真实性。4)多数公钥加密比对称密钥加密的速度要慢几个数量级。5)公钥加密方案的密钥长度比对称加密的密钥要长。6)公钥加密方案没有被证明是安全的。 公钥密码的概念本身就被公认为是密码学上的一块里程碑。三十多年来的研究表明，公钥密码成功地解决了计算机网络安全中的密钥管理，身份认证和数字签名等问题，已经成为信息安全技术中的重大核心技术。 四、RSA算法 1.概述 RSA加密算法于1977年由美国麻省理工学院的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adleman命名为RSA算法。这三位科学家荣获2002图灵奖，以表彰他们在算法方面的突出贡献。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数的乘积却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。它无须收发双方同时参与加密过程，既可以用于保密也可以用于签名，因而非常适合于电子邮件系统的加密，互连网和信用卡安全系统。 算法概述：找两素数p和q，取n=p*q，取t=(p-1)*(q-1)，取任何一个数e，要求满足e 2.算法设计 1)publicstaticvoid GetPrime()说明：利用Java语言的中的java.math.BigInteger类的方法中随机产生大数。 2)public static boolean MillerRobin(BigInteger num)参数说明：num是由GetPrime方法产生的大数。 说明：这个方法判断GetPrime方法传过来的是否是一个素数，是就返回true,否就返回false。 3)public static BigInteger powmod(BigIntegera，BigIntegert，BigInteger num)说明：这个方法对传入的大数进行幂运算。 4)public static BigInteger invmod(BigInteger a，BigInteger b)说明：这个方法对大数进行取模运算。 5)public static String Encode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextFieldd)方法名称：加密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。d为公钥。 6)publicstatic String Decode(String inStr，BigInteger PrimeP，BigInteger PrimeQ，BigInteger n，int nLen，int m，JTextField e)方法名称：解密算法。参数说明： inStr是从界面输入的明文。 PrimeP和PrimeQ是由GetPrime方法产生的两个大素数。n是由PrimeP和PrimeQ得到的值。nLen为n的长度。e为私钥。 在对称加密中：n，d两个数构成公钥，可以告诉别人；n，e两个数构成私钥，e自己保留，不让任何人知道。给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。 RSA的安全性在于对于一个大数n，没有有效的方法能够将其分解从而在已知n，d的情况下无法获得e；同样在已知n，e的情况下无法求得d。 五、实验结果 实验结果如下图所示： 六、实验总结 本次实验对输入的任意一段明文字母，实现了输出对应密钥的密文字母。亲手实际编写RSA密码算法代码，更好的了解和掌握了RSA的相关内容。通过用Java对RSA密码体制进行编程，对RSA密码体制的加解密过程有了更深入的理解。通过这个实验更是让我获得了很多实际工作中所要具备的能力。 七、代码附录 略 C语言常用算法归纳 应当掌握的一般算法 一、基本算法： 交换、累加、累乘 二、非数值计算常用经典算法： 穷举、排序（冒泡，选择）、查找（顺序即线性） 三、数值计算常用经典算法： 级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法） 四、其他： 迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形） 详细讲解 一、基本算法 1．交换（两量交换借助第三者） 例 1、任意读入两个整数，将二者的值交换后输出。main(){ int a,b,t; scanf(“%d%d”,&a,&b); printf(“%d,%dn”,a,b);t=a;a=b;b=t; printf(“%d,%dn”,a,b);} 1 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例 2、任意读入三个整数，然后按从小到大的顺序输出。main(){ int a,b,c,t;scanf(“%d%d%d”,&a,&b,&c);/*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a;a=b;b=t;} if(a>c){ t=a;a=c;c=t;} /*以下if语句使得b中存放的数次小*/ if(b>c){ t=b;b=c;c=t;} printf(“%d,%d,%dn”,a,b,c);} 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 例 1、求1+2+3+……+100的和。main(){ int i,s;s=0;i=1;while(i<=100){ s=s+i;/*累加式*/ i=i+1;/*特殊的累加式*/ } printf(“1+2+3+...+100=%dn”,s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 3．累乘 累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。 例 1、求10！ [分析] 10！=1×2×3×……×10 main(){ int i;long c;c=1;i=1;while(i<=10){ c=c*i;/*累乘式*/ i=i+1;} printf(“1*2*3*...*10=%ldn”,c);} 二、非数值计算常用经典算法 1．穷举 也称为“枚举法”，即将可能出现的每一种情况一一测试，判断是否满足条件，一般采用循环来实现。 例 1、用穷举法输出所有的水仙花数（即这样的三位正整数：其每位数位上的数字的立方和与该数相等，比如：1*1*1+5*5*5+3*3*3=153）。 [法一] main(){ int x,g,s,b;for(x=100;x<=999;x++){ g=x%10;s=x/10%10;b=x/100; if(b*b*b+s*s*s+g*g*g==x)printf(“%dn”,x);} } 【解析】此方法是将100到999所有的三位正整数一一考察，即将每一个三位正整数的个位数、十位数、百位数一一求出（各数位上的数字的提取算法见下面的“数字处理”），算出三者的立方和，一旦与原数相等就输出。共考虑了900个三位正整数。 [法二] main(){int g,s,b;for(b=1;b<=9;b++)for(s=0;s<=9;s++)for(g=0;g<=9;g++) if(b*b*b+s*s*s+g*g*g==b*100+s*10+g)printf(“%dn”,b*100+s*10+g);} 【解析】此方法是用1到9做百位数字、0到9做十位和个位数字，将组成的三位正整数与每一组的三个数的立方和进行比较，一旦相等就输出。共考虑了900个组合（外循环单独执行的次数为9，两个内循环单独执行的次数分别为10次，故if语句被执行的次数为9×10×10=900），即900个三位正整数。与法一判断的次数一样。 2．排序 （1）冒泡排序（起泡排序） 假设要对含有n个数的序列进行升序排列，冒泡排序算法步骤是： ①从存放序列的数组中的第一个元素开始到最后一个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置； ②第①趟结束后，最大数就存放到数组的最后一个元素里了，然后从第一个元素开始到倒数第二个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置； ③重复步骤①n-1趟，每趟比前一趟少比较一次，即可完成所求。例 1、任意读入10个整数，将其用冒泡法按升序排列后输出。#define n 10 main(){ int a[n],i,j,t;for(i=0;i scanf(“%d”,&a[i]);for(j=1;j<=n-1;j++) /*n个数处理n-1趟*/ for(i=0;i<=n-1-j;i++)/*每趟比前一趟少比较一次*/ if(a[i]>a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;} for(i=0;i （2）选择法排序 选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是： ①从数组存放的n个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置； ②除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置； ③重复步骤①n-1趟，即可完成所求。 例 1、任意读入10个整数，将其用选择法按升序排列后输出。#define n 10 main(){ int a[n],i,j,k,t;for(i=0;i if(a[j] < a[k])k = j; if(k!= i){ t = a[i];a[i] = a[k];a[k] = t;} } for(i=0;i printf(“%dn”,a[i]);} （3）插入法排序 要想很好地掌握此算法，先请了解“有序序列的插入算法”，就是将某数据插入到一个有序序列后，该序列仍然有序。插入算法参见下面的“数组元素的插入”。 例 1、将任意读入的整数x插入一升序数列后，数列仍按升序排列。#define n 10 main(){ int a[n]={-1,3,6,9,13,22,27,32,49},x,j,k; /*注意留一个空间给待插数*/ scanf(“%d”,&x);if(x>a[n-2])a[n-1]=x; /*比最后一个数还大就往最后一个元素中存放*/ else /*查找待插位置*/ { j=0; while(j<=n-2 && x>a[j])j++; for(k=n-2;k>=j;k--)/*从最后一个数开始直到待插位置上的数依次后移一位*/ a[k+1]=a[k]; a[j]=x; /*插入待插数*/ } for(j=0;j<=n-1;j++)printf(“%d ”,a[j]);} 插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。 例 2、任意读入10个整数，将其用插入法按降序排列后输出。（提示：将第2至第10个数一一有序插入到数组a中）#define n 10 main(){ int a[n],i,j,k,x;scanf(“%d”,&a[0]);/*读入第一个数，直接存到a[0]中*/ for(j=1;j { scanf(“%d”,&x); if(x else /*以下查找待插位置*/ { i=0; while(x /*以下for循环从原最后一个数开始直到待插位置上的数依次后移一位*/ for(k=j-1;k>=i;k--)a[k+1]=a[k]; a[i]=x;/*插入待插数*/ } } for(i=0;i （4）归并排序 即将两个都升序（或降序）排列的数据序列合并成一个仍按原序排列的序列。 例 1、有一个含有6个数据的升序序列和一个含有4个数据的升序序列，将二者合并成一个含有10个数据的升序序列。 #define m 6 #define n 4 main(){ int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22};int i,j,k,c[m+n];i=j=k=0;while(i /*将a、b数组中的较小数依次存放到c数组中*/ { if(a[i] else {c[k]=b[j];j++;} k++;} while(i>=m && j （1）顺序查找（即线性查找）顺序查找的思路是：将待查找的量与数组中的每一个元素进行比较，若有一个元素与之相等则找到；若没有一个元素与之相等则找不到。 例 1、任意读入10个数存放到数组a中，然后读入待查找数值，存放到x中，判断a中有无与x等值的数。 #define N 10 main(){ int a[N],i,x;for(i=0;i （2）折半查找（即二分法） 顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数列必须有序。 二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值为止。 例 1、任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。#define n 10 main(){ int a[n]={2,4,7,9,12,25,36,50,77,90};int x,high,low,mid;/*x为关键值*/ scanf(“%d”,&x);high=n-1;low=0;mid=(high+low)/2;while(a[mid]!=x&&low else low=mid+1;/*修改区间下界*/ mid=(high+low)/2;} if(x==a[mid])printf(“Found %d,%dn”,x,mid);else printf(“Not foundn”);} 三、数值计算常用经典算法 1．级数计算 级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法又称递推法。 直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个（或多个）通项写出后一个通项。 可以用直接法描述通项的级数计算例子有：（1）1+2+3+4+5+…… （2）1+1/2+1/3+1/4+1/5+……等等。 可以用间接法描述通项的级数计算例子有：（1）1+1/2+2/3+3/5+5/8+8/13+……（2）1+1/2!+1/3!+1/4!+1/5!+……等等。（1）直接法求通项 例 1、求1+1/2+1/3+1/4+1/5+……+1/100的和。main(){ float s;int i;s=0.0;for(i=1;i<=100;i++)s=s+1.0/i;printf(“1+1/2+1/3+...+1/100=%fn”,s);} 【解析】程序中加粗部分就是利用项次i的倒数直接描述出每一项，并进行累加。注意：因为i是整数，故分子必须写成1.0的形式！ （2）间接法求通项（即递推法） 例 2、计算下列式子前20项的和：1+1/2+2/3+3/5+5/8+8/13+……。[分析]此题后项的分子是前项的分母，后项的分母是前项分子分母之和。main(){ float s,fz,fm,t,fz1;int i;s=1;/*先将第一项的值赋给累加器s*/ fz=1;fm=2;t=fz/fm;/*将待加的第二项存入t中*/ for(i=2;i<=20;i++){ s=s+t; /*以下求下一项的分子分母*/ fz1=fz;/*将前项分子值保存到fz1中*/ fz=fm;/*后项分子等于前项分母*/ fm=fz1+fm;/*后项分母等于前项分子、分母之和*/ t=fz/fm;} printf(“1+1/2+2/3+...=%fn”,s);} 下面举一个通项的一部分用直接法描述，另一部分用递推法描述的级数计算的例子： 例 3、计算级#include 数的值，当通项的绝对值小于eps时计算停止。 { float x,eps;scanf(“%f%f”,&x,&eps);printf(“n%f,%fn”,x,g(x,eps));} float g(float x,float eps){ int n=1;float s,t;s=1;t=1;do { t=t*x/(2*n); s=s+(n*n+1)*t;/*加波浪线的部分为直接法描述部分，t为递推法描述部分*/ n++;}while(fabs(t)>eps);return s;} 2．一元非线性方程求根 （1）牛顿迭代法 牛顿迭代法又称牛顿切线法：先任意设定一个与真实的根接近的值x0作为第一次近似根，由x0求出f(x0),过(x0，f(x0))点做f(x)的切线，交x轴于x1，把它作为第二次近似根，再由x1求出f(x1),过(x1，f(x1))点做f(x)的切线，交x轴于x2，……如此继续下去，直到足够接近（比如|x-x0|<1e-6时）真正的根x*为止。 而f '(x0)=f(x0)/(x1-x0)所以 x1= x0-f(x0)/ f '(x0) 例如，用牛顿迭代法求下列方程在1.5附近的根：2x3-4x2+3x-6=0。#include “math.h” main(){ float x,x0,f,f1;x=1.5;do{ x0=x; f=2*x0*x0*x0-4*x0*x0+3*x0-6; f1=6*x0*x0-8*x0+3; x=x0-f/f1;}while(fabs(x-x0)>=1e-5);printf(“%fn”,x);} （2）二分法 算法要领是：先指定一个区间[x1, x2]，如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和 f(x2)是否同号来确定方程f(x)=0在区间[x1, x2]内是否有一个实根；如果f(x1)和 f(x2)同号，则f(x)在区间[x1, x2]内无实根，要重新改变x1和x2的值。当确定f(x)在区间[x1, x2]内有一个实根后，可采取二分法将[x1, x2]一分为二，再判断在哪一个小区间中有实根。如此不断进行下去，直到小区间足够小为止。 具体算法如下： （1）输入x1和x2的值。（2）求f(x1)和f(x2)。 （3）如果f(x1)和f(x2)同号说明在[x1, x2] 内无实根，返回步骤（1），重新输入x1和x2的值；若f(x1)和f(x2)不同号，则在区间[x1, x2]内必有一个实根，执行步骤（4）。（4）求x1和x2的中点：x0=（x1+ x2）/2。（5）求f(x0)。 （6）判断f(x0)与f(x1)是否同号。 ①如果同号，则应在[x0, x2]中寻找根，此时x1已不起作用，用x0代替x1，用f(x0)代替f(x1)。 ②如果不同号，则应在[x1, x0]中寻找根，此时x2已不起作用，用x0代替x2，用f(x0)代替f(x2)。 （7）判断f(x0)的绝对值是否小于某一指定的值（例如10-5）。若不小于10-5，则返回步骤（4）重复执行步骤（4）、（5）、（6）；否则执行步骤（8）。（8）输出x0的值，它就是所求出的近似根。 例如，用二分法求方程2x3-4x2+3x-6=0在(-10，10)之间的根。#include “math.h” main(){ float x1,x2,x0,fx1,fx2,fx0;do { printf(“Enter x1&x2”); scanf(“%f%f”,&x1,&x2); fx1=2*x1*x1*x1-4*x1*x1+3*x1-6; fx2=2*x2*x2*x2-4*x2*x2+3*x2-6; }while(fx1*fx2>0);do { x0=(x1+x2)/2; fx0=2*x0*x0*x0-4*x0*x0+3*x0-6; if((fx0*fx1)<0){ x2=x0;fx2=fx0;} else {x1=x0;fx1=fx0;} }while(fabs(fx0)>1e-5);printf(“%fn”,x0);} 3．梯形法计算定积分 定积分 的几何意义是求曲线y=f(x)、x=a、x=b以及x轴所围成的面积。 可以近似地把面积视为若干小的梯形面积之和。例如，把区间[a, b]分成n个长度相等的小区间，每个小区间的长度为h=(b-a)/n，第i个小梯形的面积为[f(a+(i-1)·h)+f(a+i·h)]·h/2，将n个小梯形面积加起来就得到定积分的近似值： 根据以上分析，给出“梯形法”求定积分的N-S结构图： 输入区间端点：a，b 输入等分数n h=(b-a)/2, s=0 i从1到n si=(f(a+(i-1)*h)+f(a+i*h))*h/2 s=s+si 输出s 11 上述程序的几何意义比较明显，容易理解。但是其中存在重复计算，每次循环都要计算小梯形的上、下底。其实，前一个小梯形的下底就是后一个小梯形的上底，完全不必重复计算。为此做出如下改进： 矩形法求定积分则更简单，就是将等分出来的图形当作矩形，而不是梯形。例如：求定积分的值。等分数n=1000。 #include “math.h” float DJF(float a,float b){ float t,h;int n,i;float HSZ(float x);n=1000;h=fabs(a-b)/n;t=(HSZ(a)+HSZ(b))/2;for(i=1;i<=n-1;i++)t=t+HSZ(a+i*h);t=t*h;return(t);} float HSZ(float x){ return(x*x+3*x+2);} main(){ float y;y=DJF(0,4); printf(“%fn”,y);} 四、其他常见算法 1．迭代法 其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。每次重复都从旧值的基础上递推出新值，并由新值代替旧值。 例如，猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，就只剩一个桃子了。编程求第一天共摘多少桃子。 main(){ int day,peach;peach=1;for(day=9;day>=1;day--)peach=(peach+1)*2;printf(“The first day:%dn”,peach);} 又如，用迭代法求x= 的根。 求平方根的迭代公式是：xn+1=0.5×(xn+a/ xn)[算法]（1）设定一个初值x0。 （2）用上述公式求出下一个值x1。 （3）再将x1代入上述公式，求出下一个值x2。 （4）如此继续下去，直到前后两次求出的x值（xn+1和xn）满足以下关系： | xn+1-xn|<10-5 #include “math.h” main(){ float a,x0,x1;scanf(“%f”,&a);x0=a/2;x1=(x0+a/x0)/2;do{ x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-5); printf(“%fn”,x1);} 2．进制转换 （1）十进制数转换为其他进制数 一个十进制正整数m转换成r进制数的思路是，将m不断除以r取余数，直到商为0时止，以反序输出余数序列即得到结果。 注意，转换得到的不是数值，而是数字字符串或数字串。 例如，任意读入一个十进制正整数，将其转换成二至十六任意进制的字符串。void tran(int m,int r,char str[],int *n){ char sb[]=“0123456789ABCDEF”;int i=0,g;do{ g=m%r; str[i]=sb[g]; m=m/r; i++; }while(m!=0);*n=i;} main(){ int x,r0;/*r0为进制基数*/ int i,n;/*n中存放生成序列的元素个数*/ char a[50]; scanf(“%d%d”,&x,&r0);if(x>0&&r0>=2&&r0<=16){ tran(x,r0,a,&n);for(i=n-1;i>=0;i--)printf(“%c”,a[i]); printf(“n”);} else exit(0);}（2）其他进制数转换为十进制数 其他进制整数转换为十进制整数的要领是：“按权展开”，例如，有二进制数101011，则其十进制形式为1×25+0×24+1×23+0×22+1×21+1×20=43。若r进制数an……a2a1（n位数）转换成十进制数，方法是an×r n-1+……a2×r1+a1×r0。 注意：其他进制数只能以字符串形式输入。 例 1、任意读入一个二至十六进制数（字符串），转换成十进制数后输出。 #include “string.h” #include “ctype.h” main(){ char x[20];int r,d;gets(x);/*输入一个r进制整数序列*/ scanf(“%d”,&r);/*输入待处理的进制基数2-16*/ d=Tran(x,r);printf(“%s=%dn”,x,d);} int Tran(char *p,int r){ int d,i,cr;char fh,c;d=0;fh=*p;if(fh=='-')p++;for(i=0;i if(toupper(c)>='A')cr=toupper(c)-'A'+10; else cr=c-'0'; d=d*r+cr;} if(fh=='-')d=-d;return(d);} 3．矩阵转置 矩阵转置的算法要领是：将一个m行n列矩阵（即m×n矩阵）的每一行转置成另一个n×m矩阵的相应列。 例 1、将以下2×3矩阵转置后输出。即将 1 2 3 转置成 1 4 6 main(){ int a[2][3],b[3][2],i,j,k=1;for(i=0;i<2;i++) for(j=0;j<3;j++) a[i][j]=k++;/*以下将a的每一行转存到b的每一列*/ for(i=0;i<2;i++)for(j=0;j<3;j++) b[j][i]=a[i][j];for(i=0;i<3;i++)/*输出矩阵b*/ { for(j=0;j<2;j++) printf(“%3d”,b[i][j]); printf(“n”);} } 4．字符处理 （1）字符统计：对字符串中各种字符出现的次数的统计。典型例题：任意读入一个只含小写字母的字符串，统计其中每个字母的个数。#include “stdio.h ” main(){ char a[100];int n[26]={0};int i;/*定义26个计数器并置初值0*/ gets(a);for(i=0;a[i]!= ' ';i++)/*n[0]中存放‟a‟的个数，n[1] 中存放‟b‟的个数……*/ n[a[i]-'a' ]++;/*各字符的ASCII码值减‟a‟的ASCII码值，正好得对应计数器下标*/ for(i=0;i<26;i++) if(n[i]!=0)printf(“%c :%dn ”, i+'a', n[i]);}（2）字符加密 例如、对任意一个只含有英文字母的字符串，将每一个字母用其后的第三个字母替代后输出（字母X后的第三个字母为A，字母Y后的第三个字母为B，字母Z后的第三个字母为C。） #include “stdio.h” #include “string.h” main(){ char a[80]= “China”;int i;for(i=0;i 算法核心是利用“任何正整数整除10的余数即得该数个位上的数字”的特点，用循环从低位到高位依次取出整数的每一数位上的数字。 例 1、任意读入一个5位整数，输出其符号位及从高位到低位上的数字。main(){ long x;int w,q,b,s,g;scanf(“%ld”,&x); if(x<0){printf(“-,”);x=-x;} w=x/10000;/*求万位上的数字*/ q=x/1000%10;/*求千位上的数字*/ b=x/100%10;/*求百位上的数字*/ s=x/10%10;/*求十位上的数字*/ g=x%10;/*求个位上的数字*/ printf(“%d,%d,%d,%d,%dn”,w,q,b,s,g);} 例 2、任意读入一个整数，依次输出其符号位及从低位到高位上的数字。[分析]此题读入的整数不知道是几位数，但可以用以下示例的方法完成此题： 例如读入的整数为3796，存放在x中，执行x%10后得余数为6并输出；将x/10得379后赋值给x。再执行x%10后得余数为9并输出；将x/10得37后赋值给x……直到商x为0时终止。 main(){ long x;scanf(“%ld”,&x);if(x<0){printf(“-”);x=-x;} do { /*为了能正确处理0，要用do_while循环*/ printf(“%d ”, x%10); x=x/10; }while(x!=0); printf(“n”);} 例 3、任意读入一个整数，依次输出其符号位及从高位到低位上的数字。 [分析]此题必须借助数组将依次求得的低位到高位的数字保存后，再逆序输出。main(){ long x;int a[20],i,j;scanf(“%ld”,&x); if(x<0){ printf(“-”);x=-x;} i=0;do { a[i]=x%10; x=x/10;i++; }while(x!=0); for(j=i-1;j>=0;j--) printf(“%d ”,a[j]);printf(“n”);} 6．辗转相除法求两个正整数的最大公约数 该算法的要领是：假设两个正整数为a和b，先求出前者除以后者的余数，存放到变量r中，若r不为0，则将b的值得赋给a，将r的值得赋给b；再求出a除以b的余数，仍然存放到变量r中……如此反复，直至r为0时终止，此时b中存放的即为原来两数的最大公约数。 例 1、任意读入两个正整数，求出它们的最大公约数。[ 法一：用while循环时，最大公约数存放于b中] main(){ int a,b,r;do scanf(“%d%d”,&a,&b);while(a<=0||b<=0);/*确保a和b为正整数*/ r=a%b;while(r!=0){ a=b;b=r;r=a%b;} printf(“%dn”,b);} [ 法二：用do…while循环时，最大公约数存放于a中] main(){ int a,b,r;do scanf(“%d%d”,&a,&b);while(a<=0||b<=0);/*确保a和b为正整数*/ do {r=a%b;a=b;b=r; }while(r!=0);printf(“%dn”,a);} 【引申】可以利用最大公约数求最小公倍数。提示：两个正整数a和b的最小公倍数=a×b/最大公约数。 例 2、任意读入两个正整数，求出它们的最小公倍数。[法一：利用最大公约数求最小公倍数] main(){ int a,b,r,x,y;do scanf(“%d%d”,&a,&b);while(a<=0||b<=0);/*确保a和b为正整数*/ x=a;y=b;/*保留a、b原来的值*/ r=a%b;while(r!=0){ a=b;b=r;r=a%b;} printf(“%dn”,x*y/b);} [法二：若其中一数的最小倍数也是另一数的倍数，该最小倍数即为所求] main(){ int a,b,r,i;do scanf(“%d%d”,&a,&b);while(a<=0||b<=0);/*确保a和b为正整数*/ i=1;while(a*i%b!=0)i++;printf(“%dn”,i*a);} 7．求最值 即求若干数据中的最大值（或最小值）。算法要领是：首先将若干数据存放于数组中，通常假设第一个元素即为最大值（或最小值），赋值给最终存放最大值（或最小值）的max（或min）变量中，然后将该量max（或min）的值与数组其余每一个元素进行比较，一旦比该量还大（或小），则将此元素的值赋给max（或min）……所有数如此比较完毕，即可求得最大值（或最小值）。 例 1、任意读入10个数，输出其中的最大值与最小值。#define N 10 main(){ int a[N],i,max,min;for(i=0;i 素数又称质数，即“只能被1和自身整除的大于1的自然数”。判断素数的算法要领就是依据数学定义，即若该大于1的正整数不能被2至自身减1整除，就是素数。 例 1、任意读入一个正整数，判断其是否为素数。 main(){ int x,k;do scanf(“%d”,&x);while(x<=1);/*确保读入大于1的正整数*/ for(k=2;k<=x-1;k++) if(x%k==0)break;/*一旦能被2~自身-1整除，就不可能是素数*/ if(k==x)printf(“%d is sushun”,x);else printf(“%d is not sushun”,x);} 以上例题可以用以下两种变形来解决（需要使用辅助判断的逻辑变量）： 【变形一】将“2~自身-1”的范围缩小至“2~自身的一半” main(){ int x,k,flag;do scanf(“%d”,&x);while(x<=1);flag=1;/*先假设x就是素数*/ for(k=2;k<=x/2;k++)if(x%k==0){ flag=0;break;}/*一旦不可能是素数，即置flag为0*/ if(flag==1)printf(“%d is sushun”,x);else printf(“%d is not sushun”,x);} 【变形二】将“2~自身-1”的范围缩小至“2~自身的平方根” #include “math.h” main(){ int x,k,flag;do scanf(“%d”,&x);while(x<=1);flag=1;/*先假设x就是素数*/ for(k=2;k<=(int)sqrt(x);k++) if(x%k==0){ flag=0;break;}/*一旦不可能是素数，即置flag为0*/ if(flag==1)printf(“%d is sushun”,x);else printf(“%d is not sushun”,x);} 例 2、用筛选法求得100以内的所有素数。 算法为：（1）定义一维数组a，其初值为：2，3，……，100； （2）若a[k]不为0，则将该元素以后的所有a[k]的倍数的数组元素置为0；（3）a中不为0的元素，均为素数。#include clrscr();/*清屏函数*/ for(k=2;k<101;k++)a[k]=k; for(k=2;k for(j=k+1;j<101;j++) if(a[k]!=0&&a[j]!=0) if(a[j]%a[k]==0)a[j]=0; for(k=2;k<101;k++)if(a[k]!=0)printf(“%5d”,a[k]);} 9．数组元素的插入、删除 （1）数组元素的插入 此算法一般是在已经有序的数组中再插入一个数据，使数组中的数列依然有序。算法要领是： 假设待插数据为x，数组a中数据为升序序列。 ①先将x与a数组当前最后一个元素进行比较，若比最后一个元素还大，就将x放入其后一个元素中；否则进行以下步骤； ②先查找到待插位置。从数组a的第1个元素开始找到不比x小的第一个元素，设其下标为i ； ③将数组a中原最后一个元素至第i个元素依次一一后移一位，让出待插数据的位置，即下标为i的位置； ④将x存放到a(i)中。例题参见前面“„排序‟中插入法排序的例1”。（2）数组元素的删除 此算法的要领是：首先要找到（也可能找不到）待删除元素在数组中的位置（即下标），然后将待删元素后的每一个元素向前移动一位，最后将数组元素的个数减1。 例 1、数组a中有若干不同考试分数，任意读入一个分数，若与数组a中某一元素值相等，就将该元素删除。 #define N 6 main(){ int fs[N]={69,90,85,56,44,80},x;int i,j,n;n=N;scanf(“%d”,&x);/*任意读入一个分数值*/ /*以下查找待删分数的位置，即元素下标*/ for(i=0;i （1）方阵的特点 行列相等的矩阵又称方阵。其两条对角线中“”方向的为主对角线，“/”方向的为副对角线。主对角线上各元素的下标特点为：行列值相等；副对角线上各元素的下标特点为：行列值之和都为阶数加1。 主对角线及其以下部分（行值大于列值）称为下三角。例 1、输出如下5阶方阵。1 2 2 2 2 3 1 2 2 2 3 3 1 2 2 3 3 3 1 2 3 3 3 3 1 #define N 5 main(){ int a[N][N],i,j;for(i=0;i if(i==j)a[i][j]=1; else if(i else a[i][j]=3;for(i=0;i printf(“%3d”,a[i][j]);printf(“n”);} } 例 2、输出如下5阶方阵。1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 #define N 5 main(){ int a[N][N],i,j;for(i=0;i a[i][j]=i+j+1;/*沿副对角线平行线方向考察每个元素，其值等于行列值之和+1*/ for(i=0;i printf(“%3d”,a[i][j]); printf(“n”);} }（2）杨辉三角形 杨辉三角形的每一行是(x+y)n的展开式各项的系数。例如第一行是(x+y)0，其系数为1；第二行是(x+y)1，其系数为1，1；第三行是(x+y)2，其展开式为x2+2xy+y2，系数分别为1，2，1；……直观形式如下： 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 …… 分析以上形式，可以发现其规律：是n阶方阵的下三角，第一列和主对角线均为1，其余各元素是它的上一行、同一列元素与上一行、前一列元素之和。 例 1、编程输出杨辉三角形的前10行。 #define N 10 main(){ int a[N][N],i,j;for(i=0;i for(j=1;j<=i-1;j++) a[i][j]=a[i-1][j-1]+a[i-1][j];for(i=0;i printf(“n”); } } 例 2、以等腰三角形的形状输出杨辉三角形的前5行。1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 #define N 5 main(){ int a[N][N],i,j;for(i=0;i a[i][0]=a[i][i]=1;for(i=0;i for(j=0;j<=i;j++) printf(“%4d”,a[i][j]); printf(“n”); } }第二篇：RSA加密解密算法c语言程序
第三篇：c语言课程设计-文件加密解密(含源代码)
第四篇：RSA算法实验报告
第五篇：C语言常用算法归纳
点击咨询 