算法与程序实践习题解答2(数制转换)

目录CS21：特殊的四位数1CS22：确定进制3CS23：skew数5CS24：十进制到八进制7CS25：八进制到十进制8CS26：二进制转化为十六进制8CS27：八进制小数（也属于高精度计算）8CS28：二进制数13CS29：回文数（PalindromNumbers）14CS210：设计计算器（BasicallySpeaking）15CS211：18《算法与程序实践》习题解答2——数制转换解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再把十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示转换结果的一位数字。根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数是不等比的。例如在时间表示中，从秒到分采用60进进制；从月到年采用12进制。把一个数值从数制B的表示bmbm-1bm-2...b1转换成十进制表示dndn-1dn-2...d1比较简单。假设数制B中，第i位的基数为basei(1<=i<=m)，直接把basei与bi相乘，然后对全部乘积求和。从十进制表示dndn-1dn-2...d1到bmbm-1bm-2...b1的转换需要分两种情况考虑：数制B中相邻数字的基数是等比关系，即：basei(1<=i<=m)可以表示成Ci-1，其中C是一个常量。将dndn-1dn-2...d1除以C，余数即为b1；将dndn-1dn-2...d1和C相除的结果再除以C，余数即为b2；…；直至计算出为bm止。数制B中相邻数字的基数不等比。需要先判断dndn-1dn-2...d1在数制B中需要的位数m，然后从高位到低位依次计算bm、bm-1、bm-2、...、b1。10级 课堂讲解：CS21CS22CS23 课堂练习：CS24CS25课后作业：CS26CS2809级 第一次课堂讲解：CS21CS22CS23 实验：CS24CS25 第二次课堂讲解：CS26CS210 实验：CS28CS29CS21：特殊的四位数（来源：POJ2196ZOJ2405程序设计方法及在线实践指导（王衍等）例3.4，P140）问题描述：找出并输出所有的4位数（十进制数）中具有如下属性的数：四位数字之和等于其十六进制形式各位数字之和，也等于其十二进制形式各位数字之和。例如：十进制数2991，其四位数字之和2+9+9+1=21。由于2991=1*1728+8*144+9*12+3,其十二进制形式为1893(12),其各位数字之和也为21.但是它的十六进制形式为BAF(16)，其各位数字之和等于11+10+15=36。因此你的程序要舍去2991这个数据。 下一个数2992，其十进制、十二进制、十六进制形式各位数字之和均为22，因此2992符合要求，应该输出来。（只考虑4位数，2992是第一个符合要求的数）输入：本题没有输入。输出：你的程序要求输出2992及其他更大的、满足要求的四位数（要求严格按升序输出），每个数占一行（前后都没有空行），整个输出以换行符结尾。输出中没有空行。输出中的前几行如样例输出所示。样例输入：本题没有输入。样例输出：29922993299429952996299729982999...解题思路： 该题在求解时要用到枚举的算法思想，即枚举所有的四位数（1000-9999），判断其是否满足十六进制、十二进制和十进制形式的各位数之和相等。 这里要注意进制转换方法。将一个十进制数Num转换到M进制，其方法是：将Num除以M取余数，直到商为0为止，存储得到的余数，先得到的余数为低位，后得到的余数为高位进行排序，余数0不能舍去。由于此题需要得到Num在16、12和10进制下各位的和，所以只要累加其余数即可。参考程序：#include<stdio.h>intmain(){ intNum,tmp; for(Num=1000;Num<=9999;Num++) { ints16=0,s12=0,s10=0; tmp=Num; while(tmp)//求其十六进制的和 { s16+=tmp%16; tmp/=16; } tmp=Num; while(tmp)//求十二进制的和 { s12+=tmp%12; tmp/=12; } if(s16!=s12)continue; tmp=Num; while(tmp) { s10+=tmp%10; tmp/=10; } if(s16==s10)printf("%d\n",Num); } return0;}CS22：确定进制（来源：2972，程序设计导引及在线实践（李文新）例3.1P98）问题描述：6*9=42对于十进制来说是错误的，但是对于13进制来说是正确的。即,6(13)*9(13)=42(13)，而42(13)=4*131+2*130=54(10)。你的任务是写一段程序读入三个整数p、q和r，然后确定一个进制B(2<=B<=16)使得p*q=r。如果B有很多选择，输出最小的一个。例如：p=11，q=11，r=121。则有11(3)*11(3)=121(3)因为11(3)=1*31+1*30=4(10)和121(3)=1*32+2*31+1*30=16(10)。对于进制10。有11(10)*11(10)=121(10)。这种情况下，应该输出3。如果没有合适的进制，则输出0。输入：输入有T组测试样例。T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。p、q、r的所有位都是数字，并且1<=p、q、r<=1,000,000。输出：对于每个测试样例输出一行。该行包含一个整数：即使得p*q=r成立的最小的B。如果没有合适的B，则输出0。样例输入：369421111121222样例输出：1330解题思路：此问题很简单。选择一个进制B，按照该进制将被乘数、乘数、乘积分别转换成十进制。然后判断等式是否成立。使得等式成立的最小B就是所求的结果。分别用一个字符型数组存储p、q、r的各位数字符号。先以字符串的方式读入p、q、r，然后按不同的进制将它们转换成成十进制数，判断是否相等。参考程序：#include<stdio.h>#include<string.h>longb2ten(char*x,intb){ intret=0; intlen=strlen(x); inti; for(i=0;i<len;i++) { if(x[i]-'0'>=b)return-1; ret*=b; ret+=x[i]-'0'; } return(long)ret;}intmain(){ intn,b; charp[8],q[8],r[8]; longpb,qb,rb;//用来存储转换为十进制后的结果 scanf("%d",&n); while(n--) { scanf("%s%s%s",p,q,r); for(b=2;b<=16;b++) { pb=b2ten(p,b); qb=b2ten(q,b); rb=b2ten(r,b); if(pb==-1||qb==-1||rb==-1)continue; if(pb*qb==rb) { printf("%d\n",b); break; } } if(b==17)printf("0\n"); } return0;}注意事项：在数制b(2<=b<=16)的表示中，每一位上的数字一定都比b小。每读入一组数据后，需要根据其中的数字，判断b的下限。在参考程序的b2ten函数中，如果字符串x中存储的数字比b大、或者与b相等，则返回-1，表明：按照数制b，x中存储的表示形式是非法的，因此b不可能是所求的值。检查：在未找到合适的b时，是否输出0。CS23：skew数（来源：2973，程序设计导引及在线实践（李文新）例3.2P101）问题描述：在skewbinary表示中，第k位的值xk表示xk*(2k+1-1)。每个位上的可能数字是0或1，最后面一个非零位可以是2，例如,10120(skew)=1*(25-1)+0*(24-1)+1*(23-1)+2*(22-1)+0*(21-1)=31+0+7+6+0=44.前十个skew数是0、1、2、10、11、12、20、100、101以及102。输入：输入包含一行或多行，每行包含一个整数n。如果n=0表示输入结束，否则n是一个skew数。输出：对于每一个输入，输出它的十进制表示。转换成十进制后，n不超过231-1=2147483647。输入样例：1012020000000000000000000000000000010100000000000000000000000000000011100111110000011100001011011020000输出样例：44214748364632147483647471041110737解题思路1：skew数的相邻位上，基数之间没有等比关系。计算每一位的基数后，再把一个skew数转换成十进制表示就很简单。对于长度为k的skew数，最后一位数字的基数为2k-1。由于转换成十进制后，n不超过231-1，因此输入skew数的最大长度不超过31。用一个整型数组base[31]，依次存储skew数最末位、倒数第2位、…..、第31位的基数值。使用这个数组，把每个skew数转换成对应的十进制数。base[0]=1base[k]=2k+1-1=2*(2k-1)+1=2*base[k-1]+1参考程序1：#include<stdio.h>#include<string.h>intmain(){ inti,k,base[31],sum; charskew[32]; base[0]=1; for(i=1;i<31;i++) base[i]=2*base[i-1]+1; while(1) { scanf("%s",skew); if(strcmp(skew,"0")==0) break; sum=0; k=strlen(skew); for(i=0;i<strlen(skew);i++) { k--; sum+=(skew[i]-'0')*base[k]; } printf("%d\n",sum); } return0;}解题分析2： 很明显，对输入文件中的skew二进制数，不能采用整数形式（int）读入，必须采用字符数组。那么需要定义多长的字符数组呢？题目中提到“输入文件中的skew二进制数最大值对应到十进制数为231-1=2147483647” 在把skew二进制数转换成十进制时，只需把每位按权值展开求和即可。参考程序2：#include<stdio.h>#include<string.h>#include<math.h>intmain(){ charstr[40];//读入的每个skew二进制数 while(scanf("%s",str)!=EOF) { intlen=strlen(str); intnum=0;//对应的十进制数 if(len==1&&str[0]=='0')break; intweight=2;//每位的权值为weight-1 inti; for(i=len-1;i>=0;i--) { num+=(str[i]-'0')*(weight-1); weight*=2; } printf("%d\n",num); } return0;}CS24：十进制到八进制（来源：2734，程序设计导引及在线实践（李文新）练习1P102）问题描述：把一个十进制正整数转化成八进制输入：一行，仅含一个十进制表示的整数a(0<a<65536)输出：一行，a的八进制表示样例输入：9样例输出：11CS25：八进制到十进制（来源：2735，程序设计导引及在线实践（李文新）练习2P103）问题描述：把一个八进制正整数转化成十进制输入：一行，仅含一个八进制表示的正整数a，a的十进制表示的范围是(0,65536)输出：一行，a的十进制表示样例输入：11样例输出：9CS26：二进制转化为十六进制（来源：2798，程序设计导引及在线实践（李文新）练习3P103）问题描述：输入一个2进制的数，要求输出该2进制数的16进制表示。在16进制的表示中，A-F表示10-15输入：第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000输出：n行，每行输出对应一个输入。样例输入：2100000111样例输出：207解题思路 二进制转换为十六进制从低位开始，每4位转换为一位十六进制。最前面剩余的不足4位的补0补到4位，再转换。CS27：八进制小数（也属于高精度计算）（来源：2765，程序设计导引及在线实践（李文新）练习4P103）问题描述：八进制小数可以用十进制小数精确的表示。比如，八进制里面的0.75等于十进制里面的0.963125(7/8+5/64)。所有小数点后位数为n的八进制小数都可以表示成小数点后位数不多于3n的十进制小数。你的任务是写一个程序，把(0,1)中的八进制小数转化成十进制小数。输入：输入包括若干八进制小数，每个小数占用一行。每个小数的形式是0.d1d2d3...dk，这里di是八进制数0...7，而且已知0<k<15。输出：对于每个输入的八进制小数，输入如下形式的一行0.d1d2d3...dk[8]=0.D1D2D3...Dm[10]这里左边是输入的八进制小数，右边是相等的十进制小数。输出的小数末尾不能有0，也就是说Dm不等于0。样例输入：0.750.00010.01234567样例输出：0.75[8]=0.953125[10]0.0001[8]=0.000244140625[10]0.01234567[8]=0.020408093929290771484375[10]提示：如果你使用字符串读取八进制小数，你可以使用如下的形式中止输入charoctal[100];while(cin>>octal){...}d1d2d3...dk[8]=(d1+(d2+(d3+(...dk*0.125...)*0.125)*0.125)*0.125[10]=(d1*103*(k-1)+(d2*103*(k-2)+(d3*103*(k-3)+(...dk*125...)*125)*125)*125*10-3*k[10]D1D2D3...Dm中小数点后最多可以有42位数字。用一个数组来存储D1D2D3...Dm，每个元素存储一位数字。参考程序1：（网上直接粘贴来的）#include<stdio.h>#include<string.h>intset[15][50],output[50],op[50];voidinit(){ inti,j,sum=0; memset(set,0,15*50*sizeof(int)); set[0][2]=1; for(i=1;i<15;i++) { sum=0; for(j=2;j<50;j++) { sum*=10; sum+=set[i-1][j]; if(sum>=8) { set[i][j]=sum/8; sum%=8; } } }}voidadd(int*output,int*op){ inti; for(i=49;i>=0;i--) { output[i]+=op[i]; if(output[i]>=10) { output[i]-=10; output[i-1]++; } }}voidmulti(intn,intm){ inti; memset(op,0,50*sizeof(int)); for(i=0;i<n;i++) add(op,set[m]);}intmain(){ init(); inti,len,flag; charinput[20]; while(scanf("%s",input)!=EOF) { memset(output,0,50*sizeof(int)); len=strlen(input); for(i=2;i<len;i++) { multi((input[i]-'0'),i-1); add(output,op); } for(i=49;i>=0;i--) if(output[i]) break; flag=i; printf("%s[8]=0.",input); for(i=3;i<=flag;i++) printf("%d",output[i]); printf("[10]\n"); } return0;}参考程序2（寿浙威）：#include<stdio.h>#include<string.h>#definemaxn100;intmain(){inti;charstr[20],res[60];while(scanf("%s",str)!=EOF){doubleexp=1;doublesum=0.0;for(i=2;str[i];i++){exp*=8;sum+=(str[i]-48)/exp;}intlen=strlen(str)-2;inttmp;exp=10;//printf("%lf\n",sum);printf("%s[8]=0.",str);for(i=0;i<len*3;i++){sum*=exp;tmp=(int)sum;sum-=tmp;res[i]=tmp+'0';//printf("%c",res[i]);}//printf("\n");intk=len*3;while(!(res[i]-'0'))k--;for(i=0;i<k;i++)printf("%c",res[i]);printf("[10]\n");}return0;}解题分析2： 八进制小数转换成十进制小数，其原理本来是按权值展开，小数点后第1位的权值为8-1=0.125，第2位的权值为8-2=0.015625.因此0.75[8]=7*0.125+5*0.015625=0.953125。但在本题中，如果按照这种思路去求解，不容易实现。 更好的方法是转换成除法运算，小数点后第1位的权值为8-1，相当于除以8；第2位的权值为8-2，相当于除以两次8，……。具体过程为：循环除以8，即从八进制小数的最后一位开始除以8，把得到的结果加到前一位，在除以8，……。一直到小数点后第1位为止。假设读入的八进制为0.d1d2d3…dn，转换后的十进制为0.D1D2D3…Dm，则循环除以8的公式为： 0.D1D2D3…Dm=（d1+(d2+(d3+…(dn-1+dn/8)/8…)/8)/8）/8 例如，对八进制小数0.123[8]=(1+(2+3/8)/8)/8.具体过程为：注意得到的十进制小数都不保留前面的0及小数点。 (1)先读入最后一位num=3，按照除法运算规则进行除8运算，不足的就补0，相当于乘以10，直到余数为0。这样得到结果为375，实际上表示的是0.375，即0.3[8]对应的十进制小数。 （2）接下来读入前一位num=2，这时要求的是2.375/8，转换成求2375/8，得到的结果为296875，实际上是0.296875，即0.23[8]对应的十进制小数。 反复进行下去，直到求完所有的位数。参考程序3：#include<stdio.h>#include<string.h>constintMAX_LENGTH=20;intmain(){ charsrc[MAX_LENGTH];//读入来的八进制小数（字符形式） inti,j;//freopen("in.txt","r",stdin); while(scanf("%s",src)!=EOF) { chardest[MAX_LENGTH*4]={'0'};//存放转化后的十进制数（无0.） intnum;//读取处理的每个八进制位（整数形式） intindex=0;//前一个八进制位除以8后dest数组中的位数 intlen=0;//当前这个八进制位除以8后dest数组中的位数 inttemp;//当前这个八进制位与前一位运算结果的每一位组合得到的值 for(i=strlen(src)-1;i>1;i--)//刨掉最前面的0和小数点. { num=src[i]-'0';//取第i位上的八进制数字 for(j=0;j<index;j++)//d1~dn-1的处理 { temp=num*10+dest[j]-'0'; dest[j]=temp/8+'0'; num=temp%8; } while(num)//d1~dn的处理（余数的处理，补0再除直到商为0为止） { num*=10; dest[len++]=num/8+'0'; num%=8; } index=len; } dest[len]='\0'; printf("%s[8]=0.%s[10]\n",src,dest); } return0;}CS28：二进制数（来源：ZOJ1383，程序设计方法及在线实践指导（王衍等）练习3.1P142）问题描述：给定一个正整数n，要求输出对应的二进制数中所有数码“1”的位置。注意最低位为第0位。例如13的二进制形式为1101，因此数码1的位置为：0,2,3.输入：输入文件中的第1行为一个正整数d，表示输入文件中测试数据的个数，1<=d<=10，接下来有d个测试数据。每个测试数据占一行，只有一个整数n，1<=n<=106。输出：输出包括d行，即对输入文件中的每个测试数据，输出一行。第i行，1<=i<=d，以升序的顺序输出第i个测试数据中的整数的二进制形式中所有数码1的位置，位置之间有1个空格，最后一个位置后面没有空格。样例输入：213127样例输出：0230123456提示：对输入的整数n，依次用2去整除，用变量pos充当计数器（代表二进制的位），如果得到的余数为1，则输出pos，否则不输出；pos的初值为0，每次将n除以2后，pos自增1.题目要求两个位置之间有1个空格，最后一个位置之后没有空格，解决方法是在第1个位置之前不输出空格，然后再接下来的所有数码“1”的位置之前输出1个空格。CS29：回文数（PalindromNumbers）（来源：ZOJ1078，程序设计方法及在线实践指导（王衍等）例7.1P234）问题描述：我们称一个数是一个回文数，当且仅当它从左往右读和从右往左读起来都是一样的。比如75457就是回文数。 当然，这种性质取决于这个数是在什么进制下，比如17在十进制下不是一个回文数，但在二进制下则是一个回文数（10001）。 这道题的目的是验证给定的一组数分别在2进制~16进制下是否是回文数。输入：输入文件包含了若干个整数，每个整数n都是在十进制下给出的，每个整数占一行，0<n<50000。输入文件以0表示结束。输出：当该整数在某些进制下是回文数，则输出“Numberiispalindrominbasis”，分别列出这些基数，其中i是给定的整数。如果该整数在2~16进制下都不是回文数，则输出“Numberiisnotpalindrom”。样例输入：17190样例输出：Number17ispalindrominbasis2416Number19isnotapalindrom解题分析： 对读入的每个十进制数number，依次判读number在2~16进制下是否为回文数并输出如果都不是则输出“Numberiisnotpalindrom”。 在判读十进制数number在basis进制下是否为回文数时，首先要将十进制数number转换为basis进制，即将number除以basis取余数。存储余数时要注意以下两个问题： （1）十进制以上的进制中的数码除了0~9外，还有字母，例如十六进制的数码为0~9，以及A、B、C、D、E、F。那么是否需要将得到的余数以字符形式存放呢？ （2）进制转换时，得到的余数排列顺序是：先得到的余数位于低位，后得到的余数位于高位，是否有必要严格按照这个顺序（即与余数产生顺序相反的顺序）存储得到的余数？ 对于第一个问题，答案是不需要，更方便的做法是在取余数时把得到的余数以整数形式存放到一个整型数组里。例如，十进制的2847，在15进制下得到的余数为12,9和12.其中第1个和第3个余数在15进制下为字符C，但我们并不需要得到真正的15进制数，只需要判断各位数码中的某些位是否相等。 对于第二个问题，答案也是不需要的。因为如果一个数是回文数，则各位逆序后仍然是回文数，因此在取余时可以按先后顺序存放到整型数组里，然后判断数组中的数是否构成回文数。CS210：设计计算器（BasicallySpeaking）（来源：POJ1546ZOJ1334，程序设计方法及在线实践指导（王衍等）练习7.1P241）问题描述：某个公司最近邀请你设计一个计算器。作为计算机科学家，你建议将这个计算器设计得灵巧一点，使得它能在各种进制之间进行转换。公司认为这是一个很好的想法，并要求你拿出实现进制转换的算法原型。公司经理告诉你，该计算器有以下特征： （1）它的显示器有7位； （2）它的按键除了数字0到9外，还有大写字母A到F； （3）它支持2~16进制。输入：输入文件中的每一行要实现一次进制转换。每一行有3个数，第1个数是A进制下的一个整数，第2个数就是A，第3个数是B，要实现的是将第1个数从A进制转换到B进制下。这3个数的两边可能有一个或多个空格。输入数据一直到文件结尾。输出：实现输入文件中的每次进制转换，转换后的数右对齐到7位显示器。如果转换后的数的位数太多，在7位显示器中显示不下，则输出“ERROR”，也是右对齐到7位显示器。样例输入：111100021011110002162102101310210210131512312421A15212345671016ABCD1615样例输出：1207817657CAERROR1100112D687D071参考程序（zzg）：#include<stdio.h>#include<string.h>longb2ten(char*x,intb);intmain(){ charnumsrc[10],numdest[10];//用来存储读入的数和转换后的数 chartemp[10]; charerror[10]="ERROR"; longnum; intsrc,dest;//转换前的进制和转换后的进制 inti,j; //freopen("in.txt","r",stdin); while(scanf("%s%d%d",numsrc,&src,&dest)!=EOF) { //先把src进制的数转换为10进制数，存放到temp中 num=b2ten(numsrc,src); if(dest==10) { if(num>9999999) printf("%7s\n",error); else printf("%7d\n",num); } else { i=0; while(num) { if(num%dest<10) numdest[i++]=num%dest+'0'; else { switch(num%dest) { case10: numdest[i++]='A'; break; case11: numdest[i++]='B'; break; case12: numdest[i++]='C'; break; case13: numdest[i++]='D'; break; case14: numdest[i++]='E'; break; case15: numdest[i++]='F'; break; } } num/=dest; } numdest[i]='\0'; if(strlen(numdest)>7) printf("%7s\n",error); else//逆序输出 { j=0; for(i=strlen(numdest)-1;i>=