注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

进制转换的应用  

2009-03-25 22:02:49|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Eva's Balance

Acceteped : 31   Submit : 80
Time Limit : 1000 MS   Memory Limit : 65536 KB
 

Description

Eva has a balance with 20 poises. The weights of the poises are 1, 3, 9, 27,...,3^19. Eva asserts that she has a way to measure any object whose weight is an integer from 1 to (3^20-1)/2. Assuming that Eva has placed an object with the weight in this range on the left tray of the balance, your task is to place the proper poises on the proper trays so as to weigh the object out.
 

Input

The first line is an integer T (1 <= T <= 20), which shows the number of the test cases. Each of the following T lines contains an integer W (1 <= W <= (3^20-1)/2), expressing the weight of an object.
 

Output

For each test case print a line, showing the weights of the poises on the left tray and the right tray. Use a space to separate the left tray and the right tray. The poises on the same tray are arranged in the increasing order, and a comma separates every two of them. If there is no poise on the tray, output "empty".
 

Sample Input

3
9
5
20
 

Sample Output

empty 9
1,3 9
1,9 3,27
 

Source

POJ Monthly--2004.07.18

 

题目大意:Eva有一个20个砝码的天平,砝码的重量分别是1,3,9,27,...,3^19。她断言只要是重量在1~(3^20-1)/2内的物体,都可以用这些砝码称出重量。现在给你个规定范围内的数,求出在托盘的两边应放的砝码。

主要思想:如果要天平平衡,要有等式W+a*3^i+...+b*3^j=c*3^m+...+d*3^n,经过变换后,有W=a0*3^0+a1*3^1+...+a19*3^19,且由题目可知a0~a19只能取1,0,-1。题目就转换为求一组序列使得前面的等式成立,若采用穷举法,则有3^20个可能性,显然行不通。仔细观察会发现等式类似于三进制表示,但是不同的是三进制中只有0,1,2三个数字,这里只能是1,0,-1。那么整道题目到这就转化为将一个十进制数转换成为平衡三进制。

代码如下:

#include<iostream>
using namespace std;
int fib(int b,int e);       //用来计算b^e
int main(){
    int t,w;
    int digit[20];          //记录权值为3^i的数的系数
    int i,j,flag;
    cin>>t;
    while(t--){
        cin>>w;
        i=0;
        while(w){
            if(w%3==2){    //如果余数是2,则将相应的系数赋值为-1,并将商加1。
                digit[i++]=-1;
                w=w/3+1;
                continue;
            }
            digit[i++]=w%3;
            w=w/3;
        }

        //下面是输出
        flag=0;
        for(j=0;j<i;j++){
            if(digit[j]==-1){
                if(flag==1)cout<<",";
                flag=1;
                cout<<fib(3,j);
            }
        }
        if(flag==0)cout<<"empty";
        cout<<" ";
        flag=0;
        for(j=0;j<i;j++){
            if(digit[j]==1){
                if(flag==1)cout<<",";
                flag=1;
                cout<<fib(3,j);
            }
        }
        cout<<endl;
    }
    return 0;
}
int fib(int b,int e){
    int i,mul=1;
    for(i=0;i<e;i++){
        mul=mul*b;
    }
    return mul;
}

后记:扩宽自己的知识面,学会将一个复杂的问题转换成简单的问题去解决。这道题目的输出显得有些复杂,可以改短一些,这里主要是为了防止细节的错误,没事的时候把它改改~

  评论这张
 
阅读(207)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017