一些算法.ppt

《一些算法.ppt》由会员分享，可在线阅读，更多相关《一些算法.ppt（48页珍藏版）》请在三一文库上搜索。

1、简单题,一个奇异的三位数,一个自然数的七进制表达式是一个三位数，而这个自然数的九进制表示也是一个三位数，且这两个三位数的数码正好相反，求这个三位数。,一个奇异的三位数,*问题分析与算法设计 根据题意可知，七进制和九进制表示的这全自然数的每一位一定小于7，可设其七进制数形式为kji(i、j、k的取值分别为16)，然后设其九进制表示形式为ijk。,*程序说明与注释 #include int main() int i,j,k; for(i=1;i7;i+) for(j=0;j7;j+) for(k=1;k7;k+) if(i*9*9+j*9+k=i+j*7+k*7*7) printf(“The sp

2、ecial number with 3 digits is:“); printf(“%d%d%d(7)=%d%d%d(9)=%d(10)n“,k,j,i,i,j,k,i*9*9+j*9+k); *运行结果 The special number with 3 digits is:503(7)=305(9)=248(10),8除不尽的自然数,一个自然数被8除余1，所得的商被8除也余1，再将第二次的商被8除后余7，最后得到一个商为a。又知这个自然数被17除余4，所得的商被17除余15，最后得到一个商是a的2倍。求这个自然数。,8除不尽的自然数,问题分析与算法设计 根据题意，可设最后的商为i(i从0开

3、始取值)，用逆推法可以列出关系式： (i*8+7)*8)+1)*8+1=(2*i*17)+15)*17+4 再用试探法求出商i的值。,8除不尽的自然数,*程序说明与注释 #include int main() int i; for(i=0;i+) /*试探商的值*/ if(i*8+7)*8+1)*8+1=(34*i+15)*17+4) /*逆推判断所取得的当前i值是否满足关系式*/ /*若满足则输出结果*/ printf(“The required number is: %dn“,(34*i+15)*17+4); break; /*退出循环*/ *运行结果 The required numbe

4、r is:1993,有限5位数,个位数为6且能被3整除的五位数共有多少？,有限5位数,*题目分析与算法设计 根据题意可知，满足条件的五位数的选择范围是10006、10016。99996。可设基础数i=1000，通过计算i*10+6即可得到欲选的数(i的变化范围是1000999)，再判断该数能否被3整除。,有限5位数,*程序说明与注释 #include int main() long int i; int count=0; /*count:统计满足条件的五位数的个数*/ for(i=1000;i9999;i+) if(!(i*10+6)%3) /*判断所选的数能否被3整除*/ count+; /

5、*若满足条件则计数*/ printf(“count=%dn“,count); *运行结果 count=2999,阶乘尾数零的个数,100!的尾数有多少个零？,阶乘尾数零的个数,问题分析与算法设计 可以设想：先求出100!的值，然后数一下末尾有多少个零。事实上，由于计算机所能表示的整数范围有限，这是不可能的。 为了解决这个问题，必须首先从数学上分析在100!结果值的末尾产生零的条件。 一个整数N若含有一个因子5，则必然会在求N!时产生一个零。因此问题转化为求1到100这100个整数中包含了多少个因子5。若整数N能被25整除，则N包含2个因子5；若整数N能被5整除，则N包含1个因子5。,阶乘尾数零

6、的个数,*程序说明与注释 #include int main() int a,count =0; for(a=5;a=100;a+=5) /循环从5开始，以5的倍数为步长，考察整数 +count; /若为5的倍数，计数器加1 if(!(a%25) +count; /若为25的倍数，计数器再加1 printf(“The number of 0 in the end of 100! is: %d.n“,count); /打印结果 return 0; *运行结果 The number of 0 in the end of 100! is: 24.,阶乘尾数零的个数,*思考题 修改程序中求因子5的数目

7、的算法，使程序可以求出任意N!的末尾有多少个零。,4位反序数,设N是一个四位数，它的9倍恰好是其反序数，求N。反序数就是将整数的数字倒过来形成的整数。例如：1234的反序数是4321。,4位反序数,*问题分析与算法设计 可设整数N的千、百、十、个位为i、j、k、l，其取值均为09，则满足关系式： (i*103+j*102+10*k+l)*9=(l*103+k*102+10*j+i) 的i、j、k、l即构成N。,4位反序数,*程序说明与注释 #include int main() int i; for(i=1002;i1111;i+) /*穷举四位数可能的值*/ if(i%10*1000+i/1

8、0%10*100+i/100%10*10+i/1000=i*9) /*判断反序数是否是原整数的9倍*/ printf(“The number satisfied stats condition is: %dn“,i); /*若是则输出*/ *运行结果 The number satisfied states condition is:1089,高次方数的尾数,求13的13次方的最后三位数 。,高次方数的尾数,*问题分析与算法设计 解本题最直接的方法是：将13累乘13次方截取最后三位即可。 但是由于计算机所能表示的整数范围有限，用这种“正确”的算法不可能得到正确的结果。事实上，题目仅要求最后三位的

9、值，完全没有必要求13的13次方的完整结果。 研究乘法的规律发现：乘积的最后三位的值只与乘数和被乘数的后三位有关，与乘数和被乘数的高位无关。利用这一规律，可以大大简化程序。,高次方数的尾数,*程序说明与注释 #include int main() int i,x,y,last=1; /*变量last保存求X的Y次方过程中的部分乘积的后三位*/ printf(“Input X and Y(X*Y):“); scanf(“%d*%d“, /*打印结果*/ *运行结果 Input X and Y(X*Y):13*13 The last 3 digits of 13*13 is:253 Input X

10、 and Y(X*Y):13*20 The last 3 digits of 13*20 is:801,求车速,一辆以固定速度行驶的汽车，司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的)，为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少？新的对称数是多少？,求车速,*问题分析与算法设计 根据题意，设所求对称数为i，其初值为95589，对其依次递增取值，将i值的每一位分解后与其对称位置上的数进行比较，若每个对称位置上的数皆相等，则可判定i即为所求的对称数。,求车速,*程序说明与注释 #include int main() int

11、t,a5; /*数组a存放分解的数字位*/ long int k,i; for(i=95860;i+) /*以95860为初值，循环试探*/ for(t=0,k=100000;k=10;t+) /*从高到低分解所取i值的每位数*/ /* 字，依次存放于a0a5中*/ at=(i%k)/(k/10); k/=10; if(a0=a4) ,求车速,*运行结果 The new symmetrical number kelometers is:95959. The velocity of the car is:50.00 *思考题 将一个数的数码倒过来所得到的新数叫原数的反序数。如果一个数等于它的反序

12、数，则称它为对称数。求不超过1993的最大的二进制的对称数。,可逆素数,求四位的可逆素数。可逆素数指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。,可逆素数,*问题分析与算法设计 本题的重点不是判断素数的方法，而是求一个整数的反序数。求反序数的方法是从整数的末尾依次截取最后一位数字，每截取一次后整数缩小10倍，将截取的数字作为新的整数的最后一位（新的整数扩大10倍后加上被截取的数字）。这样原来的整数的数字从低到高被不断地截取，依次作为新的整数从高到低的各位数字。,可逆素数,*程序说明与注释 #include #include int num(int number); int ok(i

13、nt number); int main() int i,count; printf(“There are invertable primes with 4 digits: n“); for(count=0,i=1001;i9999;i+=2) /穷举全部的奇数 if(num(i) /若是可逆素数，则输出 printf(count%9 ? “%3d:%d“ : “%3d:%dn“,+count,i); return 0; ,int num(int number) int i,j; if(!ok(number)return 0; /判断是否为素数 for(i=number,j=0;i0;i/=1

14、0) /按位将整数倒过来，产生反序数 j=j*10 + i%10; if(numberj) /若原数小于反序数 if(!ok(i) /判断对应的反序数是否为可逆素数 return 0; else return 1; /若是可逆数素数，则返回1 else return 0; getchar(); return 0; ,可逆素数,int ok(int number) int i,j; if(number%2 =0) /判断是否为素数 return 0; j= sqrt(double)number) +1 ; /取整数的平方根为判断的上限 for(i=3;ij;i+=2) if(number %i

15、=0) /若为素数则返回1，否则返回0 return 0; return 1; ,*思考题 求1000以内的孪生素数。孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2称为孪生素数。,回文素数,求不超过1000的回文素数。 所谓回文素数是指，对一个整数n从左向右和从由向左读其结果值相同且是素数，即称n为回文素数。,回文素数,*问题分析与算法设计 本题的重点不是判断素数的方法，而是求回文整数。构造回文数的方法很多，这里仅介绍一种最简单的算法。实现思路是先求出一个整数的回文数，再判断是否为素数。 不超过1000的回文数包括二位和三位的回文数，我们采用穷举法来构造一个整数并求与其对应的反序

16、数，若整数与其反序数相等，则该整数是回文数。,回文素数,*程序说明与注释 #include int a(int n) int main() int i,j,t,k,s; printf(“Following are palindrome primes not greater than 1000:n”); for(i=0;i10|t10) ,/判断参数n是否为素数 int a(int n) int i; for(i=2;i(n-1)/2;+=i) if(n%i = 0) return 0; return 1; *运行结果 Following are palindrome primes not gr

17、eater than 1000: 11 101 131 151 181 191 313 353 373 383 727 787 797 919 929,素数幻方,求四阶的素数幻方。即在一个4X4 的矩阵中，每一个格填 入一个数字，使每一行、每一列和两条对角线上的4 个数字所组成的四位数，均为可逆素数。,素数幻方,*问题分析与算法设计 有了前面的基础，本题应当说是不困难的。 最简单的算法是：采用穷举法，设定4X4矩阵中每一个元素的值后，判断每一行、每一列和两条对角线上的4个数字组成的四位数是否都是可逆素数，若是则求出了满足题意的一个解。 这种算法在原理是对的，也一定可以求出满足题意的全部解。但是

18、，按照这一思路编出的程序效率很低，在微机上几个小时也不会运行结束。这一算法致命的缺陷是：要穷举和判断的情况过多。,素数幻方,充分利用题目中的“每一个四位数都是可逆素数”这一条件，可以放弃对矩阵中每个元素进行的穷举的算法，先求出全部的四位可逆素数(204个)，以矩阵的行为单位，在四位可逆素数的范围内进行穷举，然后将穷举的四位整数分解为数字后，再进行列和对角线方向的条件判断，改进的算法与最初的算法相比，大大地减少了穷举的次数。,素数幻方,考虑矩阵的第一行和最后一行数字，它们分别是列方向四位数的第一个数字和最后一个数字，由于这些四位数也必须是可逆素数，所以矩阵的每一行和最后一行中的各个数字都不能为偶

19、数或5。 这样穷举矩阵的第一行和最后一行时，它们的取值范围是：所有位的数字均不是偶数或5的四位可逆数。由于符合这一条件的四位可逆素数很少，所以这一范围限制又一次减少了穷举的次数。,素数幻方,对算法的进一步研究会发现： 当设定了第一和第二行的值后，就已经可以判断出当前的这种组合是否一定是错误的(尚不能肯定该组合一定是正确的)。 若按列方向上的四个两位数与四位可逆数的前两位矛盾(不是其中的一种组合)，则第一、二行的取值一定是错误的。 同理在设定了前三行数据后，可以立刻判断出当前的这种组合是否一定是错误的，若判断出矛盾情况，则可以立刻设置新的一组数据。 这样就可以避免将四个数据全部设定好以后再进行判

20、断所造成的低效。,素数幻方,根据以上分析，可以用伪语言描述以上改进的算法： 开始 找出全部四位的可逆素数； 确定全部出现在第一和最后一行的四位可逆素数； 在指定范围 内穷举第一行 在指定范围内穷举第二行 若第一、第二、三行已出现矛盾，则继续穷举下一个数； 在指定范围内穷举第四行 判断列和对角方向是否符合题意 若符合题意，则输出矩阵； 否则继续穷举下一个数； 结束,最大公约数和最小公倍数,求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM),最大公约数和最小公倍数,*问题分析与算法设计 手工方式求两个正整数的最大公约数的方法是用辗转相除法，在程序中可以模拟这种方式。,最大公约数和最小公

21、倍数,*程序说明与注释 #include int main() int a,b,num1,num2,temp; printf(“Input a /*输出最小公倍数*/ ,年龄几何,张三、李四、王五、刘六的年龄成一等差数列，他们四人的年龄相加是26，相乘是880，求以他们的年龄为前4项的等差数列的前20项。,年龄几何,*问题分析与算法设计 设数列的首项为a，则前4项之和为“4*n+6*a“,前4 项之积为“n*(n+a)*(n+a+a)*(n+a+a+a)“。同时“1=a=4“,“1=n=6“。可采用穷举法求出此数列。,年龄几何,*程序说明与注释 #include int main() int

22、n,a,i; printf(“The series with equal difference are:n“); for(n=1;n=6;n+) /*公差n取值为16*/ for(a=1;a=4;a+) /*首项a取值为14*/ if(4*n+6*a=26 /*输出前20项*/ *运行结果 The series with equal difference are: 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59,爱因斯坦的数学题,爱因斯坦出了一道这样的数学题： 有一条长阶梯，若每步跨2阶，则最最后剩一阶，若每步跨3 阶，则最后剩

23、2阶，若每步跨5阶，则最后剩4阶，若每步跨6阶则最后剩5阶。只有每次跨7阶，最后才正好一阶不剩。请问这条阶梯共有多少阶？,爱因斯坦的数学题,*问题分析与算法设计 根据题意，阶梯数满足下面一组同余式： x1 (mod2) x2 (mod3) x4 (mod5) x5 (mod6) x0 (mod7),爱因斯坦的数学题,*程序说明与注释 #include int main() int i=1; /*i为所设的阶梯数*/ while(!(i%2=1) *运行结果 Staris_number=119,爱因斯坦的数学题,*问题的进一步讨论 此题算法还可考虑求1、2、4、5的最小公倍数n，然后判t(t为n-1)0(mod7)是否成立，若不成立则t=t+n,再进行判别，直至选出满足条件的t值。请自行编写程序实现,中国剩余定理,宋. 秦九韶 “大衍求一术” 三人同行七十稀 五树梅花廿一枝 七子团圆正半月 除百零五便得知 从中国剩余定理求出的数只是要求的最小解，而候选解有无穷多个。 67=1*70+2*21+4*15-105 “今有一物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”,