为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 271666
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

对大数的进制转换,可以不用大数的除法运算。
假设要把一个二进制数1011,转换成一个三进制数。
1、用二进制数的第一位1去除以3,商为0,余数是1
2、由于前面一位的除法结果有余数,所以要把余数*(进制)+该为数字。对于本例,就是1(余数)*2(进制)+0(当前这位的数值)=2。除以3后,商0,余数是2
3、同2所述,2(余数)*2(进制)+1(当前这位的数值)=5。5除以3后,商1,余数2
4、同2所述,2(余数)*2(进制)+1(当前这位的数值)=5。5除以3后,商1,余数2
以上四步可以表示为 1011(2-based) / 3(要转换成的基数) = 0011(2-based 商).. 2(3-based 余数)
然后再让0011除以3,重复以上步骤,直到商为0。每次的余数的逆序就是以3为基的数。

1011/3 -->0011 ..2
0011/3 -->0001 ..0
0001/3 -->0000 ..1

所以,1011(2-based) --> 102(3-based)

参考http://acm.pku.edu.cn/JudgeOnline/problem?id=1220

#include <iostream>
#include 
<algorithm>
#include 
<vector>
#include 
<string>
using namespace std;
char index[62= {
'0''1''2''3''4''5''6''7''8''9',
'A''B''C''D''E''F''G''H''I''J',
'K''L''M''N''O''P''Q''R''S''T',
'U''V''W''X''Y''Z''a''b''c''d',
'e''f''g''h''i''j''k''l''m''n',
'o''p''q''r''s''t''u''v''w''x',
'y''z'};
int getValue(char ch)
{
    
if(ch>='0'&&ch<='9'return ch-'0';
    
else if(ch>='A'&&ch<='Z'return ch-'A'+10;
    
else return ch-'a'+36;
}
string change(int from,int to,string input)
{
    
string res="",tmp="";
    
int remainder,pos;
    
while(input.length()!=0)
    {
        remainder
=0;
        
for(pos=0;pos<input.length();pos++)
        {
            remainder
=remainder*from+getValue(input[pos]);
            
if(remainder<to)
            {
                tmp
=tmp+'0';
                
continue;
            }
            
else
            {
                tmp
=tmp+index[remainder/to];
                remainder
%=to;
            }
        }
        res
=index[remainder]+res;
        
for(pos=0;pos<tmp.length()&&tmp[pos]=='0';pos++);
        input
=tmp.substr(pos);
        tmp
="";
    }
    
return res;
}
int main()
{
    
int t,from,to;
    
string num;
    cin
>>t;
    
while(t--)
    {
        cin
>>from>>to>>num;
        cout
<<from<<" "<<num<<endl;
        cout
<<to<<" "<<change(from,to,num)<<endl<<endl;
    }    
}

posted on 2009-10-24 17:30 baby-fly 阅读(1630) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理