Question

急求！C语言递推问题？

题目描述：
一个顽猴在一座有N级台阶的小山上爬山跳跃，猴子上山一步可跳x级或跳y级，试求猴子上山到N级台阶有多少种不同的爬法？
输入格式
输入包含三个数据N，x，y（x＜＝y＜＝N＜＝30）
输出格式
猴子上山到第N级台阶有多少种不同的爬法,如果不能到达则输出“sorry”。
样例输入1
3 1 2
样例输出1
3
样例输入2
3 2　2
样例输出2
sorry

不要代码，给出正确思路就行
请高手帮忙！！
万分感激

Answer 1

倒着想，我先举个例子，比如N=10 x=3 y=4
那么 我要到在第10阶，一种办法是从第7阶走x=3步到10，另一种从第6阶走y=4步到10
这个问题化为走到7阶和6阶要如何走
再看7阶。一种办法是从第4阶走x步到7阶，另一种从第3阶走y=4步到7
再看6阶。一种办法是从第3阶走x步到6阶，另一种从第2阶走y=4步到6.但考虑到处若从2阶走4到6的话，2阶是不可能到达的。因为只能走3或4阶，所以这里删掉这种情况
就剩下走到第4阶和第3阶的走法了
显然它们各自只有一种走法
最后就是
3+3+4
3+4+3
4+3+3
共3种
这种思想就是倒着想，向前推进。再逆转过来。有点类似动态规划
化为一般的思想
走到N阶有几种走法的问题可以转化为走到N-X与走到N-Y阶之和（X!=Y)
而同理N-X要看N-2X与N-X-Y的走法之和
N-Y要看N-X-Y与N-2Y之和
依次下去。最终结束的条件就是N-aX或N-bY或N-cX-dY中任何一个小于给定的X或Y说明此种走法不通。那么去掉这种走法且结束。
若开始的时候上述条件就成立则为sorry

Answer 2

for(x=0;x<=N;x++)
for(y=0;y<=N;y++)
if(x+y<=N && N%(x+y)==0)
num++;//成功登山+一次

其实没怎么看懂你问的问题，感觉管台阶多少，应该都不会失败的x=1 y=0 再怎么跳都能上去 可能我理解有误

Answer 3

你逆推，假如它已经到达N级台阶处，现在它要后退，有两种可能，1 后退x级 2后退y级。当它处于后退一次之后的地方时，又有两种可能的后退可能。就这样不停的后退下去，再加上退出条件就可以了 修改下，正推逆推都一样的，还有不可达的情况，你只要在退出条件里做下文章就可以，假如她退到那里是n<0的话就是不可达，n==0的话就是可达。