[UVa]11121:Base -2

這題可以先將輸入的數字的絕對值換成2進位制，
例如：7 => 111、-7 => 111。
再來從小到大看看它由哪些2的幾次方組成，
如果該次方與輸入的數字同號時，換成base(-2)的時候，也一樣會有該次方；
如果該次方與輸入的數字不同號時，換成base(-2)的時候，就需要該次方與該次方+1兩個所組成。
例如：
7 = 111 有2^0、2^1、2^2。
2^0 -> (-2)^0 直接換過來即可。
2^1 -> ((-2)^1 + (-2)^2) 該次方+該次方的下一個次方即可組成。
2^2 -> (-2)^2 直接換過來即可。
加起來會有 1個(-2)^0，1個(-2)^1，2個(-2)^2，
2個(-2)^2要進位，但是對於base(-2)又得再利用(-2)^3+(-2)^4才能組起來，
所以答案就會是 11011 。

[C](0.044)

	#include<stdio.h>
	#include<stdlib.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int x;
	for( x = 1 ; x <= N ; x++ )
	{
	int n;
	scanf( "%d", &n );
	if( n == 0 )
	{
	printf( "Case #%d: 0\n", x );
	continue;
	}
	int b[50] = {0}, bnum = 0;
	int ntemp = abs( n );
	while( ntemp )
	{
	b[bnum++] = ntemp % 2;
	ntemp /= 2;
	}
	int negorpos = ( n > 0 )? 0 : 1;
	int carry = 0;
	int i;
	for( i = 0 ; i < bnum ; i++ )
	{
	int temp = carry;
	carry = ( b[i] + temp ) / 2;
	b[i] = ( b[i] + temp ) % 2;
	if( i % 2 != negorpos && b[i] )
	carry++;
	}
	if( carry )
	{
	if( i % 2 != negorpos )
	{
	b[bnum++] = 1;
	b[bnum++] = 1;
	}
	else
	b[bnum++] = 1;
	}
	printf( "Case #%d: ", x );
	for( i = bnum-1 ; i >= 0 ; i-- )
	printf( "%d", b[i] );
	printf( "\n" );
	}
	}
	return 0;
	}

view raw UVa11121.c hosted with ❤ by GitHub