C语言程序设计100例之(24):数制转换
例24 数制转换
题目描述
请你编一程序实现两种不同进制之间的数据转换。
输入格式
共三行,第一行是一个正整数,表示需要转换的数的进制n(2≤n≤16),第二行是一个n进制数,若n>10则用大写字母a-f表示数码10-15,并且该n进制数对应的十进制的值不超过1000000000,第三行也是一个正整数,表示转换之后的数的进制m(2≤m≤16)。
输出格式
一个正整数,表示转换之后的m进制数。
输入样例
16
ff
2
输出样例
11111111
(1)编程思路。
十进制整数转换为r进制整数的基本方法是:“除r取余”。具体做法为:对于十进制数整数,用r连续除要转换的十进制整数及各次所得之商,直除到商等于0时为止,则各次所得之余数即为所求r进制整数由低位到高位的值。这个过程可以写成一个简单的循环。
一般而言,对于任意的r进制数 an-1an-2…a1a0可以表示为以下和式:
an-1×rn-1 +…+a1×r1+a0×r0 (其中r为基数)
这个和式也称为“按权展开式”。
r进制数转换为十进制数的基本方法是将r进制数的各位按权展开相加即可。
本例的思路是:将输入的n进制整数按权值展开后转换为十进制整数,再将所得的十进制整数采用“除m取余”转换为m进制整数即可。
(2)源程序。
#include <stdio.h>
int main()
{
char table[17]="0123456789abcdef";
int n,m;
char s[33];
scanf("%d",&n);
scanf("%s",s);
scanf("%d",&m);
int num=0;
for (int i=0;s[i]!='\0';i++) // n进制整数按权值展开后转换为十进制整数num
{
if (s[i]>='0' && s[i]<='9')
num=num*n+s[i]-'0';
else
num=num*n+s[i]-'a'+10;
}
int digit[32],cnt=0;
do { // 十进制整数采用“除m取余”转换为m进制整数
digit[cnt++]=num%m;
num=num/m;
} while (num!=0);
for (int i=cnt-1;i>=0;i--)
printf("%c",table[digit[i]]);
printf("\n");
return 0;
}
习题24
24-1 高低位交换
本题选自洛谷题库 (https://www.luogu.org/problem/p1100)。
题目描述
给出一个小于232的正整数。这个数可以用一个32位的二进制数表示(不足32位用0补足)。我们称这个二进制数的前16位为“高位”,后16位为“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多少(用十进制表示)。
例如,数1314520用二进制表示为00000000000101000000111011011000(添加了11个前导0补足为32位),其中前16位为高位,即0000000000010100;后16位为低位,即0000111011011000。将它的高低位进行交换,我们得到了一个新的二进制数00001110110110000000000000010100。它即是十进制的249036820。
输入格式
一个小于232的正整数。
输出格式
将新的数输出
输入样例
1314520
输出样例
249036820
(1)编程思路。
将输入的十进制整数采用“除2取余”转换为二进制整数,再将所得的二进制整数依照低16位在前高16位在后的方式按权值展开后转换为十进制整数即可。
(2)源程序。
#include <stdio.h>
int main()
{
unsigned int num;
scanf("%d",&num);
int digit[32]={0},cnt=0;
do { // 十进制整数采用“除2取余”转换为二进制整数
digit[cnt++]=num%2;
num=num/2;
} while (num!=0);
int i;
for (i=15;i>=0;i--) // 先将低16位按权值展开
num=num*2+digit[i];
for (i=31;i>=16;i--) // 再将高16位按权值展开
num=num*2+digit[i];
printf("%u\n",num);
return 0;
}
24-2 进制转换
本题选自洛谷题库 (https://www.luogu.org/problem/p1017)。
题目描述
一般说来,任何一个正整数r或一个负整数-r都可以被选来作为一个数制系统的基数。如果是以r或-r为基数,则需要用到的数码为 0,1,....r-1。例如,当r=7时,所需用到的数码是0,1,2,3,4,5和6,这与其是r或-r无关。如果作为基数的数绝对值超过10,则为了表示这些数码,通常使用英文字母来表示那些大于9的数码。例如对16进制数来说,用a表示10,用b表示11,用c表示12,用d表示13,用e表示14,用f表示15。
在负进制数中是用-r作为基数,例如-15 (十进制)相当于110001 (-2进制),并且它可以被表示为2的幂级数的和数:
110001=1×(−2)5 +1×(−2)4 +0×(−2)3 +0×(−2)2 +0×(−2)1 +1×(−2)0。
设计一个程序,读入一个十进制数和一个负进制数的基数,并将此十进制数转换为此负进制下的数:-r∈{-2,-3,-4,...,-20}
输入格式
输入包括多组测试数据。
每组测试数据占一行,每行有两个输入数据。
第一个是十进制数n (−32768≤n≤32767)
第二个是负进制数的基数-r。
输出格式
结果显示在屏幕上,相对于输入,应输出此负进制数及其基数,若此基数超过10,则参照16进制的方式处理。
输入样例
30000 -2
-20000 -2
28800 -16
-25000 -16
输出样例
30000=11011010101110000(base-2)
-20000=1111011000100000(base-2)
28800=19180(base-16)
-25000=7fb8(base-16)
(1)编程思路。
我们知道十进制整数是采用“除r取余”转换为r进制整数的,对于负基数(-r)同样如此。
先看问题描述中的例子-15转换为-2进制数。在c语言中“除r取余”运算过程为:
被除数 |
除数 |
商 |
余数 |
-15 |
-2 |
7 |
-1 |
7 |
-2 |
-3 |
1 |
-3 |
-2 |
1 |
-1 |
1 |
-2 |
0 |
1 |
这里余数出现了负数,需要将余数转换成正数,怎么处理呢?
因为, 被除数=商*除数+余数=商*除数+除数+余数-除数=(商+1)*除数+(余数-除数)。因此,若余数为负时,只需要将商+1,余数-除数,就可以将余数转换为正数。
被除数 |
除数 |
商 |
余数 |
校正的商 |
校正余数 |
-15 |
-2 |
7 |
-1 |
8 |
1 |
8 |
-2 |
-4 |
0 |
|
|
-4 |
-2 |
2 |
0 |
|
|
2 |
-2 |
-1 |
0 |
|
|
-1 |
-2 |
0 |
-1 |
1 |
1 |
1 |
-2 |
0 |
1 |
|
|
因此,-15转换为-2进制数为110001。
(2)源程序。
#include <stdio.h>
int main()
{
char table[21]="0123456789abcdefghij";
int num,r;
while (scanf("%d%d",&num,&r)!=eof)
{
printf("%d=",num);
int digit[32]={0},cnt=0;
do {
int t=num%r;
num=num/r;
if (t<0) {t=t-r; num++; }
digit[cnt++]=t;
} while (num!=0);
int i;
for (i=cnt-1;i>=0;i--)
printf("%c",table[digit[i]]);
printf("(base%d)\n",r);
}
return 0;
}
24-3 彩灯和按钮
问题描述
有一个机器,它有 m(2≤m≤30) 个彩灯和一个按钮。每按下按钮时,最右边的彩灯会发生一次变换。变换为:①如果当前状态为红色,它将变成绿色;②如果当前状态为绿色,它将变成蓝色;③如果当前状态为蓝色,它将变成红色,并且它左边的彩灯(如果存在)也会发生一次变换。初始状态下所有的彩灯都是红色的。
输入格式
输入包括多组测试,第1行给出正整数t(1≤t≤15),表示测试数据的组数。
每组测试数据包括两个整数m(2≤m≤30) 和 n(1≤n<263),分别表示彩灯的个数和按钮被按下的次数。
输出格式
对每组测试数据,按从左到右的顺序输出各彩灯的颜色状态,r 表示红色,g表示绿色,b 表示蓝色。
输入样例
2
3 1
2 3
输出样例
rrg
gr
(1)编程思路。
每按一次按钮都是从最右边的彩灯开始变换,将m个彩灯可以看成一个m位数,最右边的彩灯为其个位数,每按一次按钮可以看成个位数加1。每按三次后从右数第二个彩灯才会变一下,每按9次从右边数第三个彩灯会变换一次,……。
显然,m个彩灯表示的m位数可以看成是一个三进制数,红灯表示0,绿灯表示1,蓝灯表示2,将输入的n转换为3进制数即可。
(2)源程序。
#include <stdio.h>
#include <string.h>
int main()
{
char table[4]="rgb";
int t, m, len;
long long n;
int color[30];
scanf("%d", &t);
while(t--)
{
memset(color, 0, sizeof(color));
scanf("%d%lld", &m, &n);
len = m;
while (n > 0 && m > 0)
{
color[--m] = n % 3;
n /= 3;
}
for (int i=0; i<len; i++)
putchar(table[color[i]]);
putchar('\n');
}
return 0;
}