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