【跳台阶问题】C语言

• 跳台阶问题
• • 问题描述
  • 实际实现
  • 通项
  • • 斐波那契数列
  • C语言代码
  • • 迭代(循环)方式实现

有n级台阶，每次只能向上跳1级或2级台阶，求到达最高级台阶的跳跃方式数c。

n=1时，跳1级，c=1；
n=2时，跳1+1级或跳2级，c=2；
n=3时，跳1+1+1级或1+2级或2+1级，c=3；
n=4时，跳1+1+1+1级或1+2+1级或2+1+1级或1+1+2级或2+2级，c=5；
…

为了实现跳跃n级台阶，可以先跳(n-1)级台阶，再跳1级台阶；或先跳(n-2)级台阶，再跳2级台阶。
总跳跃方式数为c(n)=c(n-1)+c(n-2).

1，1，2，3，5，8，13，21，…
斐波那契数列的第n项等于第(n-1)项与第(n-2)项之和。

//函数递归部分
int Tiao(int n) {
	if (n == 1) {
		return 1;
	}
	else if (n == 2) {
		return 2;
	}
	else {
		return Tiao(n - 1) + Tiao(n - 2);
	}
}

int main() {
	int n = 0;
	printf("请输入台阶数：");
	scanf("%d", &n);
	int c = Tiao(n);
	printf("跳跃方式数为：%d", c);
	return 0;
}

int Tiao(int n) {
	int cn_1 = 2, cn_2 = 1, cn = 0;    //初始c1=cn_2=1,c2=cn_1=1
	if (n == 1) {
		cn = 1;
	}
	else if (n == 2) {
		cn = 2;
	}
	while (n > 2) {
		cn = cn_1 + cn_2;
		cn_2 = cn_1;    //cn_2后移一位
		cn_1 = cn;    //cn_1后移一位
		n--;
	}
	return cn;
}