下午比賽做得有點(diǎn)挫。被安排寫(xiě)G題的解題報(bào)告，這里順便貼上來(lái)。
——littlekid
題目描述：
【Problem G - 數(shù)制轉(zhuǎn)換】
Description
有一種數(shù)制的基數(shù)是三，權(quán)值可以取-1,0,1，并且分別用符號(hào)-.0.1 表示。這種數(shù)值的
101 便表示十進(jìn)制的10，即1×32 + 0×31 +
1×30 = 10，又如這種數(shù)制的-0 表示十進(jìn)制
的-3，即-1×31 + 0×30 = -3。標(biāo)稱(chēng)要求把給定的有符號(hào)證書(shū)轉(zhuǎn)換為新數(shù)制的數(shù)，該數(shù)的
前面不能有多余的0，入10 的新數(shù)制表示是101，則不要輸出乘0101。
輸入格式
數(shù)據(jù)第一行的數(shù)字T 表示輸入數(shù)據(jù)有T
組，接下來(lái)的T 行每行有一個(gè)整數(shù)N(32 位整型
可表示范圍內(nèi))，整數(shù)內(nèi)不會(huì)有其他分隔符。
輸出格式
對(duì)輸入的每一個(gè)數(shù)字輸出一行，該行是輸入行整數(shù)的新數(shù)制表示。
Sample Input
2
10
-3
Sample Output
101
-0
【題目分析】
對(duì)于每一位，他有一個(gè)權(quán)值，為這一位乘以3^(i-1)。本題關(guān)鍵點(diǎn)就在于要從后面的位開(kāi)
始取。如果能想到這里題目就搞定了——實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單，還有一點(diǎn)就是負(fù)數(shù)問(wèn)題，很快
就能想到每位取反。
【解題思路】
這個(gè)題目解法很簡(jiǎn)單：首先是正數(shù)的情況，對(duì)N進(jìn)行取余，如果得1則這一位為1，為0自然
為0，如果取模得2，則進(jìn)行轉(zhuǎn)換，當(dāng)前位取－1。對(duì)于負(fù)數(shù)，轉(zhuǎn)化為相反數(shù)處理，然后每位取
反，相反數(shù)得相反數(shù)就是這個(gè)數(shù)本身。
【樣例程序】
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) ////這里開(kāi)始未考慮到，WA了一次 !!!!!
21 {
22 printf("0\n");
23 continue;
24 }
25
26 tag = 1;
27 if (n < 0) //標(biāo)記負(fù)數(shù)
28 {
29 n *= -1;
30 tag = -1;
31 }
32 //主要過(guò)程：對(duì)n不斷除3并求余數(shù)
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 //輸出結(jié)果
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 閱讀(303)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
Problem Solving