d*******a
发帖数: 2336 | 1 Consider the following recursive function:
int c( int n, r){
if (r == 0 || r == n)
return 1;
return c(n-1,r)+ c(n-1,r-1);
}
Write a C++ program that finds the value of C(n,r) by removing the recursion
using a stack.
小弟实在是想不出来
谁能给个 答案，包子谢
有思路也行 新手
不知道如何处理每次pop 出来的c(?,?)里的?怎么表达 | K****n
发帖数: 5970 | 2 orz
如果要求用for loop写出来，那么这是算法课，如果要求用stack写出来，那么这是编
译课？
recursion本身就是用stack实现吧，可以用stack保存‘环境’，每次调用函数c之前把
n，r，和result放在一个小array里push进stack。但是其实也可以当算法题来做，就是
说把这个recursion展开，画成一个树，然后结果就是所有leaf node的和，剩下的就是
DFS了，其实BFS也行。。。但是要求用stack，故而假装是DFS.. 如果学过DP的话，怎
么做都行了。
不会c，凑合着看吧。算法扔了很久，不一定对，抛砖引玉
struct Node{
int r;
int n;
};
int d(int n, int r){
if(n
int ret = 0;
Stack s = new Stack();
n = new Node(r=r, n=n);
while(n != NULL){
if(n.r==0||n.r==n.n){
ret += 1;
}
else
{
r.push(new Node(r=n.r-1, n=n.n-1));
r.push(new Node(r=n.r, n=n.n-1));
}
n = s.pop();
}
return ret;
}
recursion
【在 d*******a 的大作中提到】
: Consider the following recursive function:
: int c( int n, r){
: if (r == 0 || r == n)
: return 1;
: return c(n-1,r)+ c(n-1,r-1);
: }
: Write a C++ program that finds the value of C(n,r) by removing the recursion
: using a stack.
: 小弟实在是想不出来
: 谁能给个 答案，包子谢
| d*******a
发帖数: 2336 | 3 谢谢 指点 是数据结构课 双黄包敬上
我也想是用一个tree来做 结果是leaf 的和
但是在拆解tree 的时候 parent 和children 的 那个关系式不知道如何写
用一个node 来保存的话 Node（n-1,r-1) 会不会让计算机不知道Node（？，
？）是多少
因为n.r 调用了很多次
【在 K****n 的大作中提到】
: orz
: 如果要求用for loop写出来，那么这是算法课，如果要求用stack写出来，那么这是编
: 译课？
: recursion本身就是用stack实现吧，可以用stack保存‘环境’，每次调用函数c之前把
: n，r，和result放在一个小array里push进stack。但是其实也可以当算法题来做，就是
: 说把这个recursion展开，画成一个树，然后结果就是所有leaf node的和，剩下的就是
: DFS了，其实BFS也行。。。但是要求用stack，故而假装是DFS.. 如果学过DP的话，怎
: 么做都行了。
: 不会c，凑合着看吧。算法扔了很久，不一定对，抛砖引玉
: struct Node{
| K****n
发帖数: 5970 | 4 r.push 写错了，应该是s.push
每个 while interation的n都是不一样的，哦。。。其实如果是c的话这个可能有
memory leak。。。应该把n给delete了再pop。FAIL
【在 d*******a 的大作中提到】
: 谢谢 指点 是数据结构课 双黄包敬上
: 我也想是用一个tree来做 结果是leaf 的和
: 但是在拆解tree 的时候 parent 和children 的 那个关系式不知道如何写
: 用一个node 来保存的话 Node（n-1,r-1) 会不会让计算机不知道Node（？，
: ？）是多少
: 因为n.r 调用了很多次
| a*******8
发帖数: 2299 | | r********n
发帖数: 7441 | 6 原程序本身也是一堆的问题，输入负数能够让你死机
recursion
【在 d*******a 的大作中提到】
: Consider the following recursive function:
: int c( int n, r){
: if (r == 0 || r == n)
: return 1;
: return c(n-1,r)+ c(n-1,r-1);
: }
: Write a C++ program that finds the value of C(n,r) by removing the recursion
: using a stack.
: 小弟实在是想不出来
: 谁能给个 答案，包子谢
|
|
