c语言常见小算法的解题思路

《c语言常见小算法的解题思路》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.判定某一年是否是闰年闰年时间：四年一闰，百年不闰，四百年再闰。闰年的条件是：1)。能被4整除，但不能被100整除的年份都是闰年。如1996,20042)0能被100整除，又能被400整除的年份是闰年。如1600,2000。不符合着两个条件的年份不是闰年。2.对于一个大于等于3的正整数，判断他是不是一个素数.所谓素数，是指除了1和该数本身外，不能被其它任何整数整除的数•判断一个数n(n>=3)是否是素数，将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。3.输入三角形的三边长，求三角形的面积。设输入的三边长a,b,c能构成三角形，从数学知识

2、知道三角形而积的公式为area=J_a)($__c),其中s=(q+〃+00一元二次方程的根为旺=2a°2a7.求一天内表的指针的重合次数可以只考虑12小时的情况，时针和分针重合时满足一下两条：每分钟的度数X分钟数=每小时的读书X小时数(因为两针重合，故其度数一定相等)小时一分钟数4-60=n(n为0到12的整数)故有360..360,mimus=hour

3、6012hour一minius/60=n12小时内重和11次(在12点重合两次只算一次)故一天24小时内重合23次8.判断m是否是素数。让m被2到除，如果m能被2〜k之中任何一个整数整除，则提前结束循环，此时i必然小于或等于k；如果m不能被2〜kZ间的任意整数整除，则在完成最后一次循环猴，i还要加1,因此i=k+l,然后猜种植循环。在循环之后判别i的值是否大于或等于k+1,若是，则表明未曾被2〜k之间任意整数整除过，因此是素数。9.约瑟夫问题设有n个人围坐一圈，现从指定的第1个人开始报数，数到第m个人出列，然后从下一个人重新开始报数，数到第m个人又出列，。。。。如此重复，知道

4、所有的人全部出列为止。选用单循环链表做为存储结构，输入出列人的标号，(1)建立具有几个节点的单循环链表，其数据域值为生成结点时的顺序号。(1)用j计数扫描过的结点，当j=m-l时，说明其直接后继结点就是出列结点，先输出其数据域值，再删除该结点，再从被删结点的下一个结点重新开始计数。如此重复上述步骤，知道仅剩最后一个结点，再将该结点出列。1.设有n个元素进栈，请给出全部可能的出栈序列个数和不可能的出栈序列个数。设全部可能的出栈序列个数为化，则b=丄厂”_丄逊对n个元素组成的序列，全部可能的排列数Pn=nl,所以不可能出栈序列的个数为Pn-bn2.字符串的模式匹配：子串的定位运算

5、。一般将主串称为目标串s,子串称为模式串t,如果目标串s中能够找到模式串t,则模式匹配成功，否则不成功。(1)简单模式匹配算法：Brute-Force算法从目标串s=,,s0sls2...sn-r,的第一个字符开始和模式串%t0tl・・.tm・l”中第一个字符比较，若相等，则继续逐个比较后续字符，否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较(相当与模式串t整体向后移动一位字符)。intindex(Sstrings,Sstringt){inti=j=0;n=s.len;m=Llen;if(n

6、s.data[i]==t.data[j]){i++；j++}else{i=i-j+1;j=0;}}if(j>=m)retumi-m+1;elsereturno;}算法最多比较n-m+1趟，总比较次数为m*(mm+l),最坏情况下时间复杂度为O(m*n)o由于目标串的指针要回溯，所以比较次数较大。(2)KMP算法改进的模式匹配算法可使目标串的检测指针不必回溯。模式串的冋溯位置与s无关，由t自身就可以推出。max{p10v上v厶且”也…心”=next[j]=<-,j=00,其它算法：voidNext(Sstringt,intnextf])intm=t.len;intj=0,k=

7、-l;next[O]=-1;while(j

8、

9、t.data[j]==t.data[k]){k++;j++；next[j]=k;}elsek=nextfk];}}KMP算法的思想是：设设i和j分别指向目标串和模式串中正待比较的字符，i和j的初值均为0。若有5,.=r.,则i和j分别增1再继续比较；否则，i不变，j改变为next

10、jj(模式串右滑)，再比较耳和―。依次类推，直到出现以下两种情况：一种是j回退到j=nextrj]的位置时有s—j,贝心和j分别增1再继续比较；另一种是j回