Machine World | Math World

记录实验过程

【数据结构】求十进制转二进制的递归算法

【背景】

在计算机中,基本的编码都是以二进制为基础。为此,理解进制转换过程,可以帮助我们更好地理解计算机底层的原理。(本题取自广西师范大学2017年硕士研究生招生考试试题编程题部分。

【源码运行环境】

操作系统:Windows 10

编译环境:Dev C++(基于C99标准)

【原理】

十进制整数转换为二进制整数采用"除2取余,逆序排列"法。

具体做法是:

1、用2整除十进制整数,可以得到一个商和余数;

2、再用2去除商,又会得到一个商和余数;

3、如此进行,直到商为小于1时为止;

4、然后把得到的余数作为二进制数的低位有效位,得到的余数作为二进制数的高位有效位;

5、依次排列起来。

【例子】

以十进制14转换为二进制1110为例:

初始值:14

1:14 / 2 = 7 ————>余0

2:7  /  2 = 3 ————>余1

3:  3  /  2 = 1  ————>余1

4:  1  /  2 = 0  ————>余1

反向输出:1110即为所求。

【源码实现】

/*
* 方法名:converse
* 作用:用于将一个十进制数字转换为二进制数的递归实现
* 参数:sum(商)i(位数)
* 返回值:rest(以int保存的二进制数)
* author: WellLee
* 最后一次修改时间:2018年12月6日 19:02:32
*/
int converse(int sum, int i)
{
	int rest;                  //余数
	if(sum <= 1 ){  //递归结束条件
		return i * sum;    //结束返回值
	}
	rest = sum % 2;            //先取余数
	sum /= 2;                  //求商取整
	rest *= i;                 //进位操作(包括递归部分的i*10)
	return rest + converse(sum, i * 10); // 递归部分
}

【总结】

本文提出了一种利用递归保存结果求二进制转十进制的C语言程序实现,实现该功能的程序并不止一种,仅供参考。也借此机会锻炼了自己关于递归程序设计的思想。

【参考文献】

  • 广西师范大学2016年硕士研究生招生考试《806/826 数据结构》试题

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注