정보 올림피아드 문제인데.. 풀이 과정이 궁금합니다.(재귀함수)
희나리
질문 제목 :정보 올림피아드 문제인데.. 풀이 과정이 궁금합니다.재귀함수에 관한 문제입니다. 답은 71인데 풀이가 궁금합니다.
다른 문제는 다 푸는데 재귀함수에 관한것은 접근 조차 못하겠네요.. ㅜㅜ
질문 내용 :
f(25, 60)을 실행한 후, count의 값은 무엇인가?
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
int count = 0;
int f(int a, int b)
{
count++;
if (a == b)
{
return a;
}
else
{
int mid;
mid = (a + b) / 2;
return f(a, mid) + f(mid + 1, b);
}
}궁금한것은 풀이과정입니다..
-
다이
감사합니다!
-
Soeun
제가 풀어본 방법입니다.
f(25,27) = f(25,25)+f(26,26)+f(27,27)
f(25,28) = f(25,25)+f(26,26)+f(27,27)+f(28,28)
결국 f(25,60) = f(25,25)+.....+f(60,60) .....1
f(x,x)가 하나 생길때 마다 count++ 되는 규칙을 찾음.
f(x,x)의 총 개수는 26개이므로 1 식까지의 count값 = 35
f(25,25) -return 25하며, 이 과정마다 coun -
민들레
return a니까 71번이 아니라 한 6~7번쯤 돌리면 될것같은데...
-
가림새
그건알아요.. 근데 답이 71이면 결국 총 71번 돌려야한다는건데 그걸 좀더 쉽게 하는방법이 없는지 궁금했습니다.
-
마징가
12,60이니까 a!=b 이고 그러면 mid=37, 여기서 return값은 f(25,37)+f(38,60)
다시 대입해서 mid 구하고
양쪽 변수가 같아질때까지 돌리시면 되요