当前位置:   article > 正文

猴子跳台阶问题的三种解法(C++实现)_一个顽猴在一座有n级台阶的小山上爬山跳跃,猴子上山一步可跳x级或跳y级,试求猴子

一个顽猴在一座有n级台阶的小山上爬山跳跃,猴子上山一步可跳x级或跳y级,试求猴子

递推/递归问题

  • 本人在学习递推时由于一个偶然的错误半天才解决此问题,除递推外也通过对本题的深入思考时发现了递推问题的一些特点,与此同时也深感自己代码能力的不足,写此文章希望帮助对此有需要的人。
  • Tip:问题来自学堂在线程序设计基础

问题描述
一个顽猴在一座有N级台阶的小山上爬山跳跃,猴子上山一步可跳x级或跳y级,试求猴子上山到N级台阶有多少种不同的爬法?猴子从山脚开始跳,可认为是第0阶。

输出描述
三个正整数N,X,Y,用空格隔开。 (x <= y <= N <= 100)

输出描述
猴子上山到第N级台阶有多少种不同的爬法,如果不能到达则输出“sorry”。

样例输入

3 1 2

样例输出

3

注释

保证最终答案不超过int范围


问题分析
假设在刚拿到问题不清楚用哪种方法求解,不妨枚举一下台阶跳法和N、X 、Y之间的关系。注意到一种特殊情况,当X=Y时:

  1. 如果N不能被X整除,则没有满足条件的跳法。
  2. 如果N可以被X整除,则有且仅有一种跳法(即每次跳X阶,总共跳N/X次)。

针对X≠Y的情况,若仅考虑猴子有多少种跳法而不分析具体的细节,我们先用枚举观察规律。
X=1,Y=2:

N方法
1(1)共1种
2(11,2)共2种
3(111,12,21)共3种
4(1111,112,121,211,22)共5种
5(11111,1112,1121,1211,122,2111,212,221)共8种
6(111111,11112,11121,11211,1122,12111,1212,1221,21111,2112,2121,2211,222)共13种
X=1,Y=3:
N方法
-------------
1(1)共1种
2(11)共1种
3(111,3)共2种
4(1111,31,13)共3种
5(11111,113,131,311)共4种
6(111111,1113,1131,1311,3111,33)共6种
注意到以上两种方法Y可以被X整除,再根据以上方法列出一个观察Y不可以被X整除的情况:
X=2,Y=3:
N方法
-------------
10
21
31
41
52
62
73
不难发现,X=1,Y=2时恰好为斐波那契数列从第2项开始的情况
X=1,Y=2时从第3项满足递推关系f(n) = f(n-1) + f(n-2)。
X=1,Y=3时从第3项满足递推关系f(n) = f(n-1) + f(n-3)。
X=2,Y=3时从第5项满足递推关系f(n) = f(n-2) + f(n-3)。

我们通过对比发现,这道题可以用递推关系漂亮地解决,只要枚举小于X+Y的项,那么剩余项就可以用递推关系计算出来。
注意到当Y可以被X整除时,从第Y项(Y>3)就有f(n) = f(n-X) + f(n-Y),Y=2时由斐波那契数列知可以看做存在f(0) =1的一种特例。
当Y不可以被X整除时,从第X+Y项也有f(n) = f(n-X) + f(n-Y)。

上述思路的代码:

#include <iostream>
#include <memory.h>
using namespace std;

int main() {
	int n = 0, x = 0, y = 0;
	cin >> n >> x >> y;
	long f[101];
	memset(f, 0, 101);
    //不存在方案的台阶数即默认为0

	int max = (y > x ? y : x);
	int min = (y > x ? x : y);
	int derta = max - min;
	int up = x + y;
	if (max % min == 0)
		up = max;

	if (x == y) {
		if (n % x == 0) {
			cout << 1 << endl;
			return 0;
		}
		else {
			cout << "sorry";
			return 0;
		}
	}

//实现部分
	for (int k = 1; k <= up; k++) {
		if ((k % x == 0 || k % y == 0) && k != up) {
			f[k - 1] += 1;
		}
			
		if (k == up && (x != y))
			f[k - 1] += 2;
	}
	for (int i = x + y; i <= n; i++) {
		f[i - 1] = f[i - x - 1] + f[i - y - 1];
	}

	if (f[n - 1] == 0)
		cout << "sorry";
	else
		cout << f[n - 1] << endl;

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

Tip:本人在使用递推方法由于sorry时把“s”写成了“S”,导致OJ一直反馈WA,才想了第二种方法。(读题时认真点啊喂!)


方法2

以N=6,X=1,Y=2为例,在没想出来方案时本想如何让计算机按照如下1-13序号的规律输出:
在这里插入图片描述

但是换一种角度考虑,这13种方案中:

  • 只存在数字1的方法只有(1)一种.
  • 只存在数字2的方法只有(13)一种.
  • 存在1个数字2的方法为图中蓝圈标记的方案,共有5种,即1个2和4个1,且数字总数为5.
  • 存在两个数字2的方法为图中绿圈标注的方案,共6种,即2个2和2个1,且数字总数为4.

仔细观察后发现,蓝圈标出的数字不正是排列组合问题中的 C 5 1 {{C_5^1}} C51 C 5 4 {{C_5^4}} C54吗(总共5个数字,1个2或4个1),总共有5组这样的方案( C 5 1 {{C_5^1}} C51 = C 5 4 {{C_5^4}} C54=5);而绿圈标注的数字则是 C 4 2 {{C_4^2}} C42,总共有6组这样的方案( C 4 2 {{C_4^2}} C42 = 6)。
根据此思路,第一种和第二章情况可以视为 C 1 1 {{C_1^1}} C11 = 1。

如果感兴趣的话可以验证其他情况,也是如此。
发现这一规律后我们可以利用双for循环,遍历X和Y可以取值的所有可能,仅计算可行方案中有多少个X多少个Y,剩下的交给排列组合函数解决即可,所有的方案数加上排列组合可能存在的所有数字即为本题答案。

以下为该思路的代码:

#include <iostream>
using namespace std;

int arrangement(int i, int j) {  //计算排列问题
	int all = i + j;
	double on = (double)all;
	double down = 1;
	int min = (i > j ? j : i);   //减少运算次数

	for (int k = 1; k < min; k++) {
		on *= ((double)all - (double)k);
		down *= ((double)k + 1);
	}
	int mid = (int)(on / down);
	//	cout << mid << endl;
	return mid;
}

void func(int n, int x, int y) {
	int Count = 0;
	int now = 0;  //猴子当前位置为第0阶
	int rx = n / x;
	int ry = n / y;   //循环次数最多只可能为n取余

	//x=y时的情况
	if (x == y) {
		if (n % x == 0) {
			cout << 1;
			return;
		}
		else {
			cout << "sorry" << endl;
			return;
		}
	}

	//x不等于y时的情况
	int px = 0, py = 0;       //当前数组指针
	for (int i = 0; i <= rx; i++) {
		for (int j = 0; j <= ry; j++) {
			now = i * x + j * y;
			if (now == n) {
//				cout << n << " = " << x << "*" << i << " + " << y << "*" << j << endl;
				if (i == 0 || j == 0)
					Count++;
				else {
					Count += arrangement(i, j);
				}
			}
		}
	}

	if (Count == 0) {
		cout << "sorry" << endl;
		return;
	}
	cout << Count << endl;
	return;
}

int main() {
	int n = 0, x = 0, y = 0;
	cin >> n >> x >> y;
	func(n, x, y);

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

总结
在解决问题过程中,如果出现类似第二个思路中的可行解的形式,如方案中有(112,121,211)出现数字相同但可以视为不同的解决方案,即括号中有3种不同的方案,则可以使用递推求解。
Tip:上述方案可视为共3个数,3种情况,即 C 3 1 {{C_3^1}} C31 = C 3 2 {{C_3^2}} C32 = 3.

方法优化和解法3
注:该方法由于需要遍历每种可能,时间复杂度为o(n²),若延拓到有3个或多个变量会导致运行速度非常慢,所以可以对该方法进行优化。
以N=5,X=1,Y=2为例,观察下图:
在这里插入图片描述利用二叉树可以很形象地看出问题的本质。
图中的8个ok分别对应着从N=5至当前节点的8种方法,线路上的数字表示在当前台阶向后跳的步数。由于方法2在双for循环时穷举的是补全的整棵二叉树,故可以在循环条件中加上当前台阶数是否大于总台阶数。

但至此就可以抛开第二个方法了,因为一旦可以跳越的台阶数超过2,使用我们学过的排列组合求解问题就会变得非常困难和复杂了(因此不推荐大家使用),为了简化求解方法,依照此二叉树我们可以用分而治之的方法漂亮地解决。

  • 递归时还是需要考虑特殊情况(X=Y),仅把实现部分的代码替换即可。

递归写法的代码:

#include <iostream>
using namespace std;

int Count = 0;  //可行条件
void stair(int n, int x, int y) {
	//递归终止条件
	if (n == 0) {
		Count++;
		return;
	}
	if (n < 0)
		return;

	//X Y两种情况
	if (n >= x)
		stair(n - x, x, y);
	if (n >= y)
		stair(n - y, x, y);
}

void judge() {
	int n = 0, x = 0, y = 0;
	cin >> n >> x >> y;

	//不存在方案的台阶数即默认为0
	if (x == y) {
		if (n % x == 0) {
			cout << 1 << endl;
			return;
		}
		else {
			cout << "sorry";
			return;
		}
	}

	stair(n, x, y);
	if (Count == 0)
		cout << "sorry";
	else
		cout << Count << endl;
}

int main() {
	judge();
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

当有多种跳台阶方法或有的台阶存在限定条件可以参考这篇
下楼问题


若文章有不足之处还请大家在评论区指正。

补充
如果原有问题变为了带有决策约束,如:总共n层楼梯,最开始可以走1步、2步、3步,但如果上一步走了1步,则下一步就只能走2或3步;上一步走了2步,则下一步只能走1或3步……,此类问题可以使用状态机模型结合动态规划解决,状态机的思想可以非常好的在很多具有决策性约束的问题。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/689968
推荐阅读
相关标签
  

闽ICP备14008679号