C语言-进制转化及高精度加法.ppt

1、ACM程序设计,福州大学至诚学院 冯新,第七讲,进制转化 及高精度加法,数制概念,数制，是使用一组数字符号来表示数的体系。一个理想的记数系统能够：有效地描述一组数（例如，整数、实数）;所有的数对应唯一的表示（至少有一个标准表示法）。 记数系统可以按照进位制，可分为十进制、二进制、八进制等,问题一,输入一个不大于231的10进制正整数，将其转化为2进制。 输入数据有多组，以EOF结束。,演示（将十进制250转化为2进制）,250 / 2 = 125 0 = 11111010 125 / 2 = 62 1 62 / 2 = 31 0 31 / 2 = 15 1 15 / 2 = 7 1 7 / 2

2、 = 3 1 3 / 2 = 1 1 1 / 2 = 0 1 ,#include #include int main() int a,b,i,j; char s35,*p; while(scanf(%d, ,举一反三,输入两个整数n,m,其中2=m10,n为十进制数，将n转化为m进制数。 输入数据有多组，以EOF结束。,问题二,输入一个不大于231的10进制正整数，将其转化为16进制。 以A表示10 B表示11 . F表示15 输入数据有多组，以EOF结束。,#include #include int main() int a,b,i,j; char s35,*p; while(scanf(%

3、d, ,问题三,输入一个长度不大于32位的二进制正整数，将其转化为十进制。（转化后的十进制数范围不会超过int型） 输入数据有多组，以EOF结束。,问题分析,二进制数转换为十进制数 二进制数第0位的权值是2的0次方，第1位的权值是2的1次方，第2位的权值是2的2次方,演示（将二进制数：0110 0100，转换为10进制）,第0位 0 * 20 = 0 第1位 0 * 21 = 0 第2位 1 * 22 = 4 第3位 0 * 23 = 0 第4位 0 * 24 = 0 第5位 1 * 25 = 32 第6位 1 * 26 = 64 第7位 0 * 27 = 0 对等式右边求和得： 0110 0

4、100(2)=100(10),#include #include int main() char s33; int i,ans,t; while(scanf(%s,s)!=EOF) ans=0; for(i=strlen(s)-1,t=1;i=0;i-,t*=2) ans+=t*(si-0); printf(%dn,ans); return 0; ,高精度概念,在某些计算中，参与运算的数的范围大大超出了标准数据类型（int,long long）能表示的范围的运算，例如求两个长度1000位的整数的和。这个时候要怎么办？,于是，我们想到了办法，将这个数字拆开，拆成一位一位的存储到一个数组中，用一个

5、数组去表示一个数字，这样表示的数字就被称为高精度数。 例如将123456789012（逆序存）存入int 型数组a中为,例题,Input 输入两个大整数a和b，每个整数的长度将不会超过1000. 输入数据有多组，以EOF结束 Output 对于每个测试案例,你要输出a+b。每组一行,Sample Input 1 2 112233445566778899 998877665544332211 Sample Output 3 1111111111111111110,解题思路:,最基础的高精度题。 解题过程分为以下几步： 1.定义相关变量及用字符串数组读入高精度数 2.将字符串数组转化为int数组

6、3.做加法及处理进位 4.输出,char Sa1005,Sb1005; int Ia1005,Ib1005,i,j,k,len1,len2;,1.用字符串数组读入高精度数,Sa和Sb用于读入大数a和大数b Ia和Ib用于存储转化后的大数的每一位,for(i=0;i1005;i+) Iai=Ibi=0; /对两个整型数组进行初始化 scanf(%s%s,Sa,Sb); /读入大数a b,2.将字符串数组转化为int数组,len1=strlen(Sa); for(i=len1-1,j=0;i=0;i-) Iaj+=Sai-0; len2=strlen(Sb); for(i=len2-1,j=0;i

7、=0;i-) Ibj+=Sbi-0; /注意，这里将字符型的每一位存入int数组时， /采取倒序存储，即Ia0存储大数的各位， /Ia1存储十位.便于做加法是各数位的对齐,3.做加法及进位,k=len1len2?len1:len2;/k为两个串中的较长的一个 for(i=0;ik;i+) Iai+=Ibi; for(i=0;i=k;i+) Iai+1+=Iai/10; Iai%=10; if(Iak!=0) k+; /这行考虑最高位数否进位，如有进位， /这两大数的长度会比输入的两个串大1,4.输出,for(i=k-1;i=0;i-) printf(%d,Iai); /int数组采取倒序存储，所以这里要对int数组采取倒序输出,int main() char Sa1005,Sb1005; int Ia1005,Ib1005,t,i,j,k,len1,len2; while(scanf(%s%s,Sa,Sb) for(i=0;i=0;i-) Iaj+=Sai-0; len2=strlen(Sb); for(i=len2-1,j=0;i=0;i-) Ibj+