4. c언어 재귀함수 - 계단오르기, 이분검색

◆ 계단 오르기

   총 n개의 계단이 있다. 처음부터 시작하여 꼭대기까지 올라가는데 한 번에 한 칸, 두 칸, 세 칸씩 올라갈 수 있다고 한다. 예를 들어, 총 3개의 계단이 있을 경우에는 다음과 같은 네 가지 방법으로 계단을 오를 수 있다.

n이 주어질 때, 계단을 오르는 서로 다른 방법의 총 가지 수를 구하는 프로그램을 작성하시오.

[ 계단 오르기 소스 ]

#include <iostream> 
using namespace std; 
int rec(int); 
int main() 
{ 
      int n; 
      cin >> n; 
      cout << rec(n); 
      return 0; 
} 
int rec(int n) 
{ 
      if(n==1 || n==2) return n;
      else if(n==3) return 4; 
      else return rec(n-1) + rec(n-2) + rec(n-3); 
}

 

■ 수 알아맞히기 (이분검색)

  "수 알아맞추기"게임을 컴퓨터가 할 수 있도록 하는 프로그램을 작성하시오. 이 게임은 다음과 같이 진행된다. 게임에 임하는 사람으로 하여금 자신이 좋아하는 숫자를 마음에 생각하도록 하고 컴퓨터는 이 숫자를 맞추어 간다. 컴퓨터가 추측해 보여주는 숫자에 대한 자신이 생각하고 있는 숫자와 비교해 높은 숫자인지, 낮은 숫자인지를 알려주어 컴퓨터가 다음 추측 숫자를 계산하도록 한다.

▶ 입력형식

① 1에서 100까지의 숫자 중에 마음에 드는 숫자를 하나 생각한다.

② 컴퓨터가 보여주는 숫자가 생각했던 숫자와 같으면 'y'를, 생각했던 숫자보다 높으면 'H', 낮으면 'L'을 입력한다.

▶ 출력형식

  맞으면 총 몇 번의 과정을 거쳤는지 출력하고 종료한다.

▶ 입력과 출력의 예

당신이 생각하고 있는 숫자가 50입니까? L 그럼 당신이 생각하고 있는 숫자가 75입니까? L 그럼 당신이 생각하고 있는 숫자가 88입니까? H 그럼 당신이 생각하고 있는 숫자가 81입니까? H 그럼 당신이 생각하고 있는 숫자가 78입니까? H 그럼 당신이 생각하고 있는 숫자가 76입니까? L 그럼 당신이 생각하고 있는 숫자가 77입니까? y 7번 만에 맞추었지요?