江苏省二级C语言上机考试常见算法当年就是凭它拿了个优秀.docx
- 文档编号:13168570
- 上传时间:2023-06-11
- 格式:DOCX
- 页数:19
- 大小:23.24KB
江苏省二级C语言上机考试常见算法当年就是凭它拿了个优秀.docx
《江苏省二级C语言上机考试常见算法当年就是凭它拿了个优秀.docx》由会员分享,可在线阅读,更多相关《江苏省二级C语言上机考试常见算法当年就是凭它拿了个优秀.docx(19页珍藏版)》请在冰点文库上搜索。
江苏省二级C语言上机考试常见算法当年就是凭它拿了个优秀
穷举法
★最大公约数和最小公倍数
用穷举法求最大公约数iloop的思路:
1、穷举的范围是1到两个整数中的最小数;
2、可能的解是两个数分别除以iloop时都能整除,余数为0的那个iloop.而最小公倍数等于两个数的积除以最大公约数。
#include
intmax(intfirst,intsecond);
intmin(intfirst,intsecond);
voidmain(){intn1=0,n2=0,imax=0,imin=0;
printf("pleaseinputtwonumber:
\n");
scanf("%d%d",&n1,&n2);
imax=max(n1,n2);
imin=min(n1,n2);
printf("maxnumberis:
%d\n",imax);
printf("minnumberis:
%d\n",imin);}intmax(intfirst,intsecond){intitmp=0,iloop=1;if(first>second){itmp=first;
first=second;
second=itmp;}while(iloop<=first){if(((first%iloop)==0)&&((second%iloop)==0))
itmp=iloop;
iloop=iloop+1;}returnitmp;}intmin(intfirst,intsecond){intitmp=0;
itmp=first*second/max(first,second);
returnitmp;}★数字分解算法
试想想十进制数123,要怎样才能分解出
1、"2和3呢?
个位3当然是:
123%10=3;十位2有点难度,不过想想就出来啦:
12%10=2嘛,那12怎么来呢?
123/10就等于12了嘛~~~至于1,用123除以100就出来啦~程序如下:
#include
voidmain(){intno=0,itmp=0;
scanf("%d",&no);
while(no>0){itmp=no%10;
printf("%d\n",itmp);
no=no/10;}}
★水仙花数
所谓水仙花数,是指一个3位的十进制数,该数各位数字的立方和等于该数本身。
例如153是一个水仙花数,因为13+53+33=
153."100到1000里当然还有几个水仙数,我们就交给电脑算吧~
#include
voidmain(){intge=0,shi=0,bai=0,itmp=0,ino=0;
for(ino=100;ino<1000;ino++){ge=ino%10;
shi=(ino/10)%10;
bai=(ino/100)%10;
itmp=ge*ge*ge+shi*shi*shi+bai*bai*bai;
if(itmp==ino)
printf("nois:
%d\n",ino);}}
排序法
(1)“冒泡法”
冒泡法大家都较熟悉。
其原理为从a[0]开始,依次将其和后面的元素比较,若a[O]>a[i],则交换它们,一直比较到a[n]。
同理对a[1],a[2],...a[n-1]处理,即完成排序。
下面列出其代码:
voidbubble(int*a,intn)/*定义两个参数:
数组首地址与数组大小*/{inti,j,temp;
for(i=0;i for(j=i+1;j if(a[i]>a[j]){ temp=a[i]; a[i]=a[j]; a[j]=temp;}} 冒泡法原理简单,但其缺点是交换次数多,效率低。 下面介绍一种源自冒泡法但更有效率的方法“选择法”。 (2)“选择法” 选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面 元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换,提高了效率。 voidchoise(int*a,intn){inti,j,k,temp; for(i=0;i k=i;/*给记号赋值*/ for(j=i+1;j if(a[k]>a[j])k=j;/*是k总是指向最小元素*/ if(i! =k){/*当k! =i是才交换,否则a[i]即为最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp;}}}选择法比冒泡法效率更高,但说到高效率,非快速法”莫属, 现在就让我们来了解它。 (3)“插入法” 插入法是一种比较直观的排序方法。 它首先把数组头两个元素排好序,再依次把后面的元素插入适当的位置。 把数组元素插完也就完成了排序。 voidinsert(int*a,intn){inti,j,temp; for(i=1;i temp=a[i];/*temp为要插入的元素*/ j=i-1; while(j>=0&&temp j--;}a[j+1]=temp;/*插入*/10473598}410 4710 34710}用c实现的插入排序法,先输入10个数,然后利用插入排序法进行排序,将结果输出。 算法简单,可供初学者学习。 #include"stdio.h" #include"conio.h" main(){inta[10],r[11]; int*p; inti,j; for(i=0;i<10;i++){p=&a[i]; printf("pleasescantheNO: %d\n",i);scanf("%d",p); r[i+1]=a[i];}r[0]=1; for(i=2;i<=10;i++){r[0]=r[i]; j=i-1; while(r[j]>r[0]){r[j+1]=r[j]; j--;}r[j+1]=r[0];}for(i=1;i<=10;i++){p=&r[i];printf("formmintomaxtheNO: %dvalue=%d\n",i,*p);}getch();}归并排序算法(合并排序算法) 合并排序(MERGESORT是又一类不同的排序方法,合并的含义就是将两 个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并 算法。 它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个有序的子序列组成,每个子序列的长度为1,然后再两两合并,得到了一个N/2个长度为2或1的有序子序列,再两两合并,如此重复,直到得到一个长度为N的有序数据序列为止,这种排序方法称为2—路合并排序。 例如数组A有7个数据,分别是: 49386597761327,那么采用归并排序算法的操作过程如图 7所示: 初始值[49][38][65][97][76][13][27] 看成由长度为1的7个子序列组成 第一次合并之后[3849][6597][1376][27] 看成由长度为1或2的4个子序列组成 第二次合并之后[38496597][132776] 看成由长度为4或3的2个子序列组成 第三次合并之后[13273849657697] 合并算法的核心操作就是将一维数组中前后相邻的两个有序序列合并成一个有序序列。 合并算法也可以采用递归算法来实现,形式上较为简单,但实用性 很差。 合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次,按照这一规律,当有N个子序列时可以推断出合并的次数是X(2>=N符合此条件的最小那个X)。 其时间复杂度为: O(nlogn)所需辅助存储空间为: O(n) 归并算法如下: longmerge(long*A,longp,longq,longr){longn1,n2,i,j,k; long*L,*R; n1=q-p+1; n2=r-q; L=(long*)malloc((n1+2)*sizeof(long)); R=(long*)malloc((n2+2)*sizeof(long));for(i=1;i<=n1;i++) L=A[p+i-1]; for(j=1;j<=n2;j++) R[j]=A[q+j]; L[n1+1]=R[n2+1]=RAND_MAX; i=j=1; for(k=p;k<=r;k++){if(L<=R[j]){A[k]=L;i++;}else{A[k]=R[j]; j++;}} free(L); free(R); return0;}longmergesort(long*A,longp,longr){longq;if(p mergesort(A,p,q); mergesort(A,q+1,r); merge(A,p,q,r);}return0;}查找法 1)线性法 线性查找法就是把数组的每一个元素与索检关键字进行比较.平均来说,程序 要把查找关键字与一般数组元素进行比较. 线性查找法对小型数组和未排序的数组效果较好,但是,对大型数组来说,线性查找法效率较低.如果已经对数组排序,那么可以使用二分查找法. #include #defineSIZE100 intlinearSearch(int[],int,int); intmain(void){inta[SIZE],x,searchKey,element; /*给数组建立一些数据*/ for(x=0;x<=SIZE-1;x++){a[x]=2*x;}printf("Enterintegersearchkey: "); scanf("%i",&searchKey); element=linearSearch(a,searchKey,SIZE); if(element! =-1){printf("Foundvalueinelement%i\n",element);}else printf("Valuenotfound\n"); return0;}/*线性查找函数*/ intlinearSearch(intarray[],intkey,intsize){intn; for(n=0;n<=size-1;n++) if(array[n]==key) returnn;} (2)折半法(二分法) 数组a中元素值已经按递增次序排列,长度为n。 现在a中用二分法查找值为b的元素,若找到则返回对应的下标,否则返回- 1." 分析: 二分法查找算法的中心思想就是设立三个位置指针,low指向低端位置high指向高端位置,mid指向low与high的中间位置,由于数组a本身已排好序,当用a[mid]与待查数b比较时,如果b=a[mid],则返回该位置退出函数;如果b>a[mid],贝Ub应该落在mid与high之间,此时用mid的值代替low的值;女口果b 如果重复到low>high时,则表示在数组a中没有找到与b的值相等的元素,返回- 1."示例函数如下: intserch(doublea[],intn,doubleb) {intlow,high,mid; low=0; high=n-1; while(low<=high){mid=(low+high)/2;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 江苏省 二级 语言 上机 考试 常见 算法 当年 就是 优秀
![提示](https://static.bingdoc.com/images/bang_tan.gif)