[语文]算法案例彭飞.ppt

为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数. 例如十进制的133，写成133(10) 七进制的13，写成13(7)；二进制的10，写成10(2) 一般地，若k是一个大于1的整数，那么以k 为基数的k进制可以表示为一串数字连写在一起 的形式： 3、十进制的构成 十进制由两个部分构成 例如：3721 其它进位制的数又是如何的呢？ 第一、它有0～9十个数字； 第二、它有“数位”，即从右往左为个位、十位、百位、千位等等。 (用10个数字来记数，称基数为10) 表示有：1个1，2个十， 7个百即7个10的平方，3个千即3个10的立方 十进制：“满十进一” 探究： K进制数化为十进制数公式 二进制与十进制的转换 1、二进制数转化为十进制数 例1：将二进制数110011(2)化成十进制数。 解： 根据进位制的定义可知 所以，110011（2）=51． 44 1 例2:把89化为二进制的数. 我们可以用下面的除法算式表示除2取余法: 2 89 余数 2 22 0 2 11 0 2 5 1 2 2 1 2 1 0 2 0 1 把算式中各步所得的余数从下到上排列,得到 89=1011001(2). 这种方法也可以推广为把十进制数化为k进制数的算法,称为除k取余法. 2.十进制数化为二进制数： 例1：把89化为五进制数。 3、十进制转换为其它进制 解： 根据除k取余法 以5作为除数，相应的除法算式为： 所以，89=324（5） 89 5 17 5 3 5 0 4 2 3 余数 [问题]你会把三进制数10221(3)化为二进制数吗? 解:第一步:先把三进制数化为十进制数: 10221(3)=1×34+0×33+2×32+2×31+1×30 =81+18+6+1=106. 第二步:再把十进制数化为二进制数: 106=1101010(2). ∴10221(3)=106= 1101010(2). 练习： 完成下列进位制之间的转化： （1）102（4）= （10）； （2）23（7）= （10）； （3）137（10）= （6）； （4）123（5）= （7）； （5）1010111（2）= （4）。 小结 一、进位制 1、其它进制数化成十进制数公式 二、各进制数之间的转化（只限整数） 2、十进制数化成k进制数 除k取余法 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 算法案例  知识探究（一）:辗转相除法 思考1:18与30的最大公约数是多少？ 你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. 思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ 思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？ 2146=1813×1+333， 148=37×4+0. 333=148×2+37， 1813=333×5+148， 8251=6105×1+2146， 6105=2146×2+1813， 大数除以小数，直到余数为0，最后的除数为最大公约数 思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步. 思考5:该算法的程序框图如何表示？ 开始 输入m，n m=n n=r r=0？ 是 输出m 结束 否 求m除以n的余数r 思考6:该程序框图对应的程序如何表述？ INPUT m，n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 开始 输