Sicily 1295 负权数 (SOJ 1295)「进制转换」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/145

20130619.后来我在网上漫看Matrix67的博客,发现了这篇专门讲述进制转换的,“好嘢大家摞出来分享”,可以先参看Matrix67《漫话进位置》

原题地址:点击打开链接

这题是目前我见过最难的(对于我来说)进制转换题,当然对于一些大牛来说想必思路是十分的清晰,可是对于鄙人是十分困难。做题思路是问了周生然后才写出来的,通过的人数比较多““莫非是水题行列之一?咳咳,不管怎么说,做这到题对于我的提升还是非常大的,建议各位也思考一下。

看到一个比较神的解法,链接在此:点击打开链接

但是我看不懂这个解法的原理……所以我还是用我理解的解法来说好了。

——————正文——————

类比一下正常的进制情况下如何表示一个数?其实就是用进制的不同次幂配上系数,然后组合起来。

说得更本质一点,就是我们要从高位开始“试错”,看看在当前这个位所能表示的范围有没有包含所要求的数,例如:

对于3进制的数,如何表示十进制的10?

  1. 首先我们试一下只有1位的情况下,能不能表示,1位的情况,最小是0,最大是2,显然10不在[0,2]这个范围内,1位无法表示
  2. 然后试一下有2位的情况,这种情况下,最小是0,最大是2*3^1+2*3^0=8,可见10不在[0,8]范围内,2位无法表示
  3. 然后是一下3位的情况,这样子,最小是0,最大是2*3^2+2*3^1+2*3^0=26,10在[0,26]范围内,因此在3进制中,3位就必定可以表示十进制中的10

然后从高位往回推,在第三位应该填的数字是多少?假设填k(在3进制下,k必定小于3),那么k必须满足(10-k*3^2)<=2*3^1+2*3^0

為什麼呢?填了第3位后,剩下的数是10-k*3^2,如果这个时候不满足上面的不等式,那么剩下的两位是无法继续表示这个剩余数的。

取k=1,即第3位添1,那么剩下10-1*3^2=1;

看看第二位,假设第二位填k1,因为1<=2*3^0成立,所以k1填0即可,第2位位0

最后一位很简单了,直接填1就可以了,所以10在3进制中表示就是101.

我相信上面的叙述没有结束,肯定有人就知道这题的思路是怎么样了,没错,从地位开始计算,每增加一位,求出当前位置可以表示出的范围,然后看看要求的n是否在这个范围内即可,原理和上面一模一样。同时介绍一下sscanf(不是scanf)这个函数,非常好用,可以自己查下使用方法,或者直接看下面的注释

那就直接上代码了,如下:

#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<memory.h>
#define MAXX 32770
using namespace std;
char s[50];           //字符串用于读取输入
int a[50];            //保存结果
int n,r;
int mp[17][32][3];    //mp[i][j][0]表示-i进制下其j次幂是多少
                      //mp[i][j][1]表示-i进制下到第j位可表示的最小数
					  //mp[i][j][2]表示-i进制下到第j位可表示的最大数

bool outside(int index) //到第index位还是不能表示则返回true,否则false
{
	if(mp[-r][index][1]>n || mp[-r][index][2]<n)
	 return true;
	return false;
}
char cv(int digit)
{
	if(digit<10)
	 return '0'+digit;
	else
	 return 'A'+digit-10;
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    for(int i=-2;i>=-16;--i)
    { 
      int j=0;
      int mu=-i-1;
      mp[-i][j][0]=1;
      mp[-i][j][1]=0;
      mp[-i][j][2]=mu;
      while(abs(mp[-i][j][0])<=MAXX)
      {
        j++;
        mp[-i][j][0]=mp[-i][j-1][0]*i;
        if(mp[-i][j][0]>0)
        {
          mp[-i][j][1]=mp[-i][j-1][1];
          mp[-i][j][2]=mp[-i][j-1][2]+mp[-i][j][0]*mu;
        }
        else
        {
          mp[-i][j][1]=mp[-i][j-1][1]+mp[-i][j][0]*mu;
          mp[-i][j][2]=mp[-i][j-1][2]; 
        }
      }
    }//预处理完毕,不是必要的,但是测试数据多时跑起来会快一点
    while(scanf("%s",s)!=EOF)
    {
      if(s[0]=='#')
       break;
      sscanf(s,"%d",&n); //这是个非常方便的函数
						 //直接将字符串内容作为输入
						 //尤其适合于字符串转数字
      scanf("%d",&r);
      int i=0;
      memset(a,0,sizeof(a));
      while(mp[-r][i][1]>n || mp[-r][i][2]<n)
        i++;
      for(;i>=1;i--)
      {
		 a[i]=0;
         while(outside(i-1))
		 {
			n-=mp[-r][i][0];
			a[i]++;
		 }
      }
      a[0]=n;
      i=31;
      while(a[i]==0) i--;
      if(i<0) i=0;
      for(;i>=0;--i)
		printf("%c",cv(a[i]));
      printf("\n");
    }
}

 

1 条思考于 “Sicily 1295 负权数 (SOJ 1295)「进制转换」

发表评论

电子邮件地址不会被公开。 必填项已用*标注