【題目描述】
Problem D - 負權(quán)數(shù)
Description
當我們寫一個十進制正書時，其值可以用各位的數(shù)碼乘以10 的冪來表示。例如：
123 = 1×102 + 2×101 + 3×100
一般來說，對于R 進制數(shù)N，其絕對值可以用各位的數(shù)碼乘以R 的冪：
N = an×Rn+ an-1×Rn-1 + ... + a0×R0
來表示。這里的R 可以是正書也可以是負數(shù)。當R 是負數(shù)時，我們稱之為負權(quán)數(shù)。不論R是正數(shù)還是負數(shù)，我們都采用{0, 1, ... , |R|-1}這R 個數(shù)碼來表示R 進制數(shù)各個位。如果|R|>10,我們還將使用大寫字母表示數(shù)碼。例如，對16 進制數(shù)來說，A 表示10（
十進制），
B 表示11（十進制），……，F 表示15（十進制）。
使用負權(quán)數(shù)的一個好處就是在表示負數(shù)時，我們不需要用到負號“-”。舉例來說，10
進制數(shù)-15 用-2 進制數(shù)來表示就是110001
:
-15 = 1×(-2)5 + 1×(-2)4 + 0×(-2)3 + 0×(-2)2 + 0×(-2)1 + 1×(-2)0
請設(shè)計一個程序讀入10 進制數(shù)和負數(shù)R，輸出這個10 進制數(shù)的R 進制的形式。
輸入數(shù)據(jù)有多組，以一行“0 0”結(jié)束。
Sample Input
30000 -2
-20000 -2
28800 -16
-25000 -16
Sample Output
11011010101110000
1111011000100000
19180
7FB8
【解題思路】
G題與這個題目很相像。
對于一個正數(shù)，我們可以先轉(zhuǎn)換為R進制數(shù)，再將R進制數(shù)轉(zhuǎn)化為－R進制數(shù)。知道這種辦法，后面就好辦了：對于奇數(shù)位（從后面數(shù)），－R與R進制代表的值是一樣的，對于偶數(shù)位，可以用高位減當前位表示（如：(-R)^3 * a = (-R)^4 – R^3 * (R-a)）。
再觀察負數(shù)，可以發(fā)現(xiàn)要轉(zhuǎn)換的是奇數(shù)位。
具體實現(xiàn)的時候就是先將一個數(shù)表示為R進制，然后在對所有的偶數(shù)位進行變換，并且注意進位的處理。對于負數(shù)，先變成他的相反數(shù)，然后對所有的奇數(shù)位進行變換。我在實現(xiàn)時直接用tag標記要轉(zhuǎn)換的數(shù)，分別用0、1分別表示正數(shù)、負數(shù)，然后利用數(shù)的奇偶進行轉(zhuǎn)換。
【題目代碼】
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 閱讀(307)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving