第一篇：C语言常用算法归纳
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”); } } #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 if(n>0) printf(“nn0.000000nn”); else printf(“nnerror!nn”);} else { if(x>0) { if(n==0) printf(“nn1.000000nn”); else { if(n>0) printf(“nn%0.6lfnn”,f(x,n)); else printf(“nn%0.6lfnn”,1/f(x,-n)); } } else { if(n==0) printf(“nn1.000000nn”); else { if(n>0) printf(“nn%0.6lfnn”,f(x,n)); else printf(“nn%0.6lfnn”,1/f(x,-n)); } } } } double f(double x,int n){ if(n==1)return x;return f(x,n-1)*x;} #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; 程序： #include lfsr(int a,int b,int c,int d,int T[]);void main(){ int A[19]={1,0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,1}; int B[22]={0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1,0,1,0,1,1};int C[23]={1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,1};for(int i=0;i { printf(“%d”,A[18]^B[21]^C[22]); lfsr(13,16,17,18,A); lfsr(12,16,20,21,B); lfsr(17,18,21,22,C);} else if(j==1) { printf(“%d”,A[18]^B[21]^C[22]); if(A[9]==0) lfsr(13,16,17,18,A); if(B[11]==0) lfsr(12,16,20,21,B); if(C[11]==0) lfsr(17,18,21,22,C);} else if(j==2) { printf(“%d”,A[18]^B[21]^C[22]); if(A[9]==1) lfsr(13,16,17,18,A); if(B[11]==1) lfsr(12,16,20,21,B); if(C[11]==1) lfsr(17,18,21,22,C);} else if(j==3) { printf(“%d”,A[18]^B[21]^C[22]); lfsr(13,16,17,18,A); lfsr(12,16,20,21,B); lfsr(17,18,21,22,C); } } printf(“n n”);} lfsr(int a,int b,int c,int d,int T[]){ int i; for(i=d;i>0;i--) { T[i]=T[i-1]; } T[0]=T[a]^T[b]^T[c]^T[d]; return(T[0]);} 密钥流： A[19]={1,0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,1}; B[22]={0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1,0,1,0,1,1};C[23]={1,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,1};密钥流序列： 1111 1111 1101 1010 1101 0101 0111 0001 1110 0000 1010 1000 0101 1100 0100 0000第二篇：RSA加密解密算法C语言代码
第三篇：C语言算法X的n次方(递归)（范文模版）
第四篇：RSA加密解密算法c语言程序
第五篇：A5算法C语言实现报告（写写帮推荐）
点击咨询 