【題目描述】
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 閱讀(303)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving