【题目描述】
Problem D - 负权数
Description
当我们写一个十进制正书时，其值可以用各位的数码乘以10 的幂来表示。例如：
123 = 1×102 + 2×101 + 3×100
一般来说，对于R 进制数N，其绝对值可以用各位的数码乘以R 的幂：
N = an×Rn+ an-1×Rn-1 + ... + a0×R0
来表示。这里的R 可以是正书也可以是负数。当R 是负数时，我们称之为负权数。不论R是正数还是负数，我们都采用{0, 1, ... , |R|-1}这R 个数码来表示R 进制数各个位。如果|R|>10,我们还将使用大写字母表示数码。例如，对16 进制数来说，A 表示10（
十进制），
B 表示11（十进制），……，F 表示15（十进制）。
使用负权数的一个好处就是在表示负数时，我们不需要用到负号“-”。举例来说，10
进制数-15 用-2 进制数来表示就是110001
:
-15 = 1×(-2)5 + 1×(-2)4 + 0×(-2)3 + 0×(-2)2 + 0×(-2)1 + 1×(-2)0
请设计一个程序读入10 进制数和负数R，输出这个10 进制数的R 进制的形式。
输入数据有多组，以一行“0 0”结束。
Sample Input
30000 -2
-20000 -2
28800 -16
-25000 -16
Sample Output
11011010101110000
1111011000100000
19180
7FB8
【解题思路】
G题与这个题目很相像。
对于一个正数，我们可以先转换为R进制数，再将R进制数转化为－R进制数。知道这种办法，后面就好办了：对于奇数位（从后面数），－R与R进制代表的值是一样的，对于偶数位，可以用高位减当前位表示（如：(-R)^3 * a = (-R)^4 – R^3 * (R-a)）。
再观察负数，可以发现要转换的是奇数位。
具体实现的时候就是先将一个数表示为R进制，然后在对所有的偶数位进行变换，并且注意进位的处理。对于负数，先变成他的相反数，然后对所有的奇数位进行变换。我在实现时直接用tag标记要转换的数，分别用0、1分别表示正数、负数，然后利用数的奇偶进行转换。
【题目代码】
1 /*
2 author:littlekid
3 created time: 2008-1-21
4 description:
5 */
6 # include <iostream>
7 using namespace std;
8
9 int main()
10 {
11 int n, r;
12 int tmp;
13 int a[ 102 ];
14 int k, tag, i;
15 while (true)
16 {
17 scanf("%d %d", &n, &r);
18 if (n == 0 && r == 0) break;
19 if (n == 0) // 0 is special
20 {
21 printf("0\n");
22 continue;
23 }
24 r *= -1;
25 //label the number: a negative or positive number?
26 tag = 1;
27 if (n < 0)
28 {
29 tag = 0;
30 n *= -1;
31 }
32 //translate a decimal number into R-representation number
33 k = 0;
34 memset(a, 0, sizeof(a));
35 while ( n != 0 )
36 {
37 tmp = n % r;
38 a[k++] = tmp;
39 n /= r;
40 }
41 //translate a R-representation number into a -R-representation number
42 i=0;
43 while (i<k || a[i])
44 {
45 if (a[i] >= r)
46 {
47 a[i] %= r;
48 a[i+1] ++;
49 }
50
51 if (i%2==tag && a[i])
52 {
53 a[i] = r-a[i];
54 a[i+1] ++;
55 }
56 i ++;
57 }
58 //output the answer
59 for (i = i-1; i >= 0; i --)
60 {
61 if (a[i] > 9) printf( "%c", 'A'+a[i]-10);
62 else printf("%d", a[i]);
63 }
64 printf("\n");
65 }
66 return 0;
67 }
posted on 2008-01-22 14:54
R2 阅读(298)
评论(0) 编辑 收藏 引用 所属分类:
Problem Solving