도전하라! 시작하라!

프로그램 명: upstair                                                                                                            제한시간: 1 초

최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 출력 하는 문제이다.

그림은 n 이 4 인 경우의 예 이다.

• 1 - 2 - 3 - 4
• 1 - 2 - 4
• 1 - 3 - 4
• 2 - 3 - 4
• 2 - 4

입력

출력

입출력 예

입력

4

출력

5

프로그램 명: euclid

두 수를 입력받아 최대공약수,최소 공배수를 구하는 프로그램을 작성하시오.

입력

출력

입출력 예

입력

8 12

출력

4 24

유클리드 호제법

유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

- Wiki, 위키백과 -

1. 입력으로 두 수 m,n(m>n)이 들어온다.

2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.

3. n이 m을 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.

4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3으로 돌아온다.

최소공배수(lcm) = (A*B) / gcd(A, B);

프로그램 명: powerofx

x 의 y 거듭제곱을 구하는 문제이다.

2 10 을 입력 받으면 2 의 10 거듭제곱 1024 가 출력되어야 한다.

2^10 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2=1024

입력

출력

출력 결과는 정수 범위( 2^31 - 1)를 넘지 않는다.

입출력 예

입력

2 10

출력

1024

재귀(Recursion)

수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다.

-  Wiki, 위키 백과 -

long factorial(int number)

{

...

factorial(number - 1);    // 함수 내부에서 자기 자신의 함수를 호출 (재귀함수)

...

}

long factorial(int number)

{

if (number <= 1)

return 1;

else

return (number * fatorial (number -1));

}

int fibo(int n)

{

if (n==0)    return 0;

else if (n==1)    return 1;

else    return return fibo(n-1) + fibo(n-2);

}

main()

{

printf("%d", fibo(4));

}

long fibo (int n)

{

int fn, fn1, fn2;

int i;

if (n <=1)    return n;

else {

fn2 = 0;

fn1 = 1;

for (i=2; i<=n; i++) {

fn = fn1 + fn2;

fn2 = fn1;

fn1 = fn;

}

return fn;

}

}