d**a
发帖数: 84 | 1 写一个程序(c++)，计算Fibonacci数列 要求
1. 不能用控制判断语句，例如if, ?:
2. 不能用循环 |
p*****n
发帖数: 368 | 2 用通项公式直接算？
【在 d**a 的大作中提到】
: 写一个程序(c++)，计算Fibonacci数列 要求
: 1. 不能用控制判断语句，例如if, ?:
: 2. 不能用循环
|
c**********e
发帖数: 2007 | 3 Just use the formula:
double fib(int n) {
double phi=(1+sqrt(5.0))/2;
return (pow(phi, n)-pow(1-phi, n))/sqrt(5.0);
} |
n****e
发帖数: 629 | 4 Fibonacci Q-Matrix
参见小尾羊大拿的日记经验
【在 d**a 的大作中提到】
: 写一个程序(c++)，计算Fibonacci数列 要求
: 1. 不能用控制判断语句，例如if, ?:
: 2. 不能用循环
|
c**********e
发帖数: 2007 | 5 The formula may be the only solution.
If no loop (while, or for), we can still use goto.
But without conditional if, one can not do it. "if" is so much
important. |
l***8
发帖数: 149 | 6 use recursion and shortcut boolean:
int fib(int n)
{
return (n < 2) || (n = fib(n - 2) + fib(n - 1)), n;
} |
m*****f
发帖数: 1243 | 7 不能用循环那肯定用递归贝
【在 d**a 的大作中提到】
: 写一个程序(c++)，计算Fibonacci数列 要求
: 1. 不能用控制判断语句，例如if, ?:
: 2. 不能用循环
|
g*******y
发帖数: 1930 | 8 其实这个我是向algorithmics大牛学习的。。。
【在 n****e 的大作中提到】
: Fibonacci Q-Matrix
: 参见小尾羊大拿的日记经验
|
C***n
发帖数: 452 | 9 那个还是要用if判断N是否为零嘛，不满足不用if的条件
【在 g*******y 的大作中提到】
: 其实这个我是向algorithmics大牛学习的。。。
|
C***n
发帖数: 452 | 10 这个解法不错，妙的惹开if语句
【在 l***8 的大作中提到】
: use recursion and shortcut boolean:
: int fib(int n)
: {
: return (n < 2) || (n = fib(n - 2) + fib(n - 1)), n;
: }
|
|
|
g*******y
发帖数: 1930 | 11 are you serious?
think about complexity~
【在 C***n 的大作中提到】
: 这个解法不错，妙的惹开if语句
|
C***n
发帖数: 452 | 12 please notice this question does not ask you to focus on complexity, only
asking you to skip "if"
how do you get away "if" if using the logN algorithm u mentioned? it needs
to identify whether N and (N&1) is 0, right?
【在 g*******y 的大作中提到】
: are you serious?
: think about complexity~
|
g*******y
发帖数: 1930 | 13 you can use similar trick to circumvent "if" in the recursive function
【在 C***n 的大作中提到】
: 那个还是要用if判断N是否为零嘛，不满足不用if的条件
|
C***n
发帖数: 452 | 14 so that is it, the key is to not use if and loop, not in complexity, I think
by the way, could you post a logN algirthm in a recrusive function without
if?
【在 g*******y 的大作中提到】
: you can use similar trick to circumvent "if" in the recursive function
|
g*******y
发帖数: 1930 | 15 at the cost of raising the complexity from Log(N) to exp(N)?
Think about low level bit manipulation tricks -- I guess you can do (almost)
everything without branching. Correct me if I'm wrong.
【在 C***n 的大作中提到】
: please notice this question does not ask you to focus on complexity, only
: asking you to skip "if"
: how do you get away "if" if using the logN algorithm u mentioned? it needs
: to identify whether N and (N&1) is 0, right?
|
g*******y
发帖数: 1930 | 16 http://graphics.stanford.edu/~seander/bithacks.html
Here you can study some bit manipulation tricks to circumvent branching.
Since some one mentioned the short circuit feature of "||" operator. I'm wondering if there's still some branching code generated by the compiler?
Even if no branching is allowed at all, I think it shouldn't matter:
branching is simply:
next PC = (cond)? PC1:PC2;
which could be re-written as：
nextPC = -cond & (PC1^PC2)^PC1;
think
【在 C***n 的大作中提到】
: so that is it, the key is to not use if and loop, not in complexity, I think
: by the way, could you post a logN algirthm in a recrusive function without
: if?
|
