NOIP2000提高组真题解析

第一题 进制转换

题目链接

解析

首先，我们知道对于10进制数x转2进制数，使用的算法是：

1. 求出x%2
2. 令x=x/2
3. 不断执行1,2,直至x为0,然后倒序输出步骤1的结果。

一般可以用数组存步骤1的结果倒序输出或者使用dfs回溯回来再输出。
对于负数的情况，比如\(-7=1*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0\)
对于第一步，有\(-7=-2*3-1\),余数是-1，根据题目要求，余数得是正数且比除数的绝对值要小，所以这样算是不行的。
如果余数是正数，自然不用做处理，如果是负数，得把余数处理成正数，考虑把商增加1，那么余数必然变成正数，且会小于除数的绝对值。这样就满足题目的要求了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,r;
void dfs(int x)
{
	if(x==0) return ;
	int b=x%r,k=x/r;
	if(b<0) b-=r,k++;
	dfs(k);
	if(b>=10) cout<<char(b+'A'-10);
	else cout<<char(b+'0');
}
int main()
{
	cin>>n>>r;
	cout<<n<<"=";
	dfs(n);
	cout<<"(base"<<r<<")"<<endl;
	return 0;	
}