关于大数除法
最近在九度oj上看了几个关于大数的问题,特意在这里总结一番。 要知道我们要将一个1000多位的十进制数转换为二进制数,是没有哪个类型能装得下的,所以在这里我们的手动模拟辗转相除法。实现将一个很长的十进制数字符串转换成二进制的字符数组。 首先我们来看看这些int,long等等的取值范围,明白它们到底可以存多大,我们才能放心到底什么时候可以用,什么时候不可以用。 ?
? ?
? 具体的转换思想(转载):在数据结构课关于栈的这一章中,我们都学过用“模2取余法”来将一个10进制数转换为一个二进制数,进而可以推广到“模n取余法”,经其转换为n进制(n任意指定)。 确实,这是一个很基础的题目,可你是否想过如果这个10进制数是一个大数(其位数可能上千位,此时用一般数据类型肯定是会溢出的),那么这个问题又如何来求解呢? 当然,也许你会说很简单嘛,自己写一个大数类(当然至少要写一个大数除法才行),或者你用的是Java这种现代化语言,就更轻松了,直接用BigInteger这样的大数类就可以来表示一个大数,进而用书上教的方法来实现。 但是,真的需要用到大数类吗?事实上,“杀鸡焉用牛刀“,我们在纸上模拟一番上述运算后就可以发现,只要做一些小小的改进,就可以在不使用大数的情况下,也可以通过“模n 取余”的原理来实现大数的进制转换的。(当然,整体的思想仍然是“模n取余”原理!!!)。 举个简单的例子,就比如说把10进制数12转换为2进制形式,书上的方法可以用下图来表示
按照 “先余为低位,后余为高位“这条铁律,其结果为1100. 这是书上教我们的常规思路(可惜按这个的话,大数是没法考虑的,因为假如这里不是12,而是一个1000位的大数,由于是是对大数的整体进行取余运算,不使用大数类及其 除法操作,又如何得以进行呢?),可我们的目的是不使用大数类,那么现在我们就来换一个视角来看这个问题,12是一个十位数,十位上是1,个位上是2,按照我们正常的 思维来看,这个计算应该是下面这样的:
那么我们发现在第一轮运算时,十位上的1作为被除数,2作为除数,得到的商是0,余数是1(可以断言只考虑当前这一个数位的计算,余数或是0,或是1,若是1的话,则进 下一数位(这里即对个位进行运算)时,要用1乘上进制(这里是10)再加上下一个数位上的值(这里是2)),即得到运算进入个位时被除数是12,除数是2,得到的商是6, 数是0。第一轮运算的结果是商是06,余数是0. 进入第二轮运算,则上一轮的商6(这里首先要去掉前面多余的0)变成本轮的被除数,如此下去,即可得到每轮的余数。 除数应该是1*10+2 = 12,所以得到的商是6,余数是0,即运算到此时的商是06,然后是第三个数位3,由于上一个数位留下的余数是0,所以此时被除数就是3,。。。如此下去 就完成第一轮的运算,这一轮完毕后,需要把得到的商变成下一轮的被除数,继续上述的运算,直到被除数为0才停止。
1 /*题目1138:进制转换 2 题目描述: 3 将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。 4 */ 5 #include "stdafx.h" 6 #pragma warning(disable:4996) 7 #include <stdio.h> 8 #include <cstring> 9 #include <string> 10 #include <iostream> 11 using namespace std; 12 char binvec[1001]; 13 14 15 void tenToBin(string str) 16 { 17 int j=0; 18 int sum=1; 19 int len=str.size(); 20 21 while (sum) 22 { 23 sum=24 for (int i=0;i<len;++i) 25 { 26 int temp=(str[i]-'0')/2; 27 sum+=temp; 28 if (i==len-1) 29 { 30 binvec[j++]=(str[i]-')%2+'; 31 }else 32 { 33 str[i+1]=str[i+1]+(str[i]-2*10;//算出下一个被除数 34 } 35 记录该次得出的商 36 str[i]=temp+37 } 38 } 39 40 41 } 42 void resout() 43 { 44 逆序 45 int len1=strlen(binvec); 46 0,j=len1-1;i<len1/2;++i,--j) 47 { 48 char temp=binvec[j]; 49 binvec[j]=binvec[i]; 50 binvec[i]=temp; 51 } 52 cout<<binvec<<endl; 53 } 54 int main() 55 { 56 string str; 57 while(cin>>str) 58 { 59 memset(binvec, |