学步园

博文视点有奖答题第二题：青蛙跳台阶问题

（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

#include <stdio.h>
#include <stdlib.h>


int main(int ac, int* av[]){
	int num_steps, result;

	printf("Please input the num of steps\n");
	scanf("%d", &num_steps);
	
	result = 0;
	result += cal_steps(num_steps);

	printf("There are %d ways for the frog to pass %d steps.\n", result, num_steps);
}

int cal_steps(int n){
	int i, j, *a;
	
	a = (int*)malloc(n * sizeof(int));
	a[0] = 1;
	a[1] = 2;

	for(i=2; i<n; i++){
		for(j=0; j<i; j++)
			a[i] += a[j];
		a[i] += 1;
	}
	return a[n-1];
}

int cal_steps_two(int n){
	int i, pre, result, tmp;
	
	if(n == 1) return 1;
	if(n == 2) return 2;
	if(n > 2){
		pre = 1;
		result = 2;
		for(i=2; i<n; i++){
			tmp = result;
			result = result + pre;
			pre = tmp;
		}	
	}

	return result;
}

int cal_steps_recursive(int n){
	int steps;

	steps = 0;
	if((n == 0) || (n < 0)){
		return 0;
	}
	if(n == 1)
		return 1;
	if(n == 2)
		return 2;
	if(n > 2){
		steps += cal_steps(n-1) + cal_steps(n-2);	
	}	
	
	return steps;
}