跳台阶问题-创新互联

• 跳台阶问题
• 递归方式
• 非递归方式
• C语言代码实现
• 二、C++
• 总结

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：青蛙每次只有一阶或者两阶两种跳法，那么：
假设第一次跳的是一阶，那么剩下的n-1个台阶，跳法是f(n-1)
假设第一次跳的是两阶，那么剩下的n-2个台阶，跳法是f(n-2)
由上面两种假设可得：f(n) = f(n-1) + f(n-2)
由实际情况可知：f(1) = 1，f(2) = 2
最终得出的是一个斐波那契数列：
| 1，n = 1
f(n) = | 2, n = 2
| f(n-1) + f(n -2), n >2

这种方法是最低级的做法，有很多重复计算，效率很低。利用数列的思想，直接写出An的表达式，An = An-1 +An-2

int D_jump_floor(int n)//递归
{if (n<= 2)
	{return n;
	}
	else
	{return D_jump_floor(n - 2) + D_jump_floor(n - 1);
	}
}

根据斐波那契数列推导，从下往上算，避免重复计算，提高效率

int FD_jump_floor(int n)//非递归
{int a1 = 1;//第一个数
	int a2 = 2;//第二个数
	int sum;
	if(n ==1)
	{sum =1;
	}
	else if(n==2)
	{sum = 2;
	}
	else 
	{for(int i = 3;i<=n;i++)
    	{	sum = a1 + a2;
	    	a1 = a2;
	    	a2 = sum;
		}
		return sum;
	}

}

#include#includeint D_jump_floor(int n)//递归
{if (n<= 2)
	{return n;
	}
	else
	{return D_jump_floor(n - 2) + D_jump_floor(n - 1);
	}
}

int FD_jump_floor(int n)//非递归
{int a = 1;//第一个数
	int b = 2;//第二个数
	int c = a;//把c赋值为a
	while (n >2)
	{c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{int n = 0;
	printf("请输入跳的台阶数：");
	scanf("%d", &n);
	int ret1 = D_jump_floor(n);
	int ret2 = FD_jump_floor(n);
	printf("%d\n", ret1);
	printf("%d\n", ret2);
	system("pause");
	return 0;
}

递归比较无脑，但是时间复杂度长

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧