POJ 3191 The Moronic Cowmpouter（进制转换）

题意：将一个10进制整数转化为-2进制的数。

思路：如果你将-2进制下的123转化为十进制是1*(-2)^2+2*(-2)^1+3*(-2)^0.所以十进制转化为-2进制就是一个逆过程。找到最小的非负整数x使得当前数减x能被2整除，这个x将作为新的最高位写到结果中，然后当前数减去x再除以-2，貌似在这里不能严格的说是余数，因为负数的余数不太准确。

 1 //POJ 3191
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 int main()
 9 {
10     __int64 n,flag,s[1005],i ;
11     while(~scanf("%I64d",&n))
12     {
13         if(n == 0)
14         {    printf("0
") ;
15         continue ;}
16         i = flag = 0 ;
17         memset(s,0,sizeof(s)) ;
18         while(n)
19         {
20             s[i] = n % 2 ;
21             if(n < 0)
22                 s[i] = -s[i] ;
23             n -= s[i] ;
24             n /= -2 ;
25             i++ ;
26         }
27         flag = i ;
28         for(i = 0 ; i < flag/2 ;i++)
29             swap(s[i],s[flag-1-i]) ;
30         for(i = 0 ; i < flag ; i++)
31             printf("%I64d",s[i]) ;
32         printf("
") ;
33     }
34     return 0 ;
35 }

View Code