工匠大師Hill打造出一個精致的天平, 對他的徒弟Oren說:“你幫我做一些砝碼配套,為了方便攜帶,砝碼數目要盡量少”。
Oren:“好。我將按照2進制的規則打造,也就是1,2,4,8,16等等,這樣在稱量同等重量下使用的砝碼數量最少,只使用7個砝碼就可以稱量1-127的重量。”
Hill:“No, you are wrong”。
Oren:“難道還有更好的方法?2進制是最優的,這一點是可以證明的”
Hill:“如果只允許砝碼放在天平的一端,那么你說的是對的,可是并沒有人限制我們可以在天平的兩端放置砝碼。所以可以有更好的方法。如可以設計砝碼重量為1,3,9,27,81,只用5個砝碼就可以稱量1-121”。
Oren:“原來是3進制,那怎么稱重呢? 如100克重量?”
Hill:“在天平的左端放上重物,再放上砝碼9,右端放砝碼1, 27, 81”。
Oren:“嗯,可這是怎么算出來的呢?”
Hill:“It’s your business”。
現在,作為Oren的朋友,請你設計一個程序來計算在這種砝碼下應如何稱量。
Input:
輸入包括多個整數,每個數n占據一行,代表要稱重的重量。0 < n <= 1000000000。
Output:
對于每個輸入的整數,計算當此重量放置在天平左端時,應如何安排3進制的砝碼,使天平平衡。每個結果輸出一行,輸出格式如例子所示,每個數字后面一個空格,如某一側沒有砝碼,則輸出0,多個砝碼按重量升序排列。
Sample Input:
100
30
Sample Output:
9 left, 1 27 81 right.
0 left, 3 27 right.
----------
題目很經典
不要誤解題意,注意n的范圍,
不是搜索。 點下面的加號打開代碼

別人的代碼
#include"stdio.h"
int left[20],right[20];
int main()
{
int n;
while(scanf("%d",&n)==1)
{
int d=1,i=0,j=1,k;
while(n)
{
while(!(n%3)) {n/=3; d*=3;}
if(n%3==1){right[i++]=d; n--;}
else if(n%3==2) {left[j++]=d; n++;}
}
if(j==1) for(k=0;k<j;k++) printf("%d ",left[k]);
else for(k=1;k<j;k++) printf("%d ",left[k]);
printf("left, ");
for(k=0;k<i;k++) printf("%d ",right[k]);
printf("right.\n");
}
return 0;
}
posted on 2009-07-19 15:46
luis 閱讀(442)
評論(1) 編輯 收藏 引用 所屬分類:
陷阱題