계단 오르기

제목:
계단은 n계단이 있는데 위층으로 올라가면 1단계를 올라갈 수도 있고 2단계를 올라갈 수도 있고 3단계를 올라갈 수도 있다. 프로그램을 짜서 계산하면 모두 몇 가지 다른 걸음걸이가 있습니까?
생각:
법칙 찾기: 4 단계 계단이 있을 때 4 단계 올라갈 때 필요한 걸음 수는 1 2 3 단계 올라갈 때 필요한 걸음 수의 총계와 같고, 5 단계 동리는 2 3 4 단계 올라갈 때 필요한 걸음 수의 총계와 같다.
코드:
1. 귀속 해법:
// : O(n³)
#include <stdio.h> // 
int f(int n)
{
	if (n < 0) return 0;
	if (n == 0 || n == 1) return 1;
	if (n == 2) return 2;

	return f(n - 1) + f(n - 2) + f(n - 3);
}

int main()
{
	int n;
	scanf("%d", &n);
	int z = f(n);
	printf("%d
"
, z); return 0; }

2. 반복 해법:
// : O(n)
#include <stdio.h> // 
int f(int n)
{
	if (n <= 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	int x1 = 1;
	int x2 = 2;
	int x3 = 4;
	for (int i = 4; i <= n; i++)
	{
		int x0 = x1;
		x1 = x2;
		x2 = x3;
		x3 = x0 + x1 + x2;
	}
	return x3;
}

int main()
{
	int n;
	scanf("%d", &n);
	int z = f(n);
	printf("%d
"
, z); return 0; }

좋은 웹페이지 즐겨찾기