- 主题:请教一个用迭代函数解决青蛙跳台阶的问题(带程序)
这类不定方程问题的解法叫DFS(深度优先搜索),用数组记录搜索过的树上的路径
const int r = 5;
const int m = 3;
// 数组里多定义一个元素,减少代码里的边界判断。数组全初始化为0
int jumps[r + 1] = {}; // 记录每一次跳分别是几层台阶
int partialTotals[r + 1] = {}; // 记录当前已经跳的台阶总数,部分和
// 找到一个解,打印出来
void print(int step) {
for (int k = 1; k <= step; ++k)
printf("%d ", jumps[k]);
printf("\n");
}
// 跳一下。step表示当前是第几跳
void jump(int step) {
// 当前这一跳的台阶数,从1到m都尝试一下。
for (int k = 1; k <= m; ++k)
{
// 当前这一跳所跳的台阶数
jumps[step] = k;
// 到目前为止跳过的总台阶数,部分和
partialTotals[step] = partialTotals[step - 1] + k;
if (partialTotals[step] == r) {
// 找到一个解,并终止当前的尝试,剪枝。因为在当前这一跳,不可能再找到下一个解了
print(step);
break;
}
else if (partialTotals[step] > r) {
// 部分和大于整体和,终止当前的尝试,剪枝。因为在当前这一跳,不可能再找到下一个解了
break;
}
else {
// 部分和小于整体和,尝试下一跳
jump(step + 1);
}
}
}
int main()
{
// 从第一跳开始
jump(1);
return 0;
}
--
修改:z16166 FROM 221.218.160.*
FROM 221.218.160.*
有两处错误
1、(RS - i)和0比较是三种情况,不是两种。
你的代码会导致(RS - i) < 0这种无解的情况下,也会执行BZ = BZ + 1,这样解的总数BZ是错的。(但这个题里正好没有错)
2、得到一个解后将J复位到1,是错的。
如果当前递归层数是n,那么当前一定是第n跳。
但是如果此时n并不是1,那么强行将J置为1,就会把第n跳(或者第x跳)的台阶数记录到第1跳里,是错的。
可以看一下我提供的代码,传给jump(int step)的参数step就是表示当前是第几跳,同时也对应着递归的层数。
这个step就是你的那个J变量,也就是7楼说的栈顶索引,是不能随便复位的。换句话说,J最好通过参数传递(这样天生就是栈顶索引),而不是用全局变量。
【 在 sqsl 的大作中提到: 】
: 我第2个函数几乎就是第1个翻版,只是调用一个数组存每一次跳了多少步。但是因为函
: 数迭代的结构,不是所有跳法都能记录齐全
: 我就是在学编程,遇到困难想解决
: ...................
--
修改:z16166 FROM 221.218.160.*
FROM 221.218.160.*
是递归,不是迭代
【 在 sqsl 的大作中提到: 】
: 第1个问题,我前面有限定条件: for(i=1;i<=__min(RS,MS);i++)
: 且MS(单次最大跳跃级数)也是小于等于RS(台阶总数)的,所以不会出现小于0的情况
: 。
: ...................
--
FROM 221.218.160.*
搞对就行了,现在没必要纠结算法效率和性能
printf这种i/o都是要耗时间的。
而且内存还要释放,虽然这种小demo不释放也不是啥问题。
【 在 sqsl 的大作中提到: 】
: 您说的J复位到1的错误,我去更改了,思路就是不复位到1,只是减1,相当于从上一种
: 跳法的尾巴回缩1位,目前程序是对的了。因为我的对跳步约定了不允许大于剩余台阶,
: 所以也没有用到break语句,没有剪枝那一步。
: ...................
--
FROM 221.218.160.*