下午比賽做得有點挫。被安排寫G題的解題報告，這里順便貼上來。
——littlekid
題目描述：
【Problem G - 數制轉換】
Description
有一種數制的基數是三，權值可以取-1,0,1，并且分別用符號-.0.1 表示。這種數值的
101 便表示十進制的10，即1×32 + 0×31 +
1×30 = 10，又如這種數制的-0 表示十進制
的-3，即-1×31 + 0×30 = -3。標稱要求把給定的有符號證書轉換為新數制的數，該數的
前面不能有多余的0，入10 的新數制表示是101，則不要輸出乘0101。
輸入格式
數據第一行的數字T 表示輸入數據有T
組，接下來的T 行每行有一個整數N(32 位整型
可表示范圍內)，整數內不會有其他分隔符。
輸出格式
對輸入的每一個數字輸出一行，該行是輸入行整數的新數制表示。
Sample Input
2
10
-3
Sample Output
101
-0
【題目分析】
對于每一位，他有一個權值，為這一位乘以3^(i-1)。本題關鍵點就在于要從后面的位開
始取。如果能想到這里題目就搞定了——實現起來比較簡單，還有一點就是負數問題，很快
就能想到每位取反。
【解題思路】
這個題目解法很簡單：首先是正數的情況，對N進行取余，如果得1則這一位為1，為0自然
為0，如果取模得2，則進行轉換，當前位取－1。對于負數，轉化為相反數處理，然后每位取
反，相反數得相反數就是這個數本身。
【樣例程序】
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-1-20 15:28:47
4 Problem Source:
5 Description:
6 ********************************************************************/
7 # include<stdio.h>
8
9 int main()
10 {
11 int t; scanf("%d", &t);
12 int tmp, k, cur, n;
13 int a[20], tag;
14
15 while (t --)
16 {
17 scanf("%d", &n);
18 tmp = n;
19 k = 0;
20 if (n == 0) ////這里開始未考慮到，WA了一次 !!!!!
21 {
22 printf("0\n");
23 continue;
24 }
25
26 tag = 1;
27 if (n < 0) //標記負數
28 {
29 n *= -1;
30 tag = -1;
31 }
32 //主要過程：對n不斷除3并求余數
33 while ( n != 0 )
34 {
35 tmp = n%3;
36 if (tmp == 2)
37 {
38 tmp = -1;
39 n += 2;
40 }
41 else
42 {
43 n -= tmp;
44 }
45 a[k] = tmp*tag;
46 n /= 3;
47 k ++;
48 }
49 //輸出結果
50 for (int i = k-1; i >= 0; i --)
51 {
52 switch(a[i])
53 {
54 case 0:printf("0");
55 break;
56 case -1:printf("-");
57 break;
58 case 1:printf("1");
59 break;
60 default:printf("ERROR\n");
61 }
62 }
63 printf("\n");
64 }
65 return 0;
66 }
67
posted on 2008-01-20 19:58
R2 閱讀(308)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving