一些算法.ppt

简单题,一个奇异的三位数,一个自然数的七进制表达式是一个三位数，而这个自然数的九进制表示也是一个三位数，且这两个三位数的数码正好相反，求这个三位数。,一个奇异的三位数,*问题分析与算法设计根据题意可知，七进制和九进制表示的这全自然数的每一位一定小于7，可设其七进制数形式为kji(i、j、k的取值分别为16)，然后设其九进制表示形式为ijk。,一个奇异的三位数,*程序说明与注释#includeint 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 special 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开始取值)，用逆推法可以列出关系式：(i*8+7)*8)+1)*8+1=(2*i*17)+15)*17+4再用试探法求出商i的值。,8除不尽的自然数,*程序说明与注释#includeint 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 number is:1993,有限5位数,个位数为6且能被3整除的五位数共有多少？,有限5位数,*题目分析与算法设计根据题意可知，满足条件的五位数的选择范围是10006、10016。99996。可设基础数i=1000，通过计算i*10+6即可得到欲选的数(i的变化范围是1000999)，再判断该数能否被3整除。,有限5位数,*程序说明与注释#includeint main()long int i;int count=0;/*count:统计满足条件的五位数的个数*/for(i=1000;i9999;i+)if(!(i*10+6)%3)/*判断所选的数能否被3整除*/count+;/*若满足条件则计数*/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。,阶乘尾数零的个数,*程序说明与注释#includeint main()int a,count=0;for(a=5;a=100;a+=5)/循环从5开始，以5的倍数为步长，考察整数+count;/若为5的倍数，计数器加1if(!(a%25)+count;/若为25的倍数，计数器再加1printf(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的数目的算法，使程序可以求出任意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位反序数,*程序说明与注释#includeint main()int i;for(i=1002;i1111;i+)/*穷举四位数可能的值*/if(i%10*1000+i/10%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次方截取最后三位即可。但是由于计算机所能表示的整数范围有限，用这种“正确”的算法不可能得到正确的结果。事实上，题目仅要求最后三位的值，完全没有必要求13的13次方的完整结果。研究乘法的规律发现：乘积的最后三位的值只与乘数和被乘数的后三位有关，与乘数和被乘数的高位无关。利用这一规律，可以大大简化程序。,高次方数的尾数,*程序说明与注释#includeint 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*13The last 3 digits of 13*13 is:253Input X and Y(X*Y):13*20The last 3 digits of 13*20 is:801,求车速,一辆以固定速度行驶的汽车，司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的)，为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少？新的对称数是多少？,求车速,*问题分析与算法设计根据题意，设所求对称数为i，其初值为95589，对其依次递增取值，将i值的每一位分解后与其对称位置上的数进行比较，若每个对称位置上的数皆相等，则可判定i即为所求的对称数。,求车速,*程序说明与注释#includeint main()int 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*思考题将一个数的数码倒过来所得到的新数叫原数的反序数。如果一个数等于它的反序数，则称它为对称数。求不超过1993的最大的二进制的对称数。,可逆素数,求四位的可逆素数。可逆素数指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。,可逆素数,*问题分析与算法设计本题的重点不是判断素数的方法，而是求一个整数的反序数。求反序数的方法是从整数的末尾依次截取最后一位数字，每截取一次后整数缩小10倍，将截取的数字作为新的整数的最后一位（新的整数扩大10倍后加上被截取的数字）。这样原来的整数的数字从低到高被不断地截取，依次作为新的整数从高到低的各位数字。,可逆素数,*程序说明与注释#include#includeint num(int number);int ok(int 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/=10)/按位将整数倒过来，产生反序数 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=0)/若为素数则返回1，否则返回0return 0;return 1;,*思考题求1000以内的孪生素数。孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2称为孪生素数。,回文素数,求不超过1000的回文素数。所谓回文素数是指，对一个整数n从左向右和从由向左读其结果值相同且是素数，即称n为回文素数。,回文素数,*问题分析与算法设计本题的重点不是判断素数的方法，而是求回文整数。构造回文数的方法很多，这里仅介绍一种最简单的算法。实现思路是先求出一个整数的回文数，再判断是否为素数。不超过1000的回文数包括二位和三位的回文数，我们采用穷举法来构造一个整数并求与其对应的反序数，若整数与其反序数相等，则该整数是回文数。,回文素数,*程序说明与注释#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 greater than 1000:11 101 131 151 181 191 313 353 373 383 727 787 797 919 929,素数幻方,求四阶的素数幻方。即在一个4X4 的矩阵中，每一个格填 入一个数字，使每一行、每一列和两条对角线上的4 个数字所组成的四位数，均为可逆素数。,素数幻方,*问题分析与算法设计有了前面的基础，本题应当说是不困难的。最简单的算法是：采用穷举法，设定4X4矩阵中每一个元素的值后，判断每一行、每一列和两条对角线上的4个数字组成的四位数是否都是可逆素数，若是则求出了满足题意的一个解。这种算法在原理是对的，也一定可以求出满足题意的全部解。但是，按照这一思路编出的程序效率很低，在微机上几个小时也不会运行结束。这一算法致命的缺陷是：要穷举和判断的情况过多。,素数幻方,充分利用题目中的“每一个四位数都是可逆素数”这一条件，可以放弃对矩阵中每个元素进行的穷举的算法，先求出全部的四位可逆素数(204个)，以矩阵的行为单位，在四位可逆素数的范围内进行穷举，然后将穷举的四位整数分解为数字后，再进行列和对角线方向的条件判断，改进的算法与最初的算法相比，大大地减少了穷举的次数。,素数幻方,考虑矩阵的第一行和最后一行数字，它们分别是列方向四位数的第一个数字和最后一个数字，由于这些四位数也必须是可逆素数，所以矩阵的每一行和最后一行中的各个数字都不能为偶数或5。这样穷举矩阵的第一行和最后一行时，它们的取值范围是：所有位的数字均不是偶数或5的四位可逆数。由于符合这一条件的四位可逆素数很少，所以这一范围限制又一次减少了穷举的次数。,素数幻方,对算法的进一步研究会发现：当设定了第一和第二行的值后，就已经可以判断出当前的这种组合是否一定是错误的(尚不能肯定该组合一定是正确的)。若按列方向上的四个两位数与四位可逆数的前两位矛盾(不是其中的一种组合)，则第一、二行的取值一定是错误的。同理在设定了前三行数据后，可以立刻判断出当前的这种组合是否一定是错误的，若判断出矛盾情况，则可以立刻设置新的一组数据。这样就可以避免将四个数据全部设定好以后再进行判断所造成的低效。,素数幻方,根据以上分析，可以用伪语言描述以上改进的算法：开始找出全部四位的可逆素数；确定全部出现在第一和最后一行的四位可逆素数；在指定范围 内穷举第一行在指定范围内穷举第二行若第一、第二、三行已出现矛盾，则继续穷举下一个数；在指定范围内穷举第四行判断列和对角方向是否符合题意若符合题意，则输出矩阵；否则继续穷举下一个数；结束,最大公约数和最小公倍数,求任意两个正整数的最大公约数和(GCD)和最小公倍数(LCM),最大公约数和最小公倍数,*问题分析与算法设计手工方式求两个正整数的最大公约数的方法是用辗转相除法，在程序中可以模拟这种方式。,最大公约数和最小公倍数,*程序说明与注释#includeint 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。可采用穷举法求出此数列。,年龄几何,*程序说明与注释#includeint main()int 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 阶，则最后剩2阶，若每步跨5阶，则最后剩4阶，若每步跨6阶则最后剩5阶。只有每次跨7阶，最后才正好一阶不剩。请问这条阶梯共有多少阶？,爱因斯坦的数学题,*问题分析与算法设计根据题意，阶梯数满足下面一组同余式：x1(mod2)x2(mod3)x4(mod5)x5(mod6)x0(mod7),爱因斯坦的数学题,*程序说明与注释#includeint 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“今有一物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”,