1.3.3算法案例--进位制(复习课) (高中数学人教A版必修三)

算法案例 ——进位制

算法的概念 自然语言 程序框图 算法语句

顺 序 结 构

条 件 结 构

循 环 结 构

顺 序 结 构

条 件 结 构

循 环 结 构

输 入 输 出 语 句

条 件 语 句

赋 值 语 句

循 环 语 句

算法案例辗转相除法与更相减损术

秦九韶算法

进位制

问题1: 编写一个程序框图,把二进制数1111 (2)化为十进制数.开始

b=b+2i-1b=0 i=i+1 否

i>4? i=1是 输出b 结束

问题2: 编写一个程序,把二进制数a4a3a2a1 化为十进制数.

(2)

a4a3a2a1b1=

=a4×23+a3×22+a2 ×21+a1×20 (2)

a1×20 ×21

b2=b1 +a2

bi=bi-1+ai×2i-1

b3=b2 +a3×22b4=b3 +a4×23

开始b=0 i=1输入a的右数第i位数字t

b=b+t*2i-1i=i+1 i>4? 是 输出b 结束 否

b=0 i=1 DO INPUT t b=b+t*2^(i-1) i=i+1 LOOP UNTIL i>4 PRINT b END

K进制数的一般形式： an an 1 a1a0 k 其中

an , an 1 , a1 , a0 N 0 an k ,0 an 1, , a1, a0 k注意：最高位不能是0

一、K进制数转化成十进制数的方法： 方幂法 先将k进制数写成各位上数字与 k的幂的乘积之和的形式，再按照 十进制数的运算规则计算出结果

(共n位)

a=

an an 1 a2 a1( k ) an 1 kn 2

an k

n 1

a2 k a1 k1

0

=b

在此过程中有没有反复操作的步骤 ——循环结构 b=0 变量及其初始值 i=1t=a MOD10 循环体

b=b+t*k^(i-1)a=a\10

i=i+1控制条件

i>n或i<=n

例1、设计一个算法，将k进制数a(共有n位)转换为十进制 数b。

(1)算法步骤:第一步，输入a,k和n的值； 第二步，将b的值初始化为0,i的值初始化为1; 第三步，b=b+ai*ki-1, i=i+1 第四步，判断i>n是否成立.若是,则执行第五步,否则, 返回第三步； 第五步，输出b的值.

程 序 框 图

① 开始 把a的右数第i位数字赋给t

输入a,n,k

b=b+t*ki-1b=0 i=1① i=i+1

i>n?是 输出b 结束

否

INPUT “a,k,n=“a,k,nb=0 i=1

t=a MOD 10DO b=b+t*k^ (i-1) a=a\10 t=a MOD 10

i=i+1LOOP UNTIL i>n PRINT b END

二、十进制数化k进制数的方法：除k取余法(从下到上)练习：将137转化成6进制数为：

345(6)100110(2)

将38转化成2进制数为：

十进制转换为二进制把49化为二进制数 有没有反 复执行的 步骤49 2 24 2 12 2 6 2 3 2 2 1 0 余数 10 0 0 1 1

注意： 1.最后一步商为0, 2.将上式各步所得的余数从下到上排列，得到：49=110001(2)

循环结构 (十进制数a转化为k进制数b)变量及其初始值b=0

i=o q=a\k循环体 r=a MOD k b=b+r*10^i i=i+1 a=q 控制条件 q=0或q≠0

例2、设计一个程序，实现“除k取余法”。(1)、 算法步骤： 第一步，给定十进制正整数a和转化后的数的基数k; 第二步，求出a 除以k 所得的商q ,余数r; 第三步，把所得到的余数依次从右到左排列， 第四步，若q 0, 则a=q,

返回第二步；否则，输出 全部余数r排列得到的k进制

例2、设计一个程序，实现“除k取余法”

(3)程序：

程序框图：

开始 输入a,k

求a除以k的商q

求a除以k的余数r

把得到的余数依次从右到左排列a=q

q=0?输出全部余数r排列得到的k进制数 结束

Input “a,k=”;a,k b=0 i=0 DO q=a\k r=a MOD k b=b+r*10^I i=i+1 a=q LOOP UNTIL q=0 PRINT b END