C常用经典算法及其实
现
集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289-
常用算法经典代码（C++版）
一、快速排序
voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中
{inth=x,r=y;
intm=a[(x+y)>>1];//取中间的那个位置的值
while(h {while(a[h] while(a[r]>m)r--;//比中间那个位置的值大，循环直到找一个比中间那个值小的 if(h<=r) {inttemp=a[h];//如果此时h<=r，交换a[h]和a[r] a[h]=a[r]; a[r]=temp; h++;r--;//这两句必不可少哦 } } if(r>x)qsort(x,r);//注意此处，尾指针跑到前半部分了 if(h } 调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序 二、冒泡排序 voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中 {for(inti=1;i if(a[j] } 或者 voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中 {for(inti=1;i if(a[j] } 调用：paopao()，适用于n比较小的排序 三、桶排序 voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化 for(inti=1;i<=n;i++)//读入n个数 {inta cin>>a; tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0，说明i出现过tong[i]次，否则没出现过i while(tong[i]!=0) {tong[i]--; cout< } } 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合（归）并排序 voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间 {intb[101];//借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素，t指向第二个区间的第一个元素。while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时，把两个区间的元素抄在新数组中 {k++;//新数组指针加1 if(a[h] else{b[k]=a[t];t++;}//抄第二个区间元素到新数组 } while(h<=m){k++;b[k]=a[h];h++;}//如果第一个区间没有抄结束，把剩下的抄在新数组中 while(t<=r){k++;b[k]=a[t];t++;}//如果第二个区间没有抄结束，把剩下的抄在新数组中 for(into=1;o<=k;o++)//把新数组中的元素，再抄回原来的区间，这两个连续的区间变为有序的区间。 a[l+o-1]=b[o]; } voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序 { intmid; if(x>=y)return; mid=(x+y)/2;//求[x,y]区间，中间的那个点mid,mid把x,y区间一分为二mergesort(x,mid);//对前一段进行二路归并 mergesort(mid+1,y);//对后一段进行二路归并 merge(x,mid,y);//把已经有序的前后两段进行合并 } 归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。 五、二分查找 intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y，查找失败，返回0 if(m>a[mid])//如果m比中间元素大，在后半区间查找，返回后半区间查找结果returnfind(mid+1,tail); else//如果m比中间元素小，在前半区间查找，返回后前区间查找结果 returnfind(head,mid-1); } 六、高精度加法 #include #include usingnamespacestd; intmain() { stringstr1,str2; inta[250],b[250],len;//数组的大小决定了计算的高精度最大位数inti; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2;//输入两个字符串 a[0]=str1.length();//取得第一个字符串的长度 for(i=1;i<=a[0];i++)//把第一个字符串转换为整数，存放在数组a中a[i]=str1[a[0]-i]-'0'; b[0]=str2.length();//取得第二个字符串长度 for(i=1;i<=b[0];i++)//把第二个字符串中的每一位转换为整数，存放在数组B中b[i]=str2[b[0]-i]-'0'; len=(a[0]>b[0]a[0]:b[0]);//取两个字符串最大的长度 for(i=1;i<=len;i++)//做按位加法，同时处理进位 { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } len++;//下面是去掉最高位的0，然后输出。 while((a[len]==0)&&(len>1))len--; for(i=len;i>=1;i--) cout< return0; } 注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。 七、高精度减法 #include intcompare(strings1,strings2); intmain() { stringstr1,str2; inta[250],b[250],len; inti; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; a[0]=str1.length(); for(i=1;i<=a[0];i++) a[i]=str1[a[0]-i]-'0'; b[0]=str2.length(); for(i=1;i<=b[0];i++) b[i]=str2[b[0]-i]-'0'; if((compare(str1,str2))==0)//大于等于，做按位减，并处理借位。{ for(i=1;i<=a[0];i++) {a[i]-=b[i]; if(a[i]<0){a[i+1]--;a[i]+=10;} } a[0]++; while((a[a[0]]==0)&&(a[0]>1))a[0]--; for(i=a[0];i>=1;i--) cout< cout< } else { cout<<'-';//小于就输出负号 for(i=1;i<=b[0];i++)//做按位减，大的减小的 {b[i]-=a[i]; if(b[i]<0){b[i+1]--;b[i]+=10;} } b[0]++; while((b[b[0]]==0)&&(b[0]>1))b[0]--; for(i=b[0];i>=1;i--) cout< cout< } return0; } intcompare(strings1,strings2)//比较字符串（两个数）数字的大小，大于等于返回0，小于返回1。 { if(s1.length()>s2.length())return0;//先比较长度，哪个字符串长，对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++)//长度相同时，就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0;//如果长度相同，每一位也一样，就返回0，说明相等 } 做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。 八、高精度乘法 #include #include usingnamespacestd; intmain() { stringstr1,str2; inta[250],b[250],c[500],len;//250位以内的两个数相乘 inti,j; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; a[0]=str1.length(); for(i=1;i<=a[0];i++) a[i]=str1[a[0]-i]-'0'; b[0]=str2.length(); for(i=1;i<=b[0];i++) b[i]=str2[b[0]-i]-'0'; memset(c,0,sizeof(c)); for(i=1;i<=a[0];i++)//做按位乘法同时处理进位，注意循环内语句的写法。for(j=1;j<=b[0];j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } len=a[0]+b[0]+1;//去掉最高位的0，然后输出 while((c[len]==0)&&(len>1))len--;//为什么此处要len>1 for(i=len;i>=1;i--) cout< return0; } 注意：两个数相乘，结果的位数应该是这两个数的位数和减1。 优化：万进制 #include #include usingnamespacestd; voidnum1(ints[],stringst1); inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法，即10000位十进制乘法。 Intmain() { stringstr1,str2; intlen; cin>>str1>>str2; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); num1(a,str1);//把str1从最低位开始，每4位存放在数组a中 num1(b,str2);//把str2从最低位开始，每4位存放在数组b中 for(inti=1;i<=a[0];i++)//作按位乘法并处理进位，此处是万进制进位for(intj=1;j<=b[0];j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10000; c[i+j-1]%=10000; } len=a[0]+b[0];//a[0]和b[0]存放的是每个数按4位处理的位数 while((c[len]==0)&&(len>1))len--;//去掉高位的0，并输出最高位cout< for(inti=len-1;i>=1;i--)//把剩下来的每一位还原成4位输出 { if(c[i]<1000)cout<<’0’; if(c[i]<100)cout<<’0’; if(c[i]<10)cout<<’0’; cout< } cout< return0; } voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1，按4位一组存放在数组s中 {intk=1,count=1; s[0]=st1.length();//存放st1的长度，省去一长度变量 for(inti=s[0]-1;i>=0;i--)//从最低位开始，处理每一位 {if(count%4==0){s[k]+=(st1[i]-‘0’)*1000;if(i!=0)k++;} if(count%4==1)s[k]=(st1[i]-‘0’); if(count%4==2)s[k]+=(st1[i]-‘0’)*10; if(count%4==3)s[k]+=(st1[i]-‘0’)*100; count++; } s[0]=k;//存放数组的位数，就是按4位处理后的万进制数的位数。 Return; } 九、高精度除法（没讲） 十、筛选法建立素数表 voidmaketable(intx)//建立X以内的素数表prim，prim[i]为0，表示i为素数，为1表示不是质数 { memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;} } } 对于那些算法中，经常要判断素数的问题，建立一个素数表，可以达到一劳永逸的目的。十一、深度优先搜索 voiddfs(intx)\\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=1;k<=n;k++)\\对与顶点x相邻而又没访问过的结点k进行深度优先搜索。 if((a[x][k]==1)&&(visited[k]==0)) dfs(k); } 十二、广度优先搜索 void?bfs(void)//按广度优先非递归遍历图G，n个顶点，编号为1..n。注：图不一定是连通的 {//使用辅助队列Q和访问标记数组visited。 for(v=1;v<=n;v++)visited[v]=0；//标记数组初始化 for(v=1;v<=n;v++) if(visited[v]==0){//v尚未访问 C语言的学习要从基础，100个经典的算法 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ________________________________________________________________ 程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... __________________________________________________________________ 程序源代码： main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出，每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理，you try! 题目：判断101-200之间有多少个素数，并输出所有素数。 _________________________________________________________________ 程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。 ___________________________________________________________________ 程序源代码： #include "math.h" main() { int m,i,k,h=0,leap=1; printf("\n"); for(m=101;m<=200;m++) { k=sqrt(m+1); for(i=2;i<=k;i++) if(m%i==0) {leap=0;break;} if(leap) {printf("%-4d",m);h++; if(h%10==0) printf("\n"); } leap=1; } printf("\nThe total is %d",h); } 题目：打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个“水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。 __________________________________________________________________ 程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。 ___________________________________________________________________ 程序源代码： 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 看懂一个程序，分三步：1、流程；2、每个语句的功能；3、试数； 小程序：1、尝试编程去解决他；2、看答案；3、修改程序，不同的输出结果； 4、照答案去敲； 5、调试错误； 6、不看答案，自己把答案敲出来； 7、实在不会就背会。。。。。周而复始，反复的敲。。。。。 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ ============================================================== 【程序3】 题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？============================================================== 【程序4】 题目：输入某年某月某日，判断这一天是这一年的第几天？ ============================================================== 【程序5】 题目：输入三个整数x,y,z，请把这三个数由小到大输出。 ============================================================== 【程序6】 题目：用*号输出字母C的图案。 ============================================================== 【程序7】 题目：输出特殊图案，请在c环境中运行，看一看，Very Beautiful! ============================================================== 【程序8】 题目：输出9*9口诀。 ============================================================== 【程序9】 题目：要求输出国际象棋棋盘。 ============================================================== 【程序10】 题目：打印楼梯，同时在楼梯上方打印两个笑脸。 -------------------------------------------------------------------------------- 【程序11】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月 后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ============================================================== 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为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,%d\n",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=%d\n",s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i } 3.素数的判断： /*方法一*/ for (t=1,i=2;i 线性方程组AX=B 的数值计算方法实验 一、 实验描述： 随着科学技术的发展，线性代数作为高等数学的一个重要组成部分， 在科学实践中得到广泛的应用。本实验的通过C 语言的算法设计以及编程，来实现高斯消元法、三角分解法和解线性方程组的迭代法（雅可比迭代法和高斯-赛德尔迭代法），对指定方程组进行求解。 二、 实验原理： 1、高斯消去法： 运用高斯消去法解方程组，通常会用到初等变换，以此来得到与原系数矩阵等价的系数矩阵，达到消元的目的。初等变换有三种：(a)、(交换变换)对调方程组两行；(b)、用非零常数乘以方程组的某一行；(c)、将方程组的某一行乘以一个非零常数，再加到另一行。 通常利用(c)，即用一个方程乘以一个常数，再减去另一个方程来置换另一个方程。在方程组的增广矩阵中用类似的变换，可以化简系数矩阵，求出其中一个解，然后利用回代法，就可以解出所有的解。 2、选主元： 若在解方程组过程中，系数矩阵上的对角元素为零的话，会导致解出的结果不正确。所以在解方程组过程中要避免此种情况的出现，这就需要选择行的判定条件。经过行变换，使矩阵对角元素均不为零。这个过程称为选主元。选主元分平凡选主元和偏序选主元两种。平凡选主元： 如果()0p pp a ≠，不交换行；如果()0p pp a =，寻找第p 行下满足() 0p pp a ≠的第一 行，设行数为k ，然后交换第k 行和第p 行。这样新主元就是非零主元。偏序选主元：为了减小误差的传播，偏序选主元策略首先检查位于主对角线或主对角线下方第p 列的所有元素，确定行k ，它的元素绝对值最大。然后如果k p >，则交换第k 行和第p 行。通常用偏序选主元，可以减小计算误差。 3、三角分解法： 由于求解上三角或下三角线性方程组很容易所以在解线性方程组时，可将系数矩阵分解为下三角矩阵和上三角矩阵。其中下三角矩阵的主对角线为1，上三角矩阵的对角线元素非零。有如下定理： 如果非奇异矩阵A 可表示为下三角矩阵L 和上三角矩阵U 的乘积： A LU = (1) 则A 存在一个三角分解。而且，L 的对角线元素为1，U 的对角线元素非零。得到L 和U 后，可通过以下步骤得到X ： (1)、利用前向替换法对方程组LY B =求解Y 。 (2)、利用回代法对方程组UX Y =求解X 。 4、雅可比迭代： C语言常用算法集合 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i C语言经典算法大全 老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官（一） 老鼠走迷官（二） 骑士走棋盘 八个皇后 八枚银币 生命游戏 字串核对 双色、三色河内塔 背包问题（Knapsack Problem） 数、运算 蒙地卡罗法求PI Eratosthenes筛选求质数 超长整数运算（大数运算） 长PI 最大公因数、最小公倍数、因式分解 完美数 阿姆斯壮数 最大访客数 中序式转后序式（前序式） 后序式的运算 关于赌博 洗扑克牌（乱数排列） Craps赌博游戏 约瑟夫问题（Josephus Problem） 集合问题 排列组合 格雷码（Gray Code） 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法- 改良的插入排序Shaker 排序法- 改良的气泡排序Heap 排序法- 改良的选择排序快速排序法（一） 快速排序法（二） 快速排序法（三） 合并排序法 基数排序法 搜寻 循序搜寻法（使用卫兵） 二分搜寻法（搜寻原则的代表）插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵 1.河内之塔 说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越 战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。 解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘 子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 #include 60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1; 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) bonus=i*0.1; else if(i<=200000) bonus=bonus1+(i-100000)*0.075; else if(i<=400000) bonus=bonus2+(i-200000)*0.05; else if(i<=600000) bonus=bonus4+(i-400000)*0.03; 经典的滤波算法(转) 1、限幅滤波法（又称程序判断滤波法） A、方法： 根据经验判断，确定两次采样允许的最大偏差值（设为A） 每次检测到新值时判断： 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值 B、优点： 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 2、中位值滤波法 A、方法： 连续采样N次（N取奇数） 把N次采样值按大小排列 取中间值为本次有效值 B、优点： 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 C、缺点： 对流量、速度等快速变化的参数不宜 3、算术平均滤波法 A、方法： 连续取N个采样值进行算术平均运算 N值较大时：信号平滑度较高，但灵敏度较低 N值较小时：信号平滑度较低，但灵敏度较高 N值的选取：一般流量，N=12；压力：N=4 B、优点： 适用于对一般具有随机干扰的信号进行滤波 这样信号的特点是有一个平均值，信号在某一数值范围附近上下波动 C、缺点： 对于测量速度较慢或要求数据计算速度较快的实时控制不适用 比较浪费RAM 递推平均滤波法对偶然出现的脉冲性干扰的抑制作用较差 4、递推平均滤波法（又称滑动平均滤波法） A、方法： 把连续取N个采样值看成一个队列 队列的长度固定为N 每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则) 把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取：流量，N=12；压力：N=4；液面，N=4~12；温度，N=1~4 B、优点： 对周期性干扰有良好的抑制作用，平滑度高 适用于高频振荡的系统 C、缺点： 灵敏度低 对偶然出现的脉冲性干扰的抑制作用较差 不易消除由于脉冲干扰所引起的采样值偏差 不适用于脉冲干扰比较严重的场合 比较浪费RAM 5、中位值平均滤波法（又称防脉冲干扰平均滤波法） A、方法： 相当于“中位值滤波法”+“算术平均滤波法” 连续采样N个数据，去掉一个最大值和一个最小值 然后计算N-2个数据的算术平均值 N值的选取：3~14 B、优点： 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差 C、缺点： 测量速度较慢，和算术平均滤波法一样 比较浪费RAM 6、限幅平均滤波法 A、方法： 相当于“限幅滤波法”+“递推平均滤波法” 每次采样到的新数据先进行限幅处理， 再送入队列进行递推平均滤波处理 B、优点： 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差 C、缺点： 比较浪费RAM 一分而治之算法 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。下列通过实例加以说明。 例：利用分而治之算法求一个整数数组中的最大值。 练习：[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。 二贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪 实验五查找的实现 一、实验目的 1．通过实验掌握查找的基本概念； 2．掌握顺序查找算法与实现； 3．掌握折半查找算法与实现。 二、实验要求 1．认真阅读和掌握本实验的参考程序。 2．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。 2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。 一、顺序查找 顺序查找代码： #include"stdio.h" #include"stdlib.h" typedef struct node{ int key; }keynode; typedef struct Node{ keynode r[50]; int length; }list,*sqlist; int Createsqlist(sqlist s) { int i; printf("请输入您要输入的数据的个数:\n"); scanf("%d",&(s->length)); printf("请输入您想输入的%d个数据;\n\n",s->length); for(i=0;i /* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： c语言经典算法设计方法 经典算法设计方法 一、什么是算法 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入， 在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑 判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决 这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一 个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法 是问题规模n的函数f(n)，算法执行的时间的增长率与f(n)的增长率正相关，称作渐进时间复杂度(Asymptotic Time Complexity)。时间复杂度用"O(数量级)"来表示，称为"阶"。常见的时间复杂度有：O(1)常数阶；O(log2n)对数阶；O(n)线性阶；O(n2)平方阶。 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时 间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复 杂度的分析要简单得多。 二、算法设计的方法 1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要 求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采 用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出 问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1 规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 【问题】阶乘计算 问题描述：编写程序，对给定的n(n≦ 100)，计算并输出k的阶乘k！ (k=1，2，…，n)的全部有效数字。 由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N 用数组a[]存储： N=a[m]×10m-1+a[m-1]×10m-2+…+a[2]×101+a[1]×100 并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元 素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素…。例如，5！=120，在数组中的存储形式为： 3 02 1… 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1， 表示成整数120。计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次 后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。细节见以下程序。 #include stdio.h #include malloc.h #define MAXN 1000 void pnext(int a[],int k) { int*b,m=a[0],i,j,r,carry； b=(int*)malloc(sizeof(int)*(m+1))； for(i=1；i=m；i++) b[i]=a[i]； for(j=1；j=k；j++) C语言经典算法100例(1)(2007-08-15 15:09:22) C 语言编程经典 100 例 A：【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf(“\n“); for(i=1;i〈5;i++) ／*以下为三重循环*/ for(j=1;j〈5;j++) for (k=1;k〈5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf(“%d,%d,%d\n“,i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf(“%ld“,&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i〈=100000) bonus=i*0.1; else if(i〈=200000) bonus=bonus1+(i-100000)*0.075; else if(i〈=400000) bonus=bonus2+(i-200000)*0.05; C语言常用算法归纳 应当掌握的一般算法 一、基本算法： 交换、累加、累乘 二、非数值计算常用经典算法： 穷举、排序（冒泡，选择）、查找（顺序即线性） 三、数值计算常用经典算法： 级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法） 四、其他： 迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形） 详细讲解 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() { int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b); } 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为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,%d\n",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=%d\n",s); } 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 3．累乘c语言经典算法
数据结构与算法C语言版期末复习题
C语言经典算法100例题目
非常全的C语言常用算法
C语言经典算法100例(1---30)
C语言常用算法集合
线性方程组的数值算法C语言实现(附代码)
最新C语言常用算法集合汇总
C语言经典算法大全
c语言经典算法100例
C语言经典算法题目及答案
经典滤波算法及C语言程序
C语言经典算法详解
查找算法的实现(C语言版)
C语言常用排序算法
c语言经典算法设计方法
C语言经典算法100例(1)
最新C语言常用算法归纳
相关主题
文本预览