|
uvaoj 11121 Base -2 整数转成负数进制
给定一个十进制的数，将其转成-2进制的数。也就是n=b0+b1*(-2)+b2*(-2)^2+b3*(-2)^3...。其中bi为0或1。
算法的描述很简单：n mod -2 余数可能为-1,0,1，但是不能出现-1，只能有0，1所以将-1变为1，并且商要加1。然后依此迭代直到商为0为止。
先来看看对一个数n变成m(m>0)进制的情况，每次模m，除m直到n为0为止，把得到的余数逆序就是m进制的数。也就是说第i(i总0开始计数)此迭代得到的是权重为m^i的位置上的数，如果我们把第i次的商加1，那么，它影响的是第i+1此迭代产生的余数，相当于把原来的数加上了m^(i+1)。
在这里，我们将余数-1变成了1，当n为正数的时候，只有当i为奇数的时候才能产生余数-1（因为余数的正负号只和n的正负号有关），那么这个位置就应该是-1*(-2)^i，因为i是奇数，所以也就是2^i，我们把-1变成了1，也就是变成了-2^i，那么就少了2^(i+1)，少了，就要加上，惊奇的发现只要在这轮迭代的商上加上1，就相当于加上了2^(i+1)，真是完美。当n为负数的情况类似。
代码如下：
/*************************************************************************
> File Name: 11121.cpp
> Author: gwq
> Mail: gwq5210@qq.com
> Created Time: 2015年01月06日 星期二 20时22分05秒
************************************************************************/
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())
using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;
const double esp = 1e-5;
#define N 1010
int ans[N];
int main(int argc, char *argv[])
{
int t;
int c = 0;
scanf("%d", &t);
while (t--) {
int n;
int cnt = 0;
scanf("%d", &n);
clr(ans, 0);
while (n != 0) {
ans[cnt++] = n % (-2);
n /= -2;
if (ans[cnt - 1] == -1) {
ans[cnt - 1] = 1;
++n;
}
}
printf("Case #%d: ", ++c);
for (int i = cnt - 1; i > 0; --i) {
printf("%d", ans[i]);
}
printf("%d\n", ans[0]);
}
return 0;
}
有了前面的讨论，就不难写出来转成任意负数进制的情况了，转成了-m(m>0)进制，那么在i为奇数时就会产生余数-p(0<p<m)，对应的位值为-p*(-m)^i=p*m^i，我们可以将p变成m-p，也就变成了-(m-p)*m^i，相当于减小了m^(i+1)，那就要补回来，同上边一样，在商的位置加上一就可以了。
代码只需要该一点就行了。
参考：
1）http://www.cnblogs.com/scau20110726/archive/2012/12/21/2828420.html | 
转播
