[수학]-문제

1. -2진수 (백준 2089)

2. 진법 변환- Base Conversion (백준 11576)

---------------------------------

1. -2진수 (백준 2089 )

2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

입력 

첫 줄에 10진법으로 표현된 수 N(-2,000,000,000≤N≤2,000,000,000)이 주어진다.

출력 

-2진법 수를 출력한다.

예제 입력 복사
 -13

예제 출력 복사
 110111

풀이

- 일반 2진수로 변환하는 것과 동일하게 2로 나눠가면서 나머지를 알아내는 방법 사용하는데, 다른 점은 부호가 계속 바뀐다는 것.

  즉, 처음에 2로 나눠서 나온 값이 a이라면, 그 다음은 -a에 대해서 처리

- 음수에 대한 몫 계산할 때 유의. 즉, -7/2=-4

- 예를 들어 -13의 경우는,

  -13/2 = -7, 1

     7/2 = 3,1

   -3/2=-2,1

    2/2 = 1,0

  -1/2=-1,1 

   1/2 = 0,1

===> 110111

- 계산되는 이진수를 보관했다가 역으로 출력해도 되고, 아래 소스에서 처럼 재귀함수를 사용해서 바로바로 출력해도 무방.

 

소스

#include <stdio.h>
void go(int n){
	if(n==0) return;
	if(n%2==0){
		go(-(n/2));
		printf("0");
	}else{
		if(n>0)	go(-(n/2));
		else	go(-(n-1)/2);		
		printf("1");
	}
}
int main(){
	int n;
	scanf("%d",&n);
	if(n==0) printf("0");
	else go(n);	
	printf("\n");
	
	return 0;
}


2. 진법 변환- Base Conversion (백준 11576)
타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 세계에서도 프로그래밍을 하고 싶었던 정이는 백준 사이트에 접속하여 문제를 풀기로 하였다. 그러나 미래세계는 A진법을 사용하고 있었고, B진법을 사용하던 정이는 문제를 풀 수가 없었다. 뛰어난 프로그래머였던 정이는 A진법으로 나타낸 숫자를 진법으로 B변환시켜주는 프로그램을 작성하기로 하였다. 
N진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 숫자의 가짓수가 N이라는 뜻이다. 예를 들어 N은 17일 때 한 자릿수에서 사용할 수 있는 수는 0, 1, 2, ... , 16으로 총 17가지가 된다.
입력
입력의 첫 줄에는 미래세계에서 사용하는 진법 A와 정이가 사용하는 진법 B가 공백을 구분으로 주어진다. A와 B는 모두 2이상 30이하의 자연수다.
입력의 두 번째 줄에는 A진법으로 나타낸 숫자의 자리수의 개수 m(1 ≤ m ≤ 25)이 주어진다. 세 번째 줄에는 A진법을 이루고 있는 숫자 m개가 공백을 구분으로 높은 자릿수부터 차례대로 주어진다. 각 숫자는 0이상 A미만임이 보장된다. 또한 수가 0으로 시작하는 경우는 존재하지 않는다.
A진법으로 나타낸 수를 10진법으로 변환하였을 때의 값은 양의 정수이며 220보다 작다.
출력
입력으로 주어진 A진법으로 나타낸 수를 B진법으로 변환하여 출력한다.
예제 입력  복사
17 8
2
2 16
예제 출력  복사
6 2

풀이
- A진법 수를 10진수로 바꾸고, 다시 이것을 B진법으로 바꾼다.
* A진법 -> 10진법 : a[] -> k
int k=0;
for(int i=1;i<=m;++i) k = k*A + a[m];

* 10진법 -> B진법: k-> b[]
while(k){
b[++i] = k % B;
k /= B;
}

소스
#include <stdio.h>
int main(){
	int A,B;	
	scanf("%d %d",&A,&B);
	
	int m,x,ten;
	scanf("%d",&m);
	for(int i=1;i<=m;++i) {
		scanf("%d",&x);
		ten = ten * A + x;
	}
	
	//to B진수
	int k=0,b[26];
	while(ten){		
		b[++k] = ten % B; 
		ten /= B;
	}	
	
	for(int i=k;i>=1;--i) printf("%d ",b[i]);
	printf("\n");
	return 0;
}
-끝-