Daily Algorithm - 고대 이집트 곱셈 (a la russe recursion)

문제

a larusse 알고리즘이란 컴퓨터에서 곱셈을 빠르고 쉽게 할 수 있는 알고리즘이다. 

이 알고리즘은 오직 덧셈과 쉬프트 연산만을 이용해서 이루어진다. 

두 정수 a, b를 곱하는 알고리즘은 다음과 같다. 

(1) declare n1, n2, n3 
(2) set n1 = a, n2 = b, n3 = 0 
(3) if n1 is odd then n3 = n3 + n2 
(4) n1 = n1 >>1, n2 = n2 <<1 ( <<= left shift, >>= right shift ) 
(5) if n1 != 0 then goto (3) 
(6) print n3 

위 알고리즘을 이용하여 입력받은 두 정수의 곱을 구하는 프로그램을 재귀로 작성하시오.

(반복문 불가, 반드시 재귀함수로 작성하시오.)

입력

두 정수 a, b가 공백으로 구분되어 입력된다. (두 정수의 곱이 2^31-1보다 크지 않다.)

출력

두 정수 곱을 출력한다.

예제 입력

6 3

예제 출력

18

풀이

#include <stdio.h>

int n3 = 0;

int alarusse(int n1, int n2)
{
	if(n1 % 2 != 0)
		n3 += n2;
	
	n1 >>= 1;
	n2 <<= 1;
	if(n1 != 0)
		alarusse(n1, n2);
	else
		return n3;
}

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", alarusse(a, b));
}

문제 출처 : http://koistudy.net/?mid=prob_page&NO=1080